PHP におけるいくつかの差分セットメソッドとパフォーマンス比較

プログラミングでは、指定された 2 つの配列の差を取るなど、常に何らかのデータを処理する必要があります。実装方法はたくさんありますが、どの方法が差分セットを見つけるパフォーマンスが良いでしょうか?今日は、差分セットを見つける例と、コードのパフォーマンスを最適化する方法を共有します。

質問は次のとおりです。それぞれ 5000 要素を持つ 2 つの配列が与えられ、それらの差集合を計算します。率直に言うと、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 はキーが配列内に存在するかどうかを判断するだけです。配列のキーと値のさまざまな組織的なインデックス付け方法と組み合わせると、効率が想像よりも高いことがよくわかります。

<?php 
function microtime_float() { 
    list($usec, $sec) = explode(" ", microtime()); 
    return ((float)$usec + (float)$sec); 
} 
function array_diff2($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; 
} 
function array_diff3($array_1, $array_2) { 
    foreach ($array_1 as $key => $item) { 
        if (in_array($item, $array_2, true)) { 
            unset($array_1[$key]); 
        } 
    } 
    return $array_1; 
} 
function array_diff4($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; 
} 
////////////////////////////// 
for($i = 0, $ary_1 = array(); $i < 5000; $i++) { 
    $ary_1[] = rand(100, 999); 
} 
for($i = 0, $ary_2 = array(); $i < 5000; $i++) { 
    $ary_2[] = rand(100, 999); 
} 
header("Content-type: text/plain;charset=utf-8"); 
$time_start = microtime_float(); 
array_diff($ary_1, $ary_2); 
echo "函数 array_diff 运行" . (microtime_float() - $time_start) . " 秒\n"; 
$time_start = microtime_float(); 
array_diff2($ary_1, $ary_2); 
echo "函数 array_diff2 运行" . (microtime_float() - $time_start) . " 秒\n"; 
$time_start = microtime_float(); 
array_diff3($ary_1, $ary_2); 
echo "函数 array_diff3 运行" . (microtime_float() - $time_start) . " 秒\n"; 
$time_start = microtime_float(); 
array_diff4($ary_1, $ary_2); 
echo "函数 array_diff4 运行" . (microtime_float() - $time_start) . " 秒\n"; 
?>

関連する推奨事項:

array_chunk() を使用せずに配列を分割する php アルゴリズム_PHP チュートリアル

配列の和集合、交差関数、差分関数

概要PHP配列ソート方法の説明

以上がPHP におけるいくつかの差分セットメソッドとパフォーマンス比較の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。