array_diff と PHP 配列トラバーサルを実装する他の方法との違い

それぞれ 5000 要素を持つ 2 つの配列を与え、それらの差を計算します。端的に言えば、array_diff アルゴリズムを実装するのに最適だと思われるアルゴリズムを PHP を使用することを意味します。

初めてこの質問を受け取ったとき、とても簡単だと思ったので、過去の経験に基づいて質問を書きました:

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 はキーが配列内に存在するかどうかを判断するだけです。配列のキーと値のさまざまな組織的なインデックス付け方法と組み合わせると、効率が想像よりも高いことがよくわかります。

以上がarray_diff と PHP 配列トラバーサルを実装する他の方法との違いの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。