c# - LINQ 中的 "RemoveAll"怎么可能比迭代快得多？

Question

以下代码:

List<Interval> intervals = new List<Interval>();
List<int> points = new List<int>();

//Initialization of the two lists
// [...]

foreach (var point in points)
{
    intervals.RemoveAll (x => x.Intersects (point));
}

当列表的大小为 ~10000 时，至少比这快 100 倍:

List<Interval> intervals = new List<Interval>();
List<int> points = new List<int>();

//Initialization of the two lists
// [...]

foreach (var point in points)
{
    for (int i = 0; i < intervals.Count;)
    {
        if (intervals[i].Intersects(point))
        {
            intervals.Remove(intervals[i]);
        }
        else
        {
            i++;
        }
    }
}

这怎么可能？ “RemoveAll”在幕后执行了什么？根据MSDN , "RemoveAll"执行线性搜索，因此在 O(n) 中。所以我希望两者的性能相似。

用“RemoveAt”替换“Remove”时，迭代速度快得多，与“RemoveAll”相当。但是“Remove”和“RemoveAt”的复杂度都是O(n)，为什么它们的性能差异这么大呢？难道仅仅是因为“Remove (item)”将列表元素与“item”进行比较，而“RemoveAt”不执行任何比较？

Answer 1

如果您从 List<T> 中删除一个项目，它之后的所有项目将被移回一个位置。所以如果你删除 n 个项目，很多项目将被移动 n 次。
RemoveAll 只会移动一次，您可以在 List<T> 的源代码中看到这一点: source

另一件事是Remove(T item)将在整个列表中搜索该项目，因此这是另外 n 个操作。

有些事情与你的问题无关，但我还是想指出:
如果您使用 for 循环从列表中删除项目，那么从最后开始会容易得多:

for (int i = intervals.Count - 1; i >= 0; i--)
{
    if (intervals[i].Intersects(point))
    {
        intervals.RemoveAt(i);
    }
}

这样，你就不需要那个丑陋的 else 子句了