今朝の array_reduce の実行速度
今朝の記事に書いた複数配列を取れる array_reduce ですが、これは全然駄目ですね。関数型言語でのリスト操作のような感覚で array_merge や array_shift を使ってしまっているので、パフォーマンスが悪すぎです。
こんなコードを使って実行時間を計測してみました。1 から N までの二乗和を計算するものです。
<?php $vec1 = range(1, $argv[1]); $vec2 = range(1, $argv[1]); $result = my_array_reduce(function($acc, $x, $y) { return $acc + $x * $y; }, 0, $vec1, $vec2);
5 回の実行時間の合計を計測してみました。test.php は前回の記事で定義した my_array_reduce 関数と上記のコードを書いた PHP ファイルだとします。
$ time (for i in `seq 1 5`; do php test.php 10000; done) >/dev/null real 0m8.554s user 0m8.480s sys 0m0.040s
my_array_reduce の while ループ部分を以下のように書き換えるだけで、20 倍以上速くなりました。
<?php ... for ($i = 0; $i < count($args[0]); $i++) { $result = call_user_func_array( $func, array_merge( array($result), array_map(function ($a) use ($i) { return $a[$i]; }, $args))); }
これで real 0m0.300s, user 0m0.259s, sys 0m0.034s でした。
そもそも、普通にループで書けばこのようになると思います。
<?php ... $result = 0; for ($i = 0; $i < count($vec1); $i++) { $result += $vec1[$i] * $vec2[$i]; }
このコードは N = 100000, i = 1..10 の設定で user 0m0.608s になりました。一方、この設定で先ほどの (高速化した方の) my_array_reduce 版を実行したところ user 0m3.535s となり、5 倍程度の差があります。
PHP の array_map と array_reduce を使って書くとどうなるでしょうか。
<?php ... $reuslt = array_reduce(array_map(function ($x, $y) { return $x * $y; }, $vec1, $vec2), function($r, $i) { return $r + $i; }, 0);
このコードで user 0m1.146s でした。array_map で配列を余分に allocate するためでしょうか。ループで書いた場合に比べて 2 倍ほど遅いようです。やはり、むやみに関数型言語の真似をしても性能は出ませんね。