Geo*_*ett 5 c# collections performance xna xbox
我正在追踪一个可以快速迭代的集合.我也会定期添加项目和删除(特定)项目,因此理想情况下这些操作也会很快.
我正在开发xbox,因此仅限于紧凑的框架(或多或少).将垃圾和对象分配保持在最低限度非常重要,因此我可以为我的对象预先分配空间的任何事情都会很棒.
我将在集合中存储uints(但int如果需要可以是s).一般的解决方案会很好,因为我相信我将来会有需求.
一个.net集合将是理想的,没有一个轻量级和开源的东西会很棒.
是否有适合我需求的收藏课程？如果没有,我将如何创建一个？
为了详细说明,它们是对象id,类应该处理每个帧.它们通常按升序添加,有间隙.没有上限.任何可以删除,这将留下空白.
迭代顺序并不完全重要,但如果顺序一致,它将非常有用(特别是对于调试).
我有两个建议可以尝试：
首先，使用 Reflector 或 ILSpy 来查看 Generic 内部怎么样List<T>？我假设 CF 中没有实现，或者您可以使用它。GenericList<T>支持数组，并使用从长度为 4 的数组开始的加倍算法，每次调用 .Add 都会导致容量加倍，并执行 Array.Copy 到新数组中。除非您明确将“容量”设置为零，否则它不会调整大小，因此从内存的角度要小心。添加是一回事，但每次删除都会导致数组在被删除的索引之后被复制并左移。
第二个建议是这样的 - 创建一个自定义类，它包装一个整数数组来处理这个问题，它使用与 Generic 类似的双倍算法（或四倍）List<T>（以处理调整大小），但从大小 256 开始。您可以添加对象整数id 的速度是乱七八糟的，只要你喜欢，它不会经常加倍。您还可以通过将 (int)-1 或 uint.MaxValue 指定为“空索引”来模拟删除，这意味着删除时没有 Array.Copy。然后，在绘制之前对每帧应用某种快速排序来对对象索引数组进行排序。如果按升序排序，所有 -1 将出现在开头（或 uint.MaxValues 在末尾），并且可以被忽略。您可以通过在单独的线程上调整大小和删除前面的索引数组来定期“收集”索引数组-1（注意 - 使用锁定；）
你怎么认为？只是想你会每帧抵消一些计算以进行快速排序（在 xbox 上并不昂贵，而在每个删除和一些添加上进行内存分配/收集（昂贵））。
更新 - BlockArray - List<T[]> 其中 T 是固定大小的数组
对此进一步评论。我最近正在尝试动态大小列表的最有效的数据结构，并通过实验发现数组块 - 一个由 T[] 列表支持的类，其中每个 T[] 是固定大小块的数组，例如512、4096、8192 与普通 List<T> 相比有几个优点。
我发现 List<T[]> 中 Add()（大小未知）的实现远远优于 List<T> 的 Add()，特别是当总大小变大时。这是由于 List<T> 的加倍算法要求新数组的大小是旧数组的 2 倍，而每当超过大小时，memcpy 都会覆盖旧数组。
迭代速度相似。对于小块大小 (512)，预分配（预定义容量）比 List<T> 慢得多，但对于大块大小 (8192) 仅稍慢一些。删除是有问题的，因为需要复制/左移许多块。
有趣的是在 List<T[]> （块列表）中，您可以缓存/池化块。如果足够小，T[] 的块适合小对象堆（有利于压缩，更快的分配），可以适合 L2 缓存，并且可以预先分配和池化许多块