PHP 陣列差集實作效能深度優化：從 O(n²) 到 O(n)

問題背景

需要實作類似 array_diff() 的功能：回傳存在於第一個陣列但不存在於第二個陣列的值（保留鍵名）。初期採用雙層迴圈暴力比對，效能極差。

三版演進歷程

版本一：雙層迴圈暴力法（O(n×m)）

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

缺點： 陣列越大，執行時間呈指數級增長。

版本二：善用 in_array() 內建函數

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()，但 in_array() 內部仍為線性搜尋。

版本三：array_flip() + isset() 鍵值交換法（O(n+m)）

function array_diff($array_1, $array_2) {
    $array_2 = array_flip($array_2); // 值轉鍵，建立雜湊索引
    foreach ($array_1 as $key => $item) {
        if (isset($array_2[$item])) { // O(1) 雜湊查找
            unset($array_1[$key]);
        }
    }
    return $array_1;
}

效能原理深度解析

為何 isset($array_2[$item]) 極快？

• PHP 陣列底層為有序雜湊表，鍵名經過雜湊索引，查找複雜度接近 O(1)。
• 值無索引，只能線性遍歷比對。
• array_flip() 將「值」轉為「鍵」，一次性建立索引，後續查找即為雜湊查找。

完整效能測試程式碼

<?php
function microtime_float() {
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}

// 版本一
function array_diff2($array_1, $array_2) { ... }
// 版本二
function array_diff3($array_1, $array_2) { ... }
// 版本三
function array_diff4($array_1, $array_2) { ... }

// 產生測試資料
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 "版本一 運行 " . (microtime_float() - $time_start) . " 秒\n";

$time_start = microtime_float();
array_diff3($ary_1, $ary_2);
echo "版本二 運行 " . (microtime_float() - $time_start) . " 秒\n";

$time_start = microtime_float();
array_diff4($ary_1, $ary_2);
echo "版本三 運行 " . (microtime_float() - $time_start) . " 秒\n";
?>

實務應用啟示

• 需頻繁「以值查找」時，優先考慮 array_flip() 建立反向索引。
• 大量資料去重、差集、交集運算，善用鍵值特性可獲數量級效能提升。
• 內建函數雖方便，但理解底層資料結構才能寫出高效能代碼。