in_arrayとarray_flip+array_key_existsの比較3

PHP Benchmark

以前こう書いた。

だめ、全然だめ。array_flipが遅い（そりゃそうだ）。

同じ配列の値を数10回以上検索するのならやる価値はあるだろうが、そのときもneedleを配列にして一度にin_arrayで検索した方が速い。

今度は Pear::Benchmark (Benchmark/Iterate.php) を使ってみようかな。

in_arrayとarray_flip+array_key_existsの比較 - ”improve it!”

これがarray_flip()ってこう使うのか・・・！！！ - ぐらめぬ・ぜぷつぇんのはてダ(2007 to 2011)で引用されてた！やった！

・・・え。マジ？ Σ（ﾟдﾟlll）

array_flip()ってこう使うのか・・・！！！ - ぐらめぬ・ぜぷつぇんのはてダ(2007 to 2011)

ちゃんと検証内容を書いておけばよかったorz
in_arrayとarray_flip+array_key_existsの比較 - ”improve it!”はその一つ前のarray_searchとin_arrayの比較2 - ”improve it!”の続きで

array_flipとarray_key_existsをつかったらどうなるのかな。

array_searchとin_arrayの比較2 - ”improve it!”

と書いたことを試してみたものでした。ただあんまりにも残念な結果だったので書く気力がなかったんです。あと、実は間違ったことを書いています。

間違いを訂正して、array_flip()ってこう使うのか・・・！！！ - ぐらめぬ・ぜぷつぇんのはてダ(2007 to 2011)のソースを流用して同じ配列の値を数10回以上検索するのならやる価値はあるを検証しようと思います。

訂正

needleを配列にして一度にin_arrayで検索した方が速い。と書いていますが、これは間違いです。
needleが配列のときにはその配列の要素で検索してくれるものと勘違いしていました。すみません。

in_array($needle, $haystack)で$needleが配列の場合と言うのは、あくまで$haystackの要素に$needleという配列があるかどうかを調べるものです。決して$haystackの要素に$needleという配列の要素があるかどうかを調べるものではないのでした。

array_flip()ってこう使うのか・・・！！！ - ぐらめぬ・ぜぷつぇんのはてダ(2007 to 2011)のベンチマーク結果

array_flip()ってこう使うのか・・・！！！ - ぐらめぬ・ぜぷつぇんのはてダ(2007 to 2011)のベンチマークを実行すると以下の結果が得られました（見やすさのために少々改変しています）。

in_array (array_flip_benchmark01.php)
Average :      0.1278607

array_flip + isset(array_flip_benchmark02.php)
Average : 
array_flip() : 0.01304
hit          : 0.0003866
total        : 0.0134266

array_flip + array_key_exists (array_flip_benchmark03.php)
Average : 
array_flip() : 0.0142595
hit          : 0.0003707
total        : 0.0146302

一見array_flipをした方が効果が絶大に見えますが、よくみるとarray_flipを使った場合、totalのうちほとんどがarray_flip()に費やされていることがわかります。どのようなベンチマークを行ったのでしょうか。

in_arrayをarray_flipを使ったものに置き換える

array_flip_benchmark02.phpの繰り返し部分は以下のようになっています。

for ($k = 0; $k < 10; $k++) {
    $t1->start();
    $arr2 = array_flip($arr1);
    $t1->setMarker('m1');
    for ($i = 0; $i < 100; $i++) {
        $needle = mt_rand(1, $sz);
        $d = isset($arr2[$needle]);
    }
    $t1->stop();
    $elapsed[] = array(
        'array_flip' => $t1->timeElapsed('Start', 'm1'),
        'hit' => $t1->timeElapsed('m1', 'Stop'),
        'total' => $t1->timeElapsed('Start', 'Stop'),
        );
}

array_flip_benchmark03.phpは以下のとおりです。

for ($k = 0; $k < 10; $k++) {
    $t1->start();
    $arr2 = array_flip($arr1);
    $t1->setMarker('m1');
    for ($i = 0; $i < 100; $i++) {
        $needle = mt_rand(1, $sz);
        array_key_exists($needle, $arr2);
    }
    $t1->stop();
    $elapsed[] = array(
        'array_flip' => $t1->timeElapsed('Start', 'm1'),
        'hit' => $t1->timeElapsed('m1', 'Stop'),
        'total' => $t1->timeElapsed('Start', 'Stop'),
        );
}

