【原創(chuàng)】深思 PHP 數(shù)組遍歷的差異（array_diff 的實(shí)現(xiàn)）

AMD-K6

原文鏈接： http://www.gracecode.com/Archive/Display/421

還是部門無聊的考題，不過這次考的是 PHP 的能力。題目如下：

給你兩個(gè)分別有 5000 個(gè)元素的數(shù)組，計(jì)算他們的差集
  -- 說白了也就是用 PHP 和你認(rèn)為最好的算法實(shí)現(xiàn) array_diff 的算法。

初次接到這個(gè)題目，我發(fā)現(xiàn)這非常的簡(jiǎn)單，于是按照以往的經(jīng)驗(yàn)“隨便”寫了一個(gè)：

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

雖然實(shí)現(xiàn)是可以的，但是發(fā)現(xiàn)這個(gè)函數(shù)的效率是慘不忍睹。于是我又重新考慮了下，并優(yōu)化了算法，第二個(gè)函數(shù)看起來是這個(gè)樣子的：


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 上的一篇文章（不好意思，作弊了），我發(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;
}

這個(gè)函數(shù)的效率非常的驚人，甚至比原 array_diff 函數(shù)的速度都要快。究其原因，我找到了解釋：

因?yàn)殒I是進(jìn)行 HASH 組織的，查找很快；
而 Value 只是由 Key 組織存放，本身沒有索引，每次查找都是遍歷。

總結(jié)

這雖然是 PHP 語言的一個(gè)小竅門，但在遍歷和對(duì)比數(shù)組的值上，如果需要對(duì)比值將其與鍵反轉(zhuǎn)的確比通常的值對(duì)值的比較效率要高得多。

比如，上面的函數(shù)二需要調(diào)用 in_array 函數(shù)需要循環(huán)判斷是否在函數(shù)內(nèi)；而函數(shù)三則僅僅判斷這個(gè)數(shù)組是否存在該鍵就可以了。

加上數(shù)組鍵和值不同的組織索引方式，效率比想象的還高那就非常可以理解了。

附，下載鏈接和腳本：http://www.gracecode.com/Archive/Display/421

[ 本帖最后由 AMD-K6 于 2007-12-21 12:50 編輯 ]

james.liu

看下googlechina的blog，，關(guān)于布爾的計(jì)算這塊，，，用布爾做差集和合集會(huì)很快。尤其是大量數(shù)據(jù)

powerpolly

明顯地，isset比in_array開銷小:wink:

myaxl2008

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

手冊(cè)上關(guān)于array_diff例子如下:

1. 
   
2. <?php
   
3. $array1 = array("a" => "green", "red", "blue", "red");
   
4. $array2 = array("b" => "green", "yellow", "red");
   
5. $result = array_diff($array1, $array2);
   
6. 
   
7. print_r($result);
   
8. ?>
   
9. 
   
10. 在 $array1 中多次出現(xiàn)的值一樣處理，輸出結(jié)果為：
    
11. 
    
12. Array
    
13. (
    
14.     [1] => blue
    
15. )
    

復(fù)制代碼

LZ所寫的情況和此函數(shù)好像不太一樣,如果兩數(shù)組的Key不一樣,值不一樣的話,所謂的比原array_diff快是沒法對(duì)比的吧.應(yīng)該和array_diff_key對(duì)比下性能.

平時(shí)對(duì)性能研究很少,分析的有問題請(qǐng)路過飄過的大俠們指點(diǎn)一二.

[ 本帖最后由 myaxl2008 于 2007-12-24 14:05 編輯 ]

goshawk

Aryang

能不能把兩種方法差別的數(shù)據(jù)列出來？

courage121

差距很大，當(dāng)兩個(gè)數(shù)組都是5000的時(shí)候應(yīng)該還能顯示出結(jié)果，但是如果兩個(gè)數(shù)組都是10000的話頁面應(yīng)該執(zhí)行到一半就顯示不出來了

ydlhero

不錯(cuò)的對(duì)比,平時(shí)很少 去做對(duì)比

myaxl2008

功能都不一樣如何做對(duì)比.......

wnpers

學(xué)習(xí)

[ 本帖最后由 wnpers 于 2007-12-26 15:51 編輯 ]