1

我有一个游戏循环，它绘制了一个对象列表，该列表称为“mylist”并包含大约 1000 个对象，需要不断从列表中添加和删除对象（尤其是快速飞行并击中物体的子弹），每个对象很少第二。

如果我理解正确，如果列表容量足够大，则 List 中的插入实际上是免费的，问题在于删除是 O(n)，因为首先我需要在列表中找到该项目，其次它会创建一个新列表拆除后。

如果我可以汇总所有删除并每帧进行一次，那将是有效的，因为我将使用 mylist.Except(listToRemove) 并且这将在 O(n) 中。但不幸的是我做不到。

链表也有问题，因为我需要在列表中找到对象。

有人有更好的建议吗？

4

4 回答 4

3

一个HashSet呢？它支持O(1)插入和删除。如果您需要排序，请使用树形数据结构或LinkedList加号Dictionary，以便您快速找到节点。

BCL 有 aSortedList和 aSortedSet和 a SortedDictionary。除了一个都非常慢，但我永远不记得哪一个是“好”的。它在内部是基于树的。

于 2013-03-23T14:28:31.940 回答
0

如果您正在搜索，那么您最好的选择是使用Dictionary平均情况为 O(1) 和最坏情况为 O(n) 的 a（当您散列到同一个存储桶时）。

如果您需要保持顺序，您可以使用平衡二叉搜索树的任何实现，您的性能将是 O(logn)。

在 .NET 中，这简单地归结为

字典- 插入/删除 O(1)（平均情况）

SortedDictionary - 保留有序操作的顺序，插入/删除O(logn)

于 2013-03-23T14:30:29.857 回答
0

因此，理想情况下，您希望使用具有O(1)或O(log n)删除和插入的数据结构。字典类型的数据结构可能是理想的，因为它们具有恒定的平均情况插入和删除时间复杂度。我会推荐 aHashSet然后覆盖GetHashCode()你的游戏对象基类。

这是有关所有不同字典/哈希表数据结构的更多详细信息。

时间复杂度

以下是所有“类字典”数据结构及其时间复杂度：

Type              Find by key  Remove      Add
HashSet           O(1)*        O(1)*     O(1)**
Dictionary        O(1)*        O(1)*     O(1)**
SortedList        O(log n)     O(n)      O(n)
SortedDictionary  O(log n)     O(log n)  O(log n)

*O(n) 有碰撞
**O(n) 有碰撞或添加超出数组的容量。

HashSet 与字典

HashSeta和 a之间的区别在于DictionaryDictionary 对 a 起作用，KeyValuePair而使用 aHashSet的键是对象本身（它的GetHashCode()方法）。

SortedList 与 SortedDictionary

只有在需要维持订单时才应考虑这些。不同之处在于它SortedDictionary使用红黑树并SortedList对其键和值使用排序数组。

参考

于 2013-03-23T14:30:46.710 回答
0

在性能方面，您可能会通过简单地不从任何类型的列表中插入或删除任何内容来看到最佳结果。分配一个足够大的数组并标记所有对象是否应该被渲染。

但是，鉴于您的要求，这可能都是过早的优化。您可以每秒 30 次重新创建 1000 个元素的整个列表，而不会看到任何性能下降。

我建议阅读 Braid 的创建者提供的关于在独立视频游戏中使用正确数据结构的演示文稿的幻灯片：http: //the-witness.net/news/2011/06/how-to-program-independent-games/（tl；博士只是对所有事情都使用数组）。

于 2013-03-23T14:48:14.700 回答