.NET 遺忘錄（三）：Array 與 List 效能抉擇——從洗牌演算法看資料結構本質

同事用 List<int> 實作洗牌演算法（Fisher-Yates），執著認為「泛型較先進」。實測證明：頻繁隨機索引存取場景，陣列完勝 List。本文從記憶體模型、IL 指令、演算法複雜度三維度剖析。

記憶體佈局本質差異

IL 級證據：索引存取指令對比

// Array: a[3]
IL_0020: ldloc.0      // 載入陣列引用
IL_0021: ldc.i4.3     // 載入索引 3
IL_0022: ldelem.i4    // 直接取值

// List: list[3]
IL_0022: ldloc.0      // 載入 List 引用
IL_0023: ldc.i4.3     // 載入索引 3
IL_0024: callvirt instance !0 class [mscorlib]System.Collections.Generic.List`1<int32>::get_Item(int32)
IL_0029: stloc.2

List 多一個 callvirt 呼叫 get_Item，雖然 JIT 可能內聯，但調試版本/未優化情境下確有呼叫開銷。

洗牌演算法實測場景

// 100 次隨機交換，每次 2 次讀 + 2 次寫 = 400 次索引操作
for (int j = 0; j < 100; j++) {
    int x1 = r.Next(10), x2 = r.Next(10);
    Swap(ref arr[x1], ref arr[x2]); // 陣列版
    Swap(ref list[x1], ref list[x2]); // List 版
}

陣列版：零方法呼叫、零邊界檢查（JIT 優化後）、最佳快取局部性。
List 版：每次存取觸發 get_Item/set_Item，含邊界檢查、版本號檢查（_version 防止枚舉器失效）。

插入/刪除：List 的真正優勢場景

• 尾端新增：List.Add 攤銷 O(1)，陣列需手動擴容複製
• 中間插入/刪除：兩者皆 O(n) 位移元素，但 List 封裝 Array.Copy 更便利
• 已知節點前插入：LinkedList O(1)，Array/List 均 O(n)

決策矩陣

結語

「泛型較先進」是危險的迷思。資料結構選擇取決於存取模式，而非語法糖衣。洗牌演算法核心是隨機索引交換，陣列是天然最優解。工程師的價值，在於透過記憶體模型與 IL 看穿封裝本質，做出理性選擇。