今朝の 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 倍ほど遅いようです。やはり、むやみに関数型言語の真似をしても性能は出ませんね。