如何高效迭代子列表中的元素并将其从列表中删除？

Question

这是一个例子：originalList 是对象列表。

var subList = (originalList.Where(x => x.number < 0)).ToList();
originalList.RemoveAll(x => x.number < 0);

我稍后会使用 subList。在这个例子中，originalList 被遍历了两次。这个函数被调用数十亿次，而且 originalList 是一个大的列表。

有没有一种简单的方法来提高性能？

---

一个重要的事情是：对象数量的值在两次调用该函数之间可能会发生改变。

- Libério Martins

---

这感觉像是一个XY问题 - 你必须使用List吗？一个更好的数据结构可能会更优。 - NetMage

例如，使用LinkedList而不是List，我可以获得一个RemoveAllAndReturn方法，其运行速度比List版本快50到200倍，具体取决于删除的频率。 - NetMage

不，我不必使用List。 非常感谢，我现在会进行测试。 - Libério Martins

请注意，LinkedList 占用更多的空间 - 如果这很关键，或者时间非常关键，那么实现单向链表可能更有效。 - NetMage

Answer 1

一种提高效率的方法（尽管最终仍为O(n)）是将删除操作批量进行。我的测试显示，这取决于删除的频率，速度可以与原来相同或快4倍以上。以下是作为扩展方法的函数：

public static List<T> RemoveAllAndReturn<T>(this List<T> input, Func<T, bool> condition) {
    List<T> result = new List<T>();
    var removeCt = 0;
    for (int i = input.Count - 1; i >= 0; --i) {
        if (condition(input[i])) {
            result.Add(input[i]);
            ++removeCt;
        }
        else if (removeCt > 0) {
            input.RemoveRange(i + 1, removeCt);
            removeCt = 0;
        }
    }
    if (removeCt > 0)
        input.RemoveRange(0, removeCt);
    return result;
}

- NetMage

Answer 2

该方法删除所有满足条件的元素，并返回已删除元素的列表。它只迭代一次。

public static List<T> RemoveAll<T>(List<T> input, Func<T,bool> condition)
{
    List<T> removedEntries = new List<T>();
    int offset = 0;
    for(int i = 0; i < input.Count - offset; i++)
    {
      while(i < input.Count - offset && condition.Invoke(input[i + offset]))
      {
         removedEntries.Add(input[i + offset]);
         offset++; 
         Console.WriteLine("i="+i+", offset="+offset);
      }
    
      if(i < input.Count - offset)
      {
         input[i] = input[i+offset];
      }
    }
    input.RemoveRange(input.Count - offset, offset);
    return removedEntries;
}

我们循环遍历列表并检查元素是否符合条件。如果匹配条件，则将该元素后面的元素复制到该位置。因此，所有不满足条件的元素都在列表的开头，而所有满足条件的元素都在列表的末尾。在最后一步中，删除列表末尾的元素。

对于removedEntries列表，给予初始容量可能是明智的。默认情况下，列表的容量为4，每当超出时就会增加一倍。如果要删除100个元素，则必须扩展容量5次。这是一个O(n)操作。如果您可以估计将删除约10％的元素，则可以编写以下内容：

List<T> removedEntries = new List<T>(input.Count / 10);

这可能会节省你一些时间，但另一方面，如果你不需要列表的完整初始容量，就会浪费一些内存。

在线演示：https://dotnetfiddle.net/dlthkH

- SomeBody

---

List.RemoveAt 是一个 O(n) 操作，其中 n = Count - index。 - Johnathan Barclay

因此，根据要删除的元素数量和类型，操作员的代码可能更有效率。 - Johnathan Barclay

我认为线程安全的集合只有在同时添加/删除列表中的对象时才能起到帮助作用。所需的同步程度取决于代码需要满足什么保证，而这在原始帖子中并没有清楚地描述。 - JonasH

你为什么要使用condition.Invoke(input[i])而不是condition(input[i])呢？ - NetMage

运行一些测试，当删除百分比为13％或更高时，这比使用LinkedList还要快；在删除少于13％的情况下，LinkedList似乎更快。 - NetMage

Answer 3

您可以考虑做这个Hack：

List<SomeType> subList = new();
originalList.RemoveAll(item =>
{
    bool shouldBeRemoved = item.Number < 0;
    if (shouldBeRemoved) subList.Add(item);
    return shouldBeRemoved;
});

< p >传递给RemoveAll的Predicate<T>不是纯函数：它具有在subList中插入匹配元素的副作用。基于RemoveAll方法的实现，这个hack应该按预期工作。然而，文档并没有明确保证谓词只会对每个元素调用一次：

当前List<T>的元素将被单独传递给Predicate<T>委托，满足条件的元素将从List<T>中删除。

这就是为什么我称之为hack。如果当前的RemoveAll方法的行为得到了记录和保证，它就不会被称为hack。如果您想要绝对安全，可以使用自定义的RemoveAll实现，该实现具有良好定义的行为，例如在this answer中找到的实现方式。

您还可以将其作为扩展方法实现：

public static int RemoveAll<T>(this List<T> source, Predicate<T> match,
    out List<T> removed)
{
    ArgumentNullException.ThrowIfNull(source);
    ArgumentNullException.ThrowIfNull(match);

    List<T> removedLocal = removed = new();
    int removedCount = source.RemoveAll(item =>
    {
        bool shouldBeRemoved = match(item);
        if (shouldBeRemoved) removedLocal.Add(item);
        return shouldBeRemoved;
    });
    Debug.Assert(removedCount == removed.Count);
    return removedCount;
}

使用示例：

originalList.RemoveAll(x => x.number < 0, out var subList);

- Theodor Zoulias