具有非常快速的迭代以及良好的添加和删除速度的集合 [英] Collection with very fast iterating and good addition and remove speeds
问题描述
我正在寻找一个可以快速迭代的集合.我还将定期添加项目并删除(特定)项目，因此理想情况下也希望这些操作也很快.
我正在xbox上进行开发，因此仅限于紧凑框架(或多或少).将垃圾和对象分配保持在最低水平是非常重要的，因此可以为对象预分配空间的任何事情都将是很好的.
我将在集合中存储uint(但是如果需要可以为int).不过，一般的解决方案将是不错的选择，因为我敢肯定，将来会有需求.
.net集合将是理想的选择，否则，轻量级和开放源代码的东西会很棒.
是否有适合我需要的收藏班?如果没有，我将如何创建一个?
为了详细说明，它们是对象ID，类应处理每个帧.通常，它们将以升序添加，并带有间隔.没有上限.不过，任何内容都可以删除，这会留下空白.
迭代顺序并不完全重要，但是如果顺序一致，它将非常有用(特别是对于调试而言).
我有两个建议可以尝试:
首先，如何使用Reflector或ILSpy在通用List<T>中查看?我假设实现不在CF中，或者您可以使用它.通用List<T>具有数组支持，并使用从长度为4的数组开始的加倍算法，对Capacity的每次调用都会使它加倍并执行Array.Copy到新数组中.除非您将Capacity显式设置为零，否则它不会调整大小，因此请从内存的角度注意.添加是一回事，但每个Remove都会导致复制数组并在删除索引后向左移.
第二个建议是-创建一个自定义类，该类包装一个整数数组以处理此问题，该类使用与通用List<T>类似的double算法(或四倍)(以处理大小调整)，但起始大小为256您可以随意添加对象整数id的顺序，并且不会经常出现.您还可以通过将(int)-1或uint.MaxValue指定为空索引"来模拟移除，这意味着移除时没有Array.Copy.然后，对每帧应用某种快速排序，以在绘制之前对对象索引数组进行排序.如果您升序排序，则所有-1都会出现在开头(或uint.MaxValues出现在结尾)，可以忽略.您可以通过在单独的线程上调整大小和删除前面的-1来定期收集"索引数组(请注意-使用锁定;)
您怎么看?只是想您将每帧偏移一些计算以进行快速排序(在xbox上并不昂贵，而在每个Remove和一些Adds上的内存分配/收集比较昂贵(昂贵).
更新-BlockArray-列表< T []>其中T是固定大小的数组
对此有进一步的评论.我最近正在尝试使用最有效的数据结构来动态调整列表大小，并通过实验发现了数组块-由T []列表支持的类，其中每个T []是固定大小的块的数组，例如512、4096、8192作为相对于普通List T的几个优点.
我发现在List< T []>中实现了Add()(大小未知)的实现.对于List< T> ;，其性能大大优于Add()，尤其是当总大小变大时.这是由于List< T>的加倍算法，该算法要求一个新数组的大小是旧数组的2倍，而memcpy则在超出大小时使用旧数组.迭代速度相似.预分配(预定义容量)比List T要慢得多.对于小块尺寸(512)，但对于大块尺寸(8192)仅稍慢一些.删除是有问题的，因为需要复制/左移许多块.
有趣的是在List< T []>中(块列表)，您可以缓存/合并块.如果足够小，则T []的块可以放入较小的对象堆中(有利于压缩，更快地分配)，可以放入L2高速缓存中，并且可以预先分配并合并许多块
I'm after a collection that I can iterate through very fast. I'll also be adding items and removing (specific) items fairly regularly and so ideally would like those operations to be fast too.
I'm developing on the xbox and so am restricted to the compact framework (more or less). It's very important that I keep garbage and object allocations to a minimum, so anything where i can pre-allocate space for my objects would be great.
I'll be storing uints (but can be ints if needed) in the collection. A generic solution would be good though, as i'm sure i'll have a need in the future.
A .net collection would be ideal, failing that something light-weight and open source would be great.
Is there a collection class that would suit my needs? If not, how would I go about creating one?
To elaborate a bit, they are object id's that a class should process each frame. They'll generally be added in ascending order, with gaps. There's no upper limit. Any could be removed though, which would leave gaps.
Iteration order isn't completely important, but it would be very useful (particularly for debugging) if it was in a consistent order.
I've got two suggestions to try:
Firstly, what about using Reflector or ILSpy to look inside Generic List<T>? I assume that implementation isn't in the CF or you could use it. Generic List<T> is array backed and uses a doubling algorithm starting at length 4 array, every call to .Add over the Capacity causes it to double and perform an Array.Copy into the new array. It doesn't resize unless you explicitly set Capacity to zero so beware from a memory point of view. Adds are one thing but each Remove will cause the array to be copied and left-shifted after the index that was removed.
The second suggestion is this - what about about creating a custom class which wraps an integer array to handle this which uses a similar double algorithm (or quadrupling) to Generic List<T> (to handle resizing) but starts at say size 256. You could add object integer id's to this out of order as fast as you like and it won't double too often. You could also simulate a remove by designating (int)-1 or uint.MaxValue as a "null index" meaning no Array.Copy on remove. Then, apply some sort of fast sorting per frame to sort the object index array before drawing. If you sort ascending all your -1s will appear at the start (or uint.MaxValues at end) and can be ignored. You can periodically "collect" the index array by resizing and removing the preceeding -1's on a separate thread (beware - use locking ;)
What do you think? Just thinking you will offset some computation once per frame for fast sorting (not expensive on xbox vs. memory allocation/collection on each Remove and some Adds (expensive).
UPDATE - BlockArray - List<T[]> where T is fixed size array
A further comment on this. I was recently experimenting with the most efficient data-structure for dynamically sized lists and discovered by experimentation that array blocks - a class which is backed by a List of T[], where each T[] was an array of fixed size block, e.g. 512, 4096, 8192 as several advantages over a plain List<T>.
I found that an implementation of Add() (where size is unknown) in a List<T[]> vastly outperformed Add() for List<T>, especially when the total size became larger. This is due to List<T>'s doubling algorithm which requests a new array 2x the size of the old, and memcpy's the old array over whenever size is exceeded.
Iterating speed is similar. Pre-allocation (pre-defined capacity) was much slower than List<T> for small block sizes (512), but only slightly slower for large block sizes (8192). Removes are problematic, as require copying/left shifting many blocks.
What's interesting is in a List<T[]> (block list), you can cache/pool the blocks. If small enough, blocks of T[] fit into the small object heap (favouring compaction, quicker allocation), may fit into the L2 cache and a number of blocks could be pre-allocated and pooled
这篇关于具有非常快速的迭代以及良好的添加和删除速度的集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
