優化筆記：C# 從 List<T> 移除空元素

需求

我們有時候需要延遲刪除 List<T> 中的元素，那時候會先把元素設為 null，最後才一次移除所有空元素。

優化前

static void RemoveNull<T>(List<T> list) {n for (int i = list.Count - 1; i >= 0; i--)n if (list[i] == null)n list.RemoveAt(i); // O(n)n}n

由於 RemoveAt() 是 時間的操作，整個函數是 。但這個問題只需要 時間。

優化後

只要把第一個空元素之後的非空元素往前移，就能實現。

static void RemoveNull<T>(List<T> list) {n // 找出第一個空元素 O(n)n int count = list.Count;n for (int i = 0; i < count; i++)n if (list[i] == null) {n // 記錄當前位置n int newCount = i++;nn // 對每個非空元素，複製至當前位置 O(n)n for (; i < count; i++)n if (list[i] != null)n list[newCount++] = list[i];nn // 移除多餘的元素 O(n)n list.RemoveRange(newCount, count - newCount);n break;n }n}n

List<T> 實際上也提供 RemoveAll(Predicate<T>) 的介面（參考實現），可以 完成相同工作。但在目前 Unity 的 IL2CPP 下，因 delegate 的調用成本，自行實現會稍快一些。

C++ 可用 std::remove, std::remove_if，因為支持內聯不需考慮調用成本。

（題圖 Photo by Adam Wilson）

推薦閱讀：