集合具有非常快速的迭代和良好的添加和删除速度
本文关键字：添加 删除 速度 迭代 非常 集合 | 更新日期: 2023-09-27 18:19:42
我正在寻找一个可以快速迭代的集合。我还将定期添加项目和删除（特定）项目，因此理想情况下希望这些操作也能很快。
我是在xbox上开发的，所以（或多或少）只限于紧凑的框架。将垃圾和对象分配保持在最低限度是非常重要的，所以任何可以为对象预先分配空间的东西都会很棒。
我将在集合中存储uint s（但如果需要，也可以是int s）。不过，通用的解决方案会很好，因为我相信我将来会有需求。
.net集合将是理想的选择，如果不能实现轻量级和开源的话，那就太棒了。
有适合我需要的收藏品课程吗？如果没有，我将如何创建一个？
更详细地说，它们是一个类应该处理每个帧的对象id。它们通常会以升序添加，并带有间隙。没有上限。不过，任何一个都可能被删除，这会留下空白
迭代顺序并不完全重要，但如果顺序一致，它将非常有用（特别是对于调试）。
我有两个建议可以尝试：
首先，使用Reflector或ILSpy查看Generic List<T>内部如何？我假设实现不在CF中，或者你可以使用它。Generic List<T>是支持数组的，每次调用都使用从长度为4的数组开始的加倍算法。在Capacity上添加会使其加倍并执行array.Copy到新数组中。除非您明确地将Capacity设置为零，否则它不会调整大小，所以从内存的角度来看要小心。添加是一回事，但每次移除都会导致数组在移除索引后被复制并左移。
第二个建议是，创建一个自定义类来包装一个整数数组来处理这个问题，该类使用类似于Generic List<T>（处理大小调整）的双倍算法（或四倍算法），但从256大小开始。您可以随心所欲地快速将对象整数id添加到这个无序的对象中，而且它不会经常翻倍。您也可以通过指定（int）-1或uint来模拟移除。MaxValue为"null索引"，表示没有数组。删除时复制。然后，在绘制之前，对每帧应用某种快速排序来对对象索引数组进行排序。如果按升序排序，所有的-1都将出现在开头（或结尾的uint.MaxValues），并且可以忽略。您可以通过在单独的线程上调整和删除前面的-1来周期性地"收集"索引数组（注意-使用锁定；）
你觉得怎么样？只是想你会为快速排序每帧抵消一次计算（在xbox上并不昂贵，而在每个Remove和一些Add上的内存分配/收集（昂贵）。
更新-区块阵列-列表<T[]>其中T是固定大小的阵列
对此有进一步的评论。最近，我尝试了用于动态大小列表的最有效的数据结构，并通过实验发现，数组块-一个由T[]列表支持的类，其中每个T[]都是固定大小块的数组，例如512、4096、8192，与普通List<T>。
我发现在List<T[]>List<T>，尤其是当总尺寸变大时。这是由于List<T>'s加倍算法，该算法请求一个旧数组大小的2倍的新数组，并且每当超过大小时，memcpy就会将旧数组覆盖。
迭代速度相似。预分配（预定义容量）比List<T>对于小块大小（512）而对于大块大小（8192）仅稍慢。删除是有问题的，因为需要复制/左移许多块。
有趣的是在列表<T[]>（块列表），您可以缓存/池化块。如果足够小，T[]的块可以放入小对象堆（有利于压缩、更快的分配），也可以放入二级缓存，并且可以预先分配和池化一些块
使用Mono的HashSet<T>怎么样？
https://github.com/mono/mono/blob/master/mcs/class/System.Core/System.Collections.Generic/HashSet.cs
它是根据MIT X11授权的，这是一个许可证。
迭代顺序可能是一个问题，这取决于T如何实现GetHashCode，但当使用uint时，这应该不是问题。另一方面，GetHashCode的默认实现在不同的实例上返回不同的值，这可能导致不同的迭代顺序。
迭代顺序也可能取决于添加项目的顺序。即，如果项目以不同顺序添加，则包含相同项目的两个集合可能以不同顺序迭代。
还有一个SortedSet<T>集合，但我不知道它有什么性能特征。
一个自定义类SparseList<T>：
- 一个列表，允许您通过将缺少的值设置为null来删除项（或者对于SparseValueList，一个特殊值，如-1（如Dr ABT的解决方案）、0（默认值（T））或int.MinValue或uint。MaxValue）和
- 则维护已删除索引的列表（堆栈<int>）。然后，当你需要添加到列表中时，它会从堆栈中弹出一个已删除的索引，并在那里添加值。（对于多线程，ConcurrentQueue<int>可能是另一种想法。）
- 枚举器可以跳过已删除的项（以支持foreach）
- 枚举过程中可以从集合中删除项！（我必须经常这样做，所以这很好。）
- 索引器提供对包含null的列表的原始访问。因此，如果使用for（；）循环，请准备过滤掉null
- 如果/当您想删除所有null时，调用Compact（）
- 如果在游戏中从不调用compact，我担心会迭代大量的null。因此，对于压缩的实验性替代方案，请参阅SparseListCleaningEnumerator：每次枚举列表时自动收缩列表，至少在单线程情况下是这样：当MoveNext从一个项移开时，它会窥视堆栈，看看索引是否更低，如果是，它会将该项分配给更低的索引，将其从当前位置删除，这将收缩列表。平衡可能需要多次迭代，并且在优化之前需要多次移动，除非用sortedlist替换堆栈，或者偶尔对堆栈进行排序。如果最后一个值为null，这将不起作用，因为索引将被隐藏在空闲索引堆栈中（用排序的东西替换堆栈可以避免这种情况）
我实现了这一点（尚未测试），但我存储的是对我的游戏实体的实际引用，而不是id，所以你需要以某种方式将其调整为int或Nullable。（好的，为了确保我回答了您问题的int/uint要求，我还添加了一个略有不同的SparseValueList<T>，使用default（T）而不是null。这意味着您不能在列表中使用0。）如果你认为自己不需要版本控制，你也许可以取消它——大多数游戏可能不需要。
/// <summary>
/// Specifying null as value has unspecified results.
/// CopyTo may contain nulls.
/// </summary>
/// <typeparam name="T"></typeparam>
public class SparseList<T> : IList<T>
where T : class
{
int version = 0;
List<T> list = new List<T>();
Stack<int> freeIndices = new Stack<int>();
public int Capacity { get { return list.Capacity; } set { list.Capacity = value; } }
public void Compact()
{
var sortedIndices = freeIndices.ToList();
foreach (var i in sortedIndices.OrderBy(x => x).Reverse())
{
list.RemoveAt(i);
}
freeIndices.Clear();
list.Capacity = list.Count;
version++; // breaks open enumerators
}
public int IndexOf(T item)
{
return list.IndexOf(item);
}
/// <summary>
/// Slow (forces a compact), not recommended
/// </summary>
/// <param name="index"></param>
/// <param name="item"></param>
public void Insert(int index, T item)
{
// One idea: remove index from freeIndices if it's in there. Stack doesn't support this though.
Compact(); // breaks the freeIndices list, so apply it before insert
list.Insert(index, item);
version++; // breaks open enumerators
}
public void RemoveAt(int index)
{
if (index == Count - 1) { list.RemoveAt(index); }
else { list[index] = null; freeIndices.Push(index); }
//version++; // Don't increment version for removals
}
public T this[int index]
{
get
{
return list[index];
}
set
{
if (value == null) throw new ArgumentNullException();
list[index] = value;
}
}
public void Add(T item)
{
if (item == null) throw new ArgumentNullException();
if (freeIndices.Count == 0) { list.Add(item); return; }
list[freeIndices.Pop()] = item;
//version++; // Don't increment version for additions? It could result in missing the new value, but shouldn't break open enumerators
}
public void Clear()
{
list.Clear();
freeIndices.Clear();
version++;
}
public bool Contains(T item)
{
if (item == null) return false;
return list.Contains(item);
}
/// <summary>
/// Result may contain nulls
/// </summary>
/// <param name="array"></param>
/// <param name="arrayIndex"></param>
public void CopyTo(T[] array, int arrayIndex)
{
list.CopyTo(array, arrayIndex);
}
//public void CopyNonNullTo(T[] array, int arrayIndex)
//{
//}
/// <summary>
/// Use this for iterating via for loop.
/// </summary>
public int Count { get { return list.Count; } }
/// <summary>
/// Don't use this for for loops! Use Count.
/// </summary>
public int NonNullCount
{
get { return list.Count - freeIndices.Count; }
}
public bool IsReadOnly
{
get { return false; }
}
public bool Remove(T item)
{
int i = list.IndexOf(item);
if (i < 0) return false;
if (i == list.Count - 1)
{
// Could throw . Could add check in
list.RemoveAt(i);
}
else
{
list[i] = null;
freeIndices.Push(i);
}
//version++; // Don't increment version for removals
return true;
}
public IEnumerator<T> GetEnumerator()
{
return new SparseListEnumerator(this);
}
private class SparseListEnumerator : IEnumerator<T>, IRemovingEnumerator
{
SparseList<T> list;
int version;
int index = -1;
public SparseListEnumerator(SparseList<T> list)
{
this.list = list;
this.version = list.version;
//while (Current == null && MoveNext()) ;
}
public T Current
{
get {
if (index >= list.Count) return null; // Supports removing last items of collection without throwing on Enumerator access
return list[index];
}
}
public void Dispose()
{
list = null;
}
object IEnumerator.Current
{
get { return Current; }
}
public bool MoveNext()
{
do
{
if (version != list.version) { throw new InvalidOperationException("Collection modified"); }
index++;
return index < list.Count;
} while (Current == null);
}
public void Reset()
{
index = -1;
version = list.version;
}
/// <summary>
/// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null.
/// </summary>
public void RemoveCurrent()
{
list.RemoveAt(index);
}
}
private class SparseListCleaningEnumerator : IEnumerator<T>, IRemovingEnumerator
{
SparseList<T> list;
int version;
int index = -1;
public SparseListCleaningEnumerator(SparseList<T> list)
{
this.list = list;
this.version = list.version;
//while (Current == null && MoveNext()) ;
}
public T Current
{
get
{
if (index >= list.Count) return null; // Supports removing last items of collection without throwing on Enumerator access
return list[index];
}
}
public void Dispose()
{
list = null;
}
object IEnumerator.Current
{
get { return Current; }
}
public bool MoveNext()
{
do
{
if (version != list.version) { throw new InvalidOperationException("Collection modified"); }
if (index > 0
&& Current != null // only works for values that are set, otherwise the index is buried in the free index stack somewhere
)
{
int freeIndex = list.freeIndices.Peek();
if (freeIndex < index)
{
list.freeIndices.Pop();
list[freeIndex] = list[index];
list.RemoveAt(index);
}
}
index++;
return index < list.Count;
} while (Current == null);
}
public void Reset()
{
index = -1;
version = list.version;
}
/// <summary>
/// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null.
/// </summary>
public void RemoveCurrent()
{
list.RemoveAt(index);
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
/// <summary>
/// Like SparseList but Supports value types, using default(T) in place of null.
/// This means values of default(T) are not permitted as values in the collection.
/// CopyTo may contain default(T).
/// TODO: Use EqualityComparer<T>.Default instead of default(T).Equals()
/// </summary>
/// <typeparam name="T"></typeparam>
public class SparseValueList<T> : IList<T>
{
int version = 0;
List<T> list = new List<T>();
Stack<int> freeIndices = new Stack<int>();
public int Capacity { get { return list.Capacity; } set { list.Capacity = value; } }
public void Compact()
{
var sortedIndices = freeIndices.ToList();
foreach (var i in sortedIndices.OrderBy(x => x).Reverse())
{
list.RemoveAt(i);
}
freeIndices.Clear();
list.Capacity = list.Count;
version++; // breaks open enumerators
}
public int IndexOf(T item)
{
return list.IndexOf(item);
}
/// <summary>
/// Slow (forces a compact), not recommended
/// </summary>
/// <param name="index"></param>
/// <param name="item"></param>
public void Insert(int index, T item)
{
// One idea: remove index from freeIndices if it's in there. Stack doesn't support this though.
Compact(); // breaks the freeIndices list, so apply it before insert
list.Insert(index, item);
version++; // breaks open enumerators
}
public void RemoveAt(int index)
{
if (index == Count - 1) { list.RemoveAt(index); }
else { list[index] = default(T); freeIndices.Push(index); }
//version++; // Don't increment version for removals
}
public T this[int index]
{
get
{
return list[index];
}
set
{
if (default(T).Equals(value)) throw new ArgumentNullException();
list[index] = value;
}
}
public void Add(T item)
{
if (default(T).Equals(item)) throw new ArgumentNullException();
if (freeIndices.Count == 0) { list.Add(item); return; }
list[freeIndices.Pop()] = item;
//version++; // Don't increment version for additions? It could result in missing the new value, but shouldn't break open enumerators
}
public void Clear()
{
list.Clear();
freeIndices.Clear();
version++;
}
public bool Contains(T item)
{
if (default(T).Equals(item)) return false;
return list.Contains(item);
}
/// <summary>
/// Result may contain default(T)'s
/// </summary>
/// <param name="array"></param>
/// <param name="arrayIndex"></param>
public void CopyTo(T[] array, int arrayIndex)
{
list.CopyTo(array, arrayIndex);
}
//public void CopyNonNullTo(T[] array, int arrayIndex)
//{
//}
/// <summary>
/// Use this for iterating via for loop.
/// </summary>
public int Count { get { return list.Count; } }
/// <summary>
/// Don't use this for for loops! Use Count.
/// </summary>
public int NonNullCount
{
get { return list.Count - freeIndices.Count; }
}
public bool IsReadOnly
{
get { return false; }
}
public bool Remove(T item)
{
int i = list.IndexOf(item);
if (i < 0) return false;
if (i == list.Count - 1)
{
// Could throw . Could add check in
list.RemoveAt(i);
}
else
{
list[i] = default(T);
freeIndices.Push(i);
}
//version++; // Don't increment version for removals
return true;
}
public IEnumerator<T> GetEnumerator()
{
return new SparseValueListEnumerator(this);
}
private class SparseValueListEnumerator : IEnumerator<T>, IRemovingEnumerator
{
SparseValueList<T> list;
int version;
int index = -1;
public SparseValueListEnumerator(SparseValueList<T> list)
{
this.list = list;
this.version = list.version;
//while (Current == default(T) && MoveNext()) ;
}
public T Current
{
get
{
if (index >= list.Count) return default(T); // Supports removing last items of collection without throwing on Enumerator access
return list[index];
}
}
public void Dispose()
{
list = null;
}
object IEnumerator.Current
{
get { return Current; }
}
public bool MoveNext()
{
do
{
if (version != list.version) { throw new InvalidOperationException("Collection modified"); }
index++;
return index < list.Count;
} while (default(T).Equals(Current));
}
public void Reset()
{
index = -1;
version = list.version;
}
/// <summary>
/// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T).
/// </summary>
public void RemoveCurrent()
{
list.RemoveAt(index);
}
}
private class SparseValueListCleaningEnumerator : IEnumerator<T>, IRemovingEnumerator
{
SparseValueList<T> list;
int version;
int index = -1;
public SparseValueListCleaningEnumerator(SparseValueList<T> list)
{
this.list = list;
this.version = list.version;
while (default(T).Equals(Current) && MoveNext()) ;
}
public T Current
{
get
{
if (index >= list.Count) return default(T); // Supports removing last items of collection without throwing on Enumerator access
return list[index];
}
}
public void Dispose()
{
list = null;
}
object IEnumerator.Current
{
get { return Current; }
}
public bool MoveNext()
{
do
{
if (version != list.version) { throw new InvalidOperationException("Collection modified"); }
if (index > 0
&& (!default(T).Equals(Current)) // only works for values that are set, otherwise the index might be buried in the stack somewhere
)
{
int freeIndex = list.freeIndices.Peek();
if (freeIndex < index)
{
list.freeIndices.Pop();
list[freeIndex] = list[index];
list.RemoveAt(index);
}
}
index++;
return index < list.Count;
} while (default(T).Equals(Current));
}
public void Reset()
{
index = -1;
version = list.version;
}
/// <summary>
/// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T).
/// </summary>
public void RemoveCurrent()
{
list.RemoveAt(index);
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}