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;
}
}

$flag) {
$diff[$k] = $v1; 効率は驚くべきものです。そこで、アルゴリズムを再検討して最適化しました。

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

コードを添付



コードをコピー

コードは次のとおりです:

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 $ary_1[] = rand(100, 999);
}

for($i = 0, $ary_2 = array(); $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) 。 " 秒";

$time_start = microtime_float();
array_diff2($ary_1, $ary_2);
echo "関数数 array_diff2 运行" 。 (microtime_float() - $time_start) 。 " 秒";

$time_start = microtime_float();
array_diff3($ary_1, $ary_2);
echo "関数数 array_diff3 运行" 。 (microtime_float() - $time_start) 。 " 秒";

$time_start = microtime_float();
array_diff4($ary_1, $ary_2);
echo「関数数array_diff4运行」。 (microtime_float() - $time_start) 。 " 秒";
?>