c# - 具有非常快的迭代和良好的添加和删除速度的集合

Question

我正在寻找一个可以非常快速地迭代的集合。我还将相当定期地添加项目和删除(特定的)项目，因此理想情况下希望这些操作也能很快。

我在 xbox 上进行开发，因此受限于紧凑型框架(或多或少)。将垃圾和对象分配保持在最低限度非常重要，因此任何可以为我的对象预分配空间的地方都会很棒。

我将在集合中存储 uint(但如果需要可以是 int)。不过，通用解决方案会很好，因为我相信我将来会有需要。

.net 集合将是理想的选择，否则轻量级和开源的东西会很棒。

是否有适合我需要的集合类？如果没有，我将如何创建一个？

---

更详细地说，它们是类应该处理每一帧的对象 ID。它们通常会按升序添加，中间有间隙。没有上限。不过，可以删除任何内容，这会留下空白。
迭代顺序并不完全重要，但如果顺序一致，它将非常有用(特别是对于调试)。

Answer 1

我有两个建议可以尝试:

首先，如何使用 Reflector 或 ILSpy 查看 Generic List<T> ？我假设该实现不在 CF 中，或者您可以使用它。通用 List<T>是数组支持的，并使用从长度为 4 的数组开始的加倍算法，每次调用 .Add over Capacity 都会使其加倍并执行 Array.Copy 到新数组中。它不会调整大小，除非您明确地将容量设置为零，因此从内存的角度来看要小心。添加是一回事，但每次删除都会导致数组在删除的索引之后被复制和左移。

第二个建议是——创建一个自定义类来包装一个整数数组来处理这个问题，它使用与 Generic List<T> 类似的双重算法(或四倍算法)。 (以处理调整大小)但从大小 256 开始。您可以按照您喜欢的速度无序地将对象整数 ID 添加到此，并且它不会经常加倍。您还可以通过将 (int)-1 或 uint.MaxValue 指定为“空索引”来模拟删除，这意味着删除时没有 Array.Copy。然后，在绘制之前对每帧应用某种快速排序来对对象索引数组进行排序。如果您按升序排序，所有 -1 将出现在开头(或 uint.MaxValues 结尾)并且可以忽略。您可以通过调整大小和删除前面的 -1 来定期“收集”索引数组。在一个单独的线程上(注意 - 使用锁定；)

你怎么看？只是想你会每帧偏移一些计算以进行快速排序(在 xbox 上并不昂贵，而在每个删除和一些添加(昂贵)上进行内存分配/收集(昂贵)。

更新 - BlockArray - List 其中 T 是固定大小的数组

对此的进一步评论。我最近正在为动态大小的列表试验最有效的数据结构，并通过试验发现数组 block ——一个由 T[] 列表支持的类，其中每个 T[] 都是固定大小块的数组，例如512、4096、8192 与普通 List 相比有几个优点。

我发现 List 中的 Add() 实现(其中大小未知)大大优于 List 中的 Add()，尤其是当总大小变大时。这是由于 List 的加倍算法要求新数组的大小是旧数组的 2 倍，并且只要超过大小，memcpy 就会覆盖旧数组。

迭代速度相似。对于小块大小 (512)，预分配(预定义容量)比 List 慢得多，但对于大块大小 (8192) 仅略慢。删除是有问题的，因为需要复制/左移许多 block 。

有趣的是在 List ( block 列表)中，您可以缓存/池 block 。如果足够小，T[] 的 block 适合小对象堆(有利于压缩，更快分配)，可能适合 L2 缓存，并且可以预分配和池化一些 block