array_flipをかけた配列（この場合は$arr2）に対して、in_arrayやarray_key_existsを100回行っています（そしてこの操作を10回行って所要時間の平均を取っています）。これは前回書いた同じ配列の値を数10回以上検索するのならといった状況に他なりません。

しかしこのように同じ配列に対して何度も検索をかけるといった状況はそうあるものでしょうか？
実際のソース中のin_arrayをarray_flipを使ったものに置き換えることを考えるとこのソースは不自然です。
実際に置き換えるとすると

in_array($needle, $haystack)

を

$haystack = array_flip($haystack);
isset($haystack[$needle]);

とすることになるでしょう。すると、array_flip_benchmark02.php、array_flip_benchmark03.phpの繰り返し部分は以下のようにすべきです。

array_flip_benchmark02.php

for ($k = 0; $k < 10; $k++) {
    $t1->start();
    $arr2 = array_flip($arr1);
    $t1->setMarker('m1');
    $needle = mt_rand(1, $sz);
    $d = isset($arr2[$needle]);
    $t1->stop();
    $elapsed[] = array(
        'array_flip' => $t1->timeElapsed('Start', 'm1'),
        'hit' => $t1->timeElapsed('m1', 'Stop'),
        'total' => $t1->timeElapsed('Start', 'Stop'),
        );
}

array_flip_benchmark03.php

for ($k = 0; $k < 10; $k++) {
    $t1->start();
    $arr2 = array_flip($arr1);
    $t1->setMarker('m1');
    $needle = mt_rand(1, $sz);
    array_key_exists($needle, $arr2);
    $t1->stop();
    $elapsed[] = array(
        'array_flip' => $t1->timeElapsed('Start', 'm1'),
        'hit' => $t1->timeElapsed('m1', 'Stop'),
        'total' => $t1->timeElapsed('Start', 'Stop'),
        );
}

条件を同じにするためarray_flip_benchmark01.phpも以下のように変更します。

for ($k = 0; $k < 10; $k++) {
    $t1->start();
    $needle = mt_rand(1, $sz);;
    in_array($needle, $arr1);
    $t1->stop();
    $elapsed[] = $t1->timeElapsed('Start', 'Stop');
}

これらの結果は以下のとおりです（見やすさのために少々改変しています）。

in_array
Average :        0.0013903379440308

array_flip + isset
Average : 
  array_flip() : 0.014025068283081
  hit          : 5.0926208496094E-05
  total        : 0.014075994491577

array_flip + array_key_exists
Average : 
  array_flip() : 0.014245533943176
  hit          : 3.7860870361328E-05
  total        : 0.014283394813538

array_flipを使うことで10倍の時間がかかっていることがわかります。array_flipは結構コストがかかるんですね。

array_flipはなかなかのコストがかかることがわかりました。それでも、同じ配列を何度も検索するという状況でin_arrayのコストが大きくなり、array_flipのコストを上回るなら、arrya_flip + issetをやる価値はあると思います。それがarray_flip()ってこう使うのか・・・！！！ - ぐらめぬ・ぜぷつぇんのはてダ(2007 to 2011)のベンチマーク結果で示されていることです。

以上が

同じ配列の値を数10回以上検索するのならやる価値はあるだろうが、そのときもneedleを配列にして一度にin_arrayで検索した方が速い。

http://d.hatena.ne.jp/uunfo/20070225/1172425825

と書いたことの前半同じ配列の値を数10回以上検索するのならやる価値はあるの意味です。

余談: はじめからハッシュを使えばいいのでは？

array_flipのコストが高いことがわかりました。それならはじめからそんなのを使わないようにすればいいんです。つまりはじめからハッシュのキーに値を保存しておけばいいのです。

array_flip_benchmark02.php、array_flip_benchmark03.phpの$arr1を生成する箇所を以下のように変更します。

for ($i = 0; $i < $sz; $i++) {
    $arr1[mt_rand(1, $sz)] = 1;
}
//shuffle($arr1);
//shuffle($arr1);

そしてarray_flipの箇所をコメントアウトしたり、Benchmark関連の箇所も削除します。
issetやarray_key_existsで$arr1の値を使うように変更します。

        $d = isset($arr1[$needle]);

        array_key_exists($needle, $arr1);

この結果は以下のとおりです。

Average : 
isset : 0.0001126766204834
Average : 
array_key_exists : 0.00013687610626221

わかってはいましたが圧倒的な速さですね。

ソースは以下のとおりです。
issetの場合

<?php
require_once('Benchmark/Timer.php');

$sz = 10000;

