給你兩個分別有 5000 個元素的數(shù)組，計算他們的差集
-- 說白了也就是用 PHP 和你認(rèn)為最好的算法實現(xiàn) array_diff 的算法。
初次接到這個題目，我發(fā)現(xiàn)這非常的簡單，于是按照以往的經(jīng)驗“隨便”寫了一個：
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;
}
雖然實現(xiàn)是可以的，但是發(fā)現(xiàn)這個函數(shù)的效率是慘不忍睹。于是我又重新考慮了下，并優(yōu)化了算法，第二個函數(shù)看起來是這個樣子的：
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 函數(shù)的速度媲美了。但是還有沒有更優(yōu)化的辦法呢？由 ChinaUnix 上的[url=http://bbs.chinaunix.net/viewthread.php?tid=938096]一篇文章（不好意思，作弊了），我發(fā)現(xiàn) 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;
}
這個函數(shù)的效率非常的驚人，甚至比原 array_diff 函數(shù)的速度都要快。究其原因，我找到了解釋：
因為鍵是進(jìn)行 HASH 組織的，查找很快；
而 Value 只是由 Key 組織存放，本身沒有索引，每次查找都是遍歷。
總結(jié)
這雖然是 PHP 語言的一個小竅門，但在遍歷和對比數(shù)組的值上，如果需要對比值將其與鍵反轉(zhuǎn)的確比通常的值對值的比較效率要高得多。
比如，上面的函數(shù)二需要調(diào)用 in_array 函數(shù)需要循環(huán)判斷是否在函數(shù)內(nèi)；而函數(shù)三則僅僅判斷這個數(shù)組是否存在該鍵就可以了。
加上數(shù)組鍵和值不同的組織索引方式，效率比想象的還高那就非?？梢岳斫饬恕?/span>
本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點擊舉報。
