怎么可能&;removeall &;在LINQ中比迭代要快得多

本文关键字：迭代 快得多 LINQ removeall 怎么可能 | 更新日期: 2023-09-27 18:10:46

以下代码:

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)中。所以我希望两者的性能相似。

将"Remove"替换为"RemoveAt"时，迭代速度快得多，与"RemoveAll"相当。但是"Remove"answers"RemoveAt"都具有O(n)复杂度，那么为什么它们之间的性能差异如此之大呢?可能只是由于"Remove (item)"比较列表元素与"item"answers"RemoveAt"不执行任何比较?

怎么可能&;removeall &;在LINQ中比迭代要快得多

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

另一件事是Remove(T item)将在整个List中搜索项目，所以这又是n次操作。

与你的问题无关，但我还是想指出来:
如果使用for循环从List中删除项，那么从末尾开始要容易得多:

for (int i = intervals.Count - 1; i >= 0; i--)
{
    if (intervals[i].Intersects(point))
    {
        intervals.RemoveAt(i);
    }
}
这样，您就不需要那个丑陋的else-子句

RemoveAll可以在O(n)中完成，通过检查n元素的条件，最多移动n元素。

你的循环是O(n^2)，因为每个Remove需要检查n元素。即使你将其更改为RemoveAt，它仍然需要向上移动到n元素。

这可能是最快的解决方案:intervals.RemoveAll(x => points.Any(x.Intersects));

List是一个数组，从数组中删除一个元素需要将你要删除的元素之后的所有元素移动到上一个索引，所以a[i]被移动到a[i-1]。

重复执行此操作需要多次移动，即使更多的元素符合删除标准。RemoveAll可以通过在遍历列表时每次移动1个以上索引来优化这一点，并找到更多符合删除条件的元素。

区别在于Remove本身是一个O(n)，所以你得到O(n^2)。

用新的集合和赋值替换for。

items = items.Where(i => ...).ToList();

此方法具有与RemoveAll相同的算法时间复杂度，但使用额外的O(n)内存。

相关文章：