JavaScript 多陣列找出重複元素：高效能演算法與效能測試

問題定義

給定多個陣列，找出 至少在兩個陣列中出現 的元素。單一陣列內保證無重複。關鍵挑戰：大資料量下的時間與空間效能。

核心演算法：雜湊表計數法

function findDuplicates(...arrays) {
    const count = new Map(); // 元素 -> 出現陣列數
    const result = [];
    
    for (const arr of arrays) {
        const seen = new Set(); // 防止同一陣列重複計數 (題目保證無重，但防禦性保留)
        for (const val of arr) {
            if (seen.has(val)) continue;
            seen.add(val);
            const c = (count.get(val) || 0) + 1;
            count.set(val, c);
            if (c === 2) result.push(val); // ちょうど2個陣列出現即加入
        }
    }
    return result;
}

複雜度：時間 O(N)，空間 O(U) (U = 所有唯一元素總數)。

完整可執行測試程式碼

<!DOCTYPE html>
<html><head><meta charset="UTF-8"><title>多陣列重複元素測試</title></head><body>
<script>
// 高精度計時
function timeIt(fn) {
    const start = performance.now();
    const ret = fn();
    const end = performance.now();
    return {ret, time: (end - start).toFixed(2) + 'ms'};
}

// 產生固定範圍、隨機順序陣列
function genRange(min, max) {
    const arr = [];
    for (let i = min; i <= max; i++) arr.push(i);
    // Fisher-Yates 洗牌
    for (let i = arr.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr;
}

// 產生隨機不重複陣列
function genRandom(min, max, count) {
    const set = new Set();
    while (set.size < count) set.add(Math.floor(Math.random() * (max - min + 1)) + min);
    return [...set];
}

// 核心函式
function getDuplicates(...arrays) {
    const count = new Map();
    const result = [];
    for (const arr of arrays) {
        for (const val of arr) {
            const c = (count.get(val) || 0) + 1;
            count.set(val, c);
            if (c === 2) result.push(val);
        }
    }
    return result;
}

// === 測試案例 ===
console.log('--- 基本測試 ---');
const a = genRange(1, 20);
const b = genRange(18, 35);
const c = genRange(34, 50);
console.log('陣列A:', a);
console.log('陣列B:', b);
console.log('陣列C:', c);
console.log('重複元素:', getDuplicates(a, b, c)); // 預期: 18,19,20, 34,35

console.log('\n--- 大量資料效能測試 ---');
// 5陣列 x 1萬 = 5萬元素
const testData5 = Array.from({length: 5}, () => genRandom(1, 1_000_000, 10_000));
console.time('5x10k');
const dup5 = getDuplicates(...testData5);
console.timeEnd('5x10k');
console.log('重複數:', dup5.length);

// 10陣列 x 1萬 = 10萬元素
const testData10 = Array.from({length: 10}, () => genRandom(1, 1_000_000, 10_000));
console.time('10x10k');
getDuplicates(...testData10);
console.timeEnd('10x10k');

// 100陣列 x 1萬 = 100萬元素
const testData100 = Array.from({length: 100}, () => genRandom(1, 1_000_000, 10_000));
console.time('100x10k');
getDuplicates(...testData100);
console.timeEnd('100x10k');
</script>
</body></html>

效能測試結果參考 (Chrome V8)

關鍵優化觀察

1. 單一 Map 計數 優於兩兩比較 (O(k²·n)) 或多重 Set 交集。
2. 陣列數多、單陣列小 效能最佳 (Map 大小 = 唯一元素總數)。
3. 單陣列過大 (10萬+) 會導致 Map 膨脹，GC 壓力增大。
4. 使用 Map 而非物件 `{}`，支援任意型別鍵值且效能更穩定。
5. 若元素為物件，需實作 toString() 或使用 WeakMap + 序列化。

進階：串流處理超大資料

若資料無法一次載入記憶體，可採用外部排序 + 歸併或分區雜湊：

// 概念：將元素按 hash 分到 N 個檔案，各檔案內部排序/去重，再歸併計數
// 適用於 TB 級日誌分析等場景

常見陷阱

• ❌ 雙層迴圈兩兩比較：O(k²·n) 指數級爆炸
• ❌ 直接 arr1.filter(x => arr2.includes(x))：includes 為 O(n)，總體 O(n²)
• ❌ 忽略單陣列內重複：導致計數偏高
• ✅ 使用 Set 去重後再計數，或如本文單次遍歷 + Map

總結

• 多陣列找重複：單次遍歷 + Map 計數 為最優解 (O(N) 時間)。
• JS 環境下 Map 效能優於物件鍵值對。
• 百萬級元素約 300ms 內完成，滿足多數前端/Node.js 場景。
• 資料量超過記憶體限制時，需轉向外部排序或分布式框架 (Spark/Flink)。