2

我需要一种只能按顺序访问的快速集合类型。它需要快速添加和快速清除。我认为有一些集合类型可以用很少的处理时间来清除。

我读过这List<>是 O(n) 操作。有没有超快速清除能力的收藏类型？也许是一个堆栈？List<int>or List<Double>（非引用类型）是否允许更快的操作？

4

4 回答 4

4

O(n) 是您搜索的时候。如果您使用 Enumerable （也许是我不知道该部分的索引器）逐步浏览列表，它将是 O(1) 查找。清算也是 O(1)，只要你不Remove(T obj)打电话Clear()就会非常快。清除仍然是 O(n)。

如果您不需要可调整大小，只需声明一个数组将有一个 O(1) 索引器并“清除”它，您只需取消引用它并创建一个新的。

于 2012-11-17T06:18:03.233 回答
2

如果您的主要目标是 O(1) 明确 - 只需将任何合适的集合（List、LinkedList、Array）作为您的 cusomt 类的成员实现IList或ICollection转发索引/迭代到该成员。要实现清晰的简单创建该内部成员的新实例。

class FastClearList<T> : IList<T>
{
  List<T> inner = new List<T>();

  public void Clear()
  {
     inner = new List<T>(); // recreating list here will give O(1)
  }

  public IEnumerator<T> GetEnumerator()
  {
     return inner.GetEnumerator();
  }
  // forward everything else ...
}
于 2012-11-17T06:42:44.973 回答
2

如果您确实需要快速清除并且不想每次都分配新的内存，您还可以通过简单地将内部计数器重置为 0 来编写自己的 O(1) 实现。IList<T>该类保持一个确定列表当前位置的计数器，要重置您可以在自己的实现中将其设置为 0。内部数组不会真正被清除，但添加到列表中的任何项目都会覆盖旧值，并且枚举不会继续过去，因此您永远不会触及旧值。ClearList<T>_size_size

本质上，您希望List<T>where Countis settable 为 0 而不仅仅是 gettable。

但请注意，如果T是引用类型，这种列表将保存对旧值的引用，并防止它们被垃圾收集。因此，也许只有在您想存储值类型时才最好使用。

于 2012-11-17T17:49:55.157 回答
0

List 确实需要清除对已清除对象的引用。最好的方法是创建一个新的 List<> 而不是清除它，或者创建一个实现这种方法的包装器/工厂。

于 2012-11-17T21:37:32.337 回答