$arr1 = array();
for ($i = 0; $i < $sz; $i++) {
    $arr1[mt_rand(1, $sz)] = 1;
}

$t1 =& new Benchmark_Timer();
$elapsed = array();
for ($k = 0; $k < 10; $k++) {
    $t1->start();
    for ($i = 0; $i < 100; $i++) {
        $needle = mt_rand(1, $sz);
        $d = isset($arr1[$needle]);
    }
    $t1->stop();
    $elapsed[] = array(
        'total' => $t1->timeElapsed('Start', 'Stop'),
        );
}

$sum_total = 0;
foreach ($elapsed as $el) {
    $sum_total += $el['total'];
    echo $el['total'] . PHP_EOL;
}
echo "-----------".PHP_EOL;
echo "Average : ".PHP_EOL;
echo "\tisset : " . $sum_total / 10 . PHP_EOL;

array_key_existsの場合

<?php
require_once('Benchmark/Timer.php');

$sz = 10000;

$arr1 = array();
for ($i = 0; $i < $sz; $i++) {
    $arr1[mt_rand(1, $sz)];
}

$t1 =& new Benchmark_Timer();
$elapsed = array();
for ($k = 0; $k < 10; $k++) {
    $t1->start();
    for ($i = 0; $i < 100; $i++) {
        $needle = mt_rand(1, $sz);
        array_key_exists($needle, $arr1);
    }
    $t1->stop();
    $elapsed[] = array(
        'total' => $t1->timeElapsed('Start', 'Stop'),
        );
}

$sum_total = 0;
foreach ($elapsed as $el) {
    $sum_total += $el['total'];
    echo $el['total'] . PHP_EOL;
}
echo "-----------".PHP_EOL;
echo "Average : ".PHP_EOL;
echo "\tarray_key_exists : " . $sum_total / 10 . PHP_EOL;

余談2: array_keysとarray_flipの比較

配列をわざわざarray_flipにかけてからarray_key_existsを使うよりは、はじめからハッシュのキーに値を保存しておけばいいことがわかりました。

でも配列に値が入っているほうが何かと便利なはずです。ハッシュのキーとして保存しておくなんて検索以外に使い道がありません。

そこでarray_keysの登場です。array_flipは配列の値をキーにするハッシュを生成するものでしたが、array_keysはその反対にハッシュのキーを値にもつ配列を生成します。

array_keysはarray_flipよりもずっと高速です。

Average : 
        array_keys : 0.020076489448547
Average : 
        array_flip : 0.18704025745392

ハッシュのキー + array_keys でいろいろ幸せになれそうな予感がします。

array_keys.php

<?php
require_once('Benchmark/Timer.php');

$sz = 10000;

$arr1 = array();
for ($i = 0; $i < $sz; $i++) {
    $arr1[mt_rand(1, $sz)] = 1;
}

$t1 =& new Benchmark_Timer();
$elapsed = array();
for ($k = 0; $k < 10; $k++) {
    $t1->start();
    for ($i = 0; $i < 10; $i++) {
        array_keys($arr1);
    }
    $t1->stop();
    $elapsed[] = array(
        'array_keys' => $t1->timeElapsed('Start', 'Stop'),
        );
}

$sum_array_keys = 0;
foreach ($elapsed as $el) {
    $sum_array_keys += $el['array_keys'];
    echo $el['array_keys'] . PHP_EOL;
}
echo "-----------".PHP_EOL;
echo "Average : ".PHP_EOL;
echo "\tarray_keys : " . $sum_array_keys / 10 . PHP_EOL;

array_flip.php

<?php
require_once('Benchmark/Timer.php');

$sz = 10000;

$arr2 = array();
for ($i = 0; $i < $sz; $i++) {
    $arr2[] = mt_rand(1, $sz);
}

$t1 =& new Benchmark_Timer();
$elapsed = array();
for ($k = 0; $k < 10; $k++) {
    $t1->start();
    for ($i = 0; $i < 10; $i++) {
        array_flip($arr2);
    }
    $t1->stop();
    $elapsed[] = array(
        'array_flip' => $t1->timeElapsed('Start', 'Stop'),
        );
}

$sum_array_keys = 0;
$sum_array_flip = 0;
foreach ($elapsed as $el) {
    $sum_array_flip += $el['array_flip'];
    echo $el['array_flip'] . PHP_EOL;
}
echo "-----------".PHP_EOL;
echo "Average : ".PHP_EOL;
echo "\tarray_flip : " . $sum_array_flip / 10 . PHP_EOL;