PHPでは配列ではなくオブジェクトに状態を持たせよ

アドベントカレンダーを書いたらコメントに面白い課題もらいました。

「Python - すごく簡単なアルゴリズムがphpで書けなくてつらい」のやつ。

id:methane

php の array と参照の関係がクソで無いなら、 http://qiita.com/methane/items/41e1376c41d8c15e8894 これを普通に書いてみてください。

id:tanakahisateru

面白そう。やりましょう。

最近ずいぶんPHP成分多めですが、実はPythonも好物なのでホクホクです。

といっても、あのエントリーは「php の array と参照の関係がクソで無い」とは言ってなくて、むしろ逆にそこは腐ってるから避けろ、オブジェクトで囲んでやれ、という話だったので...(^^ そのままやってもPythonの性能にはならないとわかっているので、配列を直接使うのはイヤです。なので、オブジェクトが状態を持つように書けという主張がどういうことなのか、実装で表してみたいと思います。

あ、5.5 の yield 使ってます。せっかく PHP にも Python のあれができたので。 yield なんてズルいと思う人はそういうイテレータークラスを実装したらいいと思います。イテレーターの実装が面倒な人は Ginq とか検討してもいいかもです。

<?php
/**
 * 末尾から消化できるシーケンス
 */
class TailConsumableSequence
{
    protected $sequence;

    function __construct($source)
    {
        $this->sequence = $source;
    }

    /**
     * Pythonのpopと同じようなもの
     * 末尾からゆらぎぶんさかのぼって抜き出す
     */
    function consume($fluctuation=0)
    {
        $size = count($this->sequence);
        $targetPos = $size - 1 - $fluctuation;
        $consumedValue = $this->sequence[$targetPos];
        for ($i = $targetPos; $i < $size - 1; ++$i) {
            $this->sequence[$i] = $this->sequence[$i + 1];
        }
        array_pop($this->sequence);
        return $consumedValue;
    }

    /**
     * n以上残っているか
     */
    function remainsEqualsOrMoreThan($n)
    {
        return count($this->sequence) >= $n;
    }

    /**
     * 残り数かlimitかどちらか小さい方
     */
    function sizeOr($limit)
    {
        $size = count($this->sequence);
        return min($limit, $size);
    }
}

/**
 * 数列の後ろのほうからごにょごにょ拾ってきてペアを作る
 * ごにょごにょ = 最末尾とそこから limit までの範囲さかのぼった位置のペア
 */
function allRandomPeairsFrom($sequence, $limit=100)
{
    $tcs = new TailConsumableSequence($sequence);
    while ($tcs->remainsEqualsOrMoreThan(2)) {
        $a = $tcs->consume(); // 最末尾から取る
        $b = $tcs->consume(
            mt_rand(0, $tcs->sizeOr($limit) - 1)
        ); // 最末尾からある程度さかのぼって取る
        yield [$a, $b];
    }
}

function test($n, $r) {
    foreach (allRandomPeairsFrom(range(0, $n-1), $r) as list($a, $b)) {
        //printf("%d %d\n", $a, $b);
        assert($a - $b < $r * 2);
    }
}

test($argv[1], 10);

これでいかがでしょうか。追記3のベタ書きと同じような特性なのに、わりと読めるコードでもあります。

$ time php matching2.php 10000; time php matching2.php 20000
php matching2.php 10000  0.23s user 0.01s system 99% cpu 0.245 total
php matching2.php 20000  0.40s user 0.02s system 98% cpu 0.421 total

追記2 で list_pop() にしていた処理をベタ書きしたら、やっと予想通りの性能が出るようになった。 php で配列の参照に対して操作してはいけない。つまり、配列を操作するアルゴリズムを関数にしてはいけない。

すごく同意。関数にしてはいけない。配列の参照に対して操作してはいけない。生で配列をごりごり書き換えるとポインタが使えないためにリファクタできなくなってハマる。じゃあどうするか...

PHPで状態を持つバッファは、オブジェクトで囲むといいです。参照渡しとか配列のコピーとかから来るややこしさから解放され、ベタ書きしたのと同じような動きになります。オブジェクトはポインタなので、好きなだけ関数に渡してもよくて、もっといいのは、オブジェクトのフィールドはスコープを行き来するローカル変数より、もっと安定したメモリに置いてあるってことです。

あの「状態の変化は、それを意図したメソッドを持つオブジェクトでのみ起こるべきです。」というのは、お作法の話であるという側面もあるけど、他に、そう書いたほうが参照渡しよりも問題が簡単になって、がんばらなくてもパフォーマンスが安定する、という意味でもあるんです。

まわりくどくて重厚に見える方法のほうが実は素直、というのが最近のPHPの面白いところです。OOPのお作法がよくなるのと、物理的に悪いものから遠ざかるのが反比例じゃない感じ。

PHPのarrayはPythonでいうところの名前付きタプルとして使うぐらいが、いちばんいい使い方だと思っています。