在c#中什么是最好的泛型，用于许多插入和删除

本文关键字：用于 许多 插入 删除 泛型 什么 | 更新日期: 2023-09-27 18:05:21

我有一个游戏循环，它绘制了一个对象列表，该列表称为"mylist"，包含大约1000个对象，对象(特别是快速飞行并击中物体的子弹)需要不断地从列表中添加和删除，每秒几个对象。

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

如果我可以聚合所有的移除并使它们每帧一次，这将是有效的，因为我将使用mylist.Except(listToRemove)，这将是在O(n)。但遗憾的是，我做不到。

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

谁有更好的建议?

在c#中什么是最好的泛型，用于许多插入和删除

HashSet呢?支持O(1)的插拔。如果您需要排序，请使用树数据结构或LinkedList + Dictionary，这可以让您快速找到节点。

BCL有SortedList、SortedSet和SortedDictionary。除了一个之外，其他的都很慢，但我永远记不住哪一个是"好"的。

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

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

在。net中，这简单地归结为

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

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

所以理想情况下，您希望使用具有O(1)或O(log n)删除和插入的数据结构。字典类型的数据结构可能是理想的，因为它们具有恒定的平均插入和删除时间复杂度。我建议使用HashSet，然后在你的游戏对象基类上重写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)与碰撞

** 0 (n) .

HashSet vs Dictionary

HashSet和Dictionary之间的区别在于，Dictionary在KeyValuePair上工作，而在HashSet上，关键字是对象本身(它的GetHashCode()方法)。

SortedList vs SortedDictionary

只有当你需要维持订单时，你才应该考虑这些。不同之处在于SortedDictionary使用红黑树，而SortedList使用排序数组作为键和值。

引用

  • 我的博客文章-。net简单的集合和字典
  • MSDN - HashSet
  • MSDN - Dictionary
  • MSDN - SortedDictionary
  • MSDN - SortedList

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

考虑到你的需求，然而，这都可能是过早的优化;您可以每秒30次重新创建包含1000个元素的整个列表，而不会看到任何性能下降。

我建议阅读一下Braid的创造者所做的关于在独立电子游戏中使用正确数据结构的幻灯片:http://the-witness.net/news/2011/06/how-to-program-independent-games/(tl;dr只是使用数组)。

相关文章：