6

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

我正在开发一个游戏，在游戏中，我有很多子弹在任何给定的时刻都在空中飞行，比如说 100 颗子弹，每一帧我将它们移动几个像素并检查与游戏中物体的碰撞，我需要移除从列表中每个碰撞的子弹。

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

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

因为循环是O(n)，而删除是O(n)，我花O(n^2了 ) 时间来删除。

有没有更好的方法来删除它，或者更适合使用的集合？

4

7 回答 7

6

集合和链表都具有恒定的时间删除。您可以使用其中任何一种数据结构吗？

没有办法避免从List<T>. 如果这对您来说是个问题，您将需要使用不同的数据结构。它也可能使计算 bulletsToRemove 的代码感觉更好。

ISet<T>有很好的方法来计算对象集之间的差异和交集。

使用集合会丢失排序，但鉴于您正在接受子弹，我猜这不是问题。您仍然可以在恒定时间内枚举它。

在您的情况下，您可能会写：

mBullets.ExceptWith(bulletsForDeletion);
于 2012-12-29T13:19:11.857 回答
5

创建一个新列表：

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

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

由于散列，该算法是 O(N)。

于 2012-12-29T13:21:49.960 回答
2

你不能从List（相当于Java的ArrayList突出显示）切换到LinkedList？LinkedList 需要 O(1) 来删除特定元素，但 O(n) 需要按索引删除

于 2012-12-29T13:18:41.420 回答
1

您不应该考虑如何在内部实现列表。您应该在该抽象级别与列表进行交互。

如果您确实有性能问题并且您将它们精确到列表中，那么是时候看看它是如何实现的了。

至于从列表中删除项目 - 您可以使用mBullets.RemoveAll(predicate), wherepredicate是一个表达式，用于标识已碰撞的项目。

于 2012-12-29T13:19:06.780 回答
1

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);
}
于 2012-12-29T13:25:58.927 回答
0

本着“usr”建议的功能习语的精神，您可能会考虑根本不从您的列表中删除。相反，让您的更新例程获取一个列表并返回一个列表。返回的列表仅包含“仍然活着”的对象。然后，您可以在游戏循环结束时（或立即，如果合适）交换列表。我自己做过这个。

于 2012-12-29T14:20:17.833 回答
0

理想情况下，考虑 C# 如何实现其 List 方法并不重要，并且有点不幸的是，它i在执行索引后重新分配了所有数组元素somelist.RemoveAt(i). ，但有时需要围绕标准库实现进行优化。

如果您发现在使用 RemoveAt 从列表中删除列表元素时，您的执行花费了无法接受的重排，则一种可能对您有用的方法是将其与末尾交换，然后RemoveAt从列表末尾交换：

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

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

于 2022-03-05T10:12:31.683 回答