PHP配列トラバーサルの差分(array_diff)実装

この質問を初めて受け取ったとき、とても簡単だったので、過去の経験に基づいて「何気なく」質問を書きました。

function array_diff($array_1, $array_2) {
$diff = array();
foreach ($array_1 as $k => $v1) {
$flag = false;
foreach ($array_2 as $v2) {
if ($flag = ( $v1 == $v2)) {
Break;
}
}
if (!$flag) {
$diff[$k] = $v1 ;
}
}
return $diff;
}

実装は可能ですが、この関数の効率は恐ろしいことがわかりました。そこで、アルゴリズムを再考して最適化しました。2 番目の関数は次のようになりました。
function array_diff($array_1, $array_2) {
foreach ($array_1 as $key => $item) {
if ( in_array($item, $array_2, true)) {
unset($array_1[$key]);
}
}

return $ array_1;
}

まあ、今回は元の array_diff 関数とほぼ同じくらい高速です。しかし、より最適化された方法はあるのでしょうか? ChinaUnix に関する記事 (ごめんなさい、騙しました) から、PHP は実際に次のように記述できることを発見しました。

function array_diff($array_1, $array_2) {
$array_2 = array_flip($array_2) ;
foreach ($array_1 as $key => $item) {
if (isset($array_2[$item])) {
unset($array_1[$key]);
}
}

return $array_1;
}

この関数の効率は驚くべきもので、元の array_diff 関数よりもさらに高速です。理由を調査すると、次のような説明が見つかりました。

キーは HASH によって編成されているため、検索は非常に高速です。
値はキー編成にのみ格納され、各検索自体にはインデックスがありません。横断しました。

まとめ

これはPHP言語の小技ですが、配列の値を走査して比較する際に、値を比較する必要がある場合はキーで反転するのが良いです。実際、通常の値対値よりも優れており、比較効率がはるかに高くなります。

たとえば、上記の関数 2 は in_array 関数を呼び出し、それが関数内にあるかどうかを判断するためにループする必要がありますが、関数 3 はキーが配列内に存在するかどうかを判断するだけです。

配列のキーと値のさまざまな組織的なインデックス付け方法と組み合わせると、効率が想像よりも高いことがよくわかります。