PHP でアルゴリズムの問題を解いてみよう

こんにちは、仙台支社のあっきーです。
PHP でアルゴリズムの問題を解いてみましょう。アルゴリズムの学習は自分のコーディングに自信を付けたり、特に作りたいものが無いときでも手軽にコードを書く練習が出来て便利です。問題を解く言語は C++や Python 等がメジャーですが、PHP も使用可能です。

アルゴリズムを学習できるサイトは様々ありますが、今回は LeetCode(https://leetcode.com/) の問題を解いてみます。LeetCode では問題の難易度が Easy, Medium, Hard と分かれています。初めて学習をする方は、まず Easy の問題を解いてみるのが良いと思います。

問題を解いてみる

試しに Easy 問題の Single Number (https://leetcode.com/problems/single-number/) を解いてみます。問題文は英語ですが、英語が苦手でも Google 翻訳や DeepL 翻訳を使えば大体の意味を把握することは出来ると思います。

今回の問題は、配列内に１回しか出現しない数値を見つける（他の要素は２回現れる）というものです。問題の入力は関数の引数で渡され、解答を関数の返り値にします。
配列内の要素の出現回数をカウントし、１回しか現れなかった要素を答えとすると良さそうです。
コードは以下のようになります。

<?php
class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums)
    {
        $counter = [];
        foreach ($nums as $num) {
            if (!array_key_exists($num, $counter)) {
                $counter[$num] = 0;
            }
            $counter[$num] += 1;
        }

        foreach($counter as $num => $count) {
            if ($count === 1) {
                return $num;
            }
        }

        return 0;
    }
}

（※ 問題文にはuse only constant extra space. とありますが、話を簡単にするため、ひとまず配列を使用して回数をカウントしています）
コードを書いたら画面右下の「Run Code」でサンプルのテストケースを実行することが出来ます。
正しく動作していそうなことを確かめたら、「Submit」でコードの提出が可能です。

その他の解答について

問題の解き方は１つだけでなく、複数ある場合があります。画面左上の「Discuss」(https://leetcode.com/problems/single-number/discuss/) で他のユーザーの回答を見ることが出来ます。これらの解法の中で、個人的に面白いと感じたビット演算による解法を紹介します。

<?php
class Solution
{

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums)
    {
        $answer = 0;
        foreach ($nums as $num) {
            $answer ^= $num; // 全ての要素のXORを計算
        }
        return $answer;
    }
}

XORは同じ要素同士の演算結果が 0 になり、足し算のように順番を入れ替えて計算しても計算結果が変わらない、という性質があります。そのため、全ての要素のXORを取れば、１回のみ出現する要素を取得できることが分かります（２回現れる要素はXORで打ち消される）
このように Easy 問題でも、自分が思いつかないようなきれいな解法があったりするので勉強になります。

PHP で問題を解く場合の補足

問題の解法が分からなくても、C++、Java 等で解答のコードが記載されています。解答のコードはif文やforループ等、言語の基本的な機能しか使わないケースがほとんどです。
PHP を知っていれば他の言語で書かれた解答でも内容を何となく理解できるので、それらを頼りに PHP のコードを書くことができます。
次に、他の言語で書かれたコードを参考に PHP のコードを作る場合についていくつか捕捉します。

整数どうしの割り算

C++, Java 等の言語と違って、PHP では整数同士の割り算が整数になるとは限りません。他の言語で書かれたコードを参考に PHP で書き直す場合は注意が必要です。
intdiv, floor, ceil 等を用途に合わせて使用すると良いと思います。

<?php
$a = 5;
$b = 2;
var_dump($a / $b); // float(2.5)
var_dump(intdiv($a, $b)); // int(2)
var_dump(floor($a / $b)); // float(2)
var_dump(ceil($a / $b)); // float(3)

関数の計算量

アルゴリズムの問題はプログラムの実行時間に制限があり、処理の内容が合っていても実行時間が長すぎると不正解になります。実行時間が超過して不正解になっている場合、使用している関数の実行時間に問題が無いか確認する必要がある場合があります。以下のコードで実験してみます。

<?php
$n = 100000;
$a = array_fill(0, $n, 0);

$time_start = microtime(true);

$loop = 10000;
for ($i = 0; $i < $loop; $i++) {
    // 配列の先頭要素の出し入れ
    $v = array_shift($a);
    array_unshift($a, $v);
}

$time_end = microtime(true);
$time = $time_end - $time_start;
echo $time . "秒";

array_shift, array_unishftを使って配列の先頭要素の出し入れを行っています。$nの値を変化させると手元の環境で、実行時間に以下のような違いがありました。

$n の値	10000	100000
実行時間	0.6386 秒	12.5109 秒

このように $nの値が大きくなると、実行時間が大きくなってしまいます。上記の操作は SplDoublyLinkedList 等のクラスを使用すると実行時間を抑えることが出来ます。https://www.php.net/manual/ja/spl.datastructures.php
上記は例なので、実際に問題になることはあまりないかもしれませんが、アルゴリズムの問題を解いているとPHPが用意している関数の計算量を意識しなければならない場面が出てきます。

まとめ

PHP でも問題なくアルゴリズムの学習をすることが出来ます。PHP には便利な関数が沢山用意されていますが、アルゴリズムの問題を解くときはそれらの計算量も意識する必要があるかもしれません。
解答のコードは if 文や for ループ等、言語の基本的な機能しか使わないケースがほとんどです。まずは PHP で始めてみて、慣れてきたら他の言語でも解いてみる、というのも良いかもしれません。
インフィニットループでは、技術に熱意のあるエンジニアを募集しています。詳しくはこちらの求人詳細をご覧ください　→　採用情報ページ（仙台支社特設ページはこちら）