単調配列array_diffの最適化について

簡単なarray_diffの検証用プログラム。

皆さんご存知の通りphpにはarray_diffという引数指定した配列の差分だけを抽出する関数が備え付けであります。
このarray_diffは配列が保持する値を比較します。

機能的にはこれで十分要件を満たしてくれている場合が多いと思います。

なんですが単調配列（連想配列ではない、オートインクリメントなインデックスによって保存される配列という意味で）においては
これをarray_diff_keyとarray_flipを用いた処理に置き換えることができ、その処理速度について検討します。

早速ですが簡単なテスト用のプログラムを用意

ここでは100個の要素を持つ配列と、5この要素を持つ配列の差分を抽出します。

if (!isset($argv[1])) {
  echo 'usage -- php profile.php {try_count}' . PHP_EOL;
}
$count = intval($argv[1]);

$array1 = array(100,200,300,400,500,600,700,800,900,1000,1100,1200,1300,1400,1500,1600,1700,1800,1900,2000,2100,2200,2300,2400,2500,2600,2700,2800,2900,3000,3100,3200,3300,3400,3500,3600,3700,3800,3900,4000,4100,4200,4300,4400,4500,4600,4700,4800,4900,5000,5100,5200,5300,5400,5500,5600,5700,5800,5900,6000,6100,6200,6300,6400,6500,6600,6700,6800,6900,7000,7100,7200,7300,7400,7500,7600,7700,7800,7900,8000,8100,8200,8300,8400,8500,8600,8700,8800,8900,9000,9100,9200,9300,9400,9500,9600,9700,9800,9900,10000);
$array2 = array(100,200,300,400,500);

$start = microtime(true);
for($i=0; $i<$count; $i++) {
  $array = array_diff($array1, $array2);
}
$end = microtime(true);
var_dump($end - $start);

$start = microtime(true);
for($i=0; $i<$count; $i++) {
  $array = array_diff_key(array_flip($array1), array_flip($array2));
}
$end = microtime(true);
var_dump($end - $start);

で結果。10000回試行してみます。

php profile.php 10000
float(1.888808965683)
float(0.19536399841309)

すごい差ですね。
array_flipのコストなんか関係なしにarray_diff_keyのほうが高速に参照できていることがわかります。

ここまで来ると実装内部まで気になりますね。また暇を見つけて掲載できればなと思います。

予想としては、ソートに最適化されたキー構造があるためやはりキーを下に検索すると早い。
値の比較では、全キーに関して値を走査する必要が有るため、単純に総当り、ということになるんでしょう。
件数が多ければ多いほど爆発的な違いなってくることが予想できます。

単調な配列のdiffに関してはarray_diff_keyを利用すると良さそうですね。