如何高效地从 List<T> 中移除元素（C#）？

Question

如果我理解正确的话（如果我错了请纠正我），在.NET中列表是由数组实现的，这意味着每删除一个列表项都会导致整个列表的重新分配（这反过来又意味着O(n)）。

我正在开发一款游戏，在游戏中我有许多子弹在空中飞行，比如说100颗，每帧我将它们移动几个像素并检测与游戏中物体的碰撞，我需要从列表中移除每个发生碰撞的子弹。

所以我将碰撞的子弹收集到另一个临时列表中，然后执行以下操作：

foreach (Bullet bullet in bulletsForDeletion)
    mBullets.Remove(bullet);

由于循环是 O(n)，删除操作也是 O(n)，所以我需要 O(n^2)时间来执行删除操作。

是否有更好的方式来进行删除操作，或者使用更适合的数据结构呢？

- OopsUser

---

不要说抱歉。我们都在这里学习。 - Soner Gönül

你确定你真的有问题，还是过早地进行了优化？ - Oded

我没有实际问题，它以60帧每秒运行，我只是“感觉”我正在编写一些错误的东西，因为这样的操作不应该是O(n^2)。 - OopsUser

Answer 1

集合和链表都具有常量时间的删除操作。您能使用这两种数据结构吗？

从List中删除需要O(N)的时间代价，无法避免。如果这是一个问题，您需要使用不同的数据结构。这也可能会使计算bulletsToRemove的代码更容易阅读。

ISet具有计算对象集合之间差异和交集的好方法。

使用集合会失去排序功能，但考虑到您要取子弹，我猜这不是一个问题。您仍然可以在常量时间内枚举它。

在您的情况下，您可以编写以下内容：

mBullets.ExceptWith(bulletsForDeletion);

- Drew Noakes

---

".NET中的“set”叫什么？我没有看到任何叫做set的通用类型。链表（以及集合）的问题在于数据不在内存中的同一位置，因此当我从List中读取时，我可以获得缓存的好处，但是当我使用set/linked list时，我就失去了这个优势。尽管我大约每秒需要从列表中删除一次项目，但我需要从列表中读取100次以上（碰撞检查等）。" - OopsUser

@OopsUser，您正在寻找ISet<T>，您可以在此处阅读相关信息。 - Drew Noakes

@OopsUser，另外，看看您如何计算bulletsForDeletion可能会很有用。也许还有一种更优化的方法。 - Drew Noakes

这是代码： foreach (Bullet bullet in mBullets) { foreach (Player player in players) { if (player.Location.Intersects(bullet.Location) { bulletsForDeletion.Add(bullet); player.HP-=1; } } } - OopsUser

Answer 2

创建一个新列表：

var newList = `oldList.Except(deleteItems).ToList()`.

尽可能使用函数式习语。不要修改现有的数据结构，创建新的数据结构。

由于哈希技术，该算法的时间复杂度为O(N)。

- usr

---

为什么它是O（n）？当他将变量复制到另一个列表时，他需要检查每个项目是否存在于“deleteItems”列表中，它看起来像O（n ^ 2）。 - OopsUser

@OopsUser Except 内部构建了一个哈希表，所以对于 oldList 中的每个项目，存在性检查是 O(1) 的。这使得 O(oldList.Count + deleteItems.Count) ~ O(N) 成立。 - usr

+1. @OopsUser，Except扩展方法会读取源枚举中的每个项，并输出那些不在deleteItems中的项。在内部，它会构建一个deleteItems的哈希表，并测试每个输入是否存在于该哈希表中。只有未在哈希表中找到的项才会通过到输出。这是O(N)的，但它将导致分配新的哈希表和新的数组（由ToList创建）。也许你不需要担心这种内存开销，但你应该知道它的存在。 - Drew Noakes

谢谢，这正是我想要的，因为我认为最好不要将列表更改为Set或LinkedList，以便在读取时获得最佳性能。 - OopsUser

Answer 3

你不能仅仅从List（相当于Java中的ArrayList）切换到LinkedList吗？LinkedList可以在O(1)时间内删除特定元素，但在按索引删除时需要O(n)时间。

- usr-local-ΕΨΗΕΛΩΝ

Answer 4

理想情况下，我们不应该考虑C#如何实现其List方法，有些不幸的是，在使用somelist.RemoveAt(i)时，它会重新分配所有索引之后的数组元素。 有时候，需要优化标准库实现。

如果您发现在从带RemoveAt的列表中删除元素时，执行效果不佳，请尝试一种方法：将其与末尾交换，然后从列表末尾RemoveAt。

if (i < mylist.Count-1) {
     mylist[i] = mylist[mylist.Count-1];
}
mylist.RemoveAt(mylist.Count-1);

当然，这是一个O(1)的操作。

- Mars

Answer 5

RemoveAt(int index) 比 Remove(T item) 更快，因为后者在内部使用第一个方法，并进行反射，这是每个函数中的代码。

此外，Remove(T) 具有函数 IndexOf，其中包含第二个循环以评估每个项目的索引。

public bool Remove(T item)
{
  int index = this.IndexOf(item);
  if (index < 0)
    return false;
  this.RemoveAt(index);
  return true;
}


public void RemoveAt(int index)
{
  if ((uint) index >= (uint) this._size)
    ThrowHelper.ThrowArgumentOutOfRangeException();
  --this._size;
  if (index < this._size)
    Array.Copy((Array) this._items, index + 1, (Array) this._items, index, this._size - index);
  this._items[this._size] = default (T);
  ++this._version;
}

我会像这样做一个循环：

for (int i=MyList.Count-1; i>=0; i--) 
{
    // add some code here
    if (needtodelete == true)
    MyList.RemoveAt(i);
}

- sharp12345

---

你最后的代码块是 MyList.Clear() 的低效版本。你是不是想写别的东西？ - Drew Noakes

@DrewNoakes，是的，我假设询问用户将添加一些条件来删除一些项目，他实际上不会删除所有项目，我已编辑我的帖子。 - sharp12345

Answer 6

关于列表的内部实现方式，这不是你应该考虑的事情。你应该在抽象层次上与列表进行交互。

如果你确实遇到了性能问题，并将其定位为列表问题，那么就是时候看看它的实现方式了。

至于从列表中删除项目 - 你可以使用 mBullets.RemoveAll(predicate)，其中predicate是一个表达式，用于识别已经发生碰撞的项目。

- Oded

Answer 7

根据“usr”建议的函数习惯，您可以考虑不从列表中删除任何对象。相反，让您的更新程序接受一个列表并返回一个列表。返回的列表仅包含“仍然存在”的对象。然后，在游戏循环的末尾（或立即，如果适用），您可以交换列表。我自己也这样做过。

- Griffin