16

我想知道 .NET 中的集合实现有什么区别。

例如,我经常使用List<int>etc 来存储项目列表。但是我只需要一个物品容器,我想我不需要所有的功能List。我只需要一个包含put方法的容器,并允许客户端代码遍历容器。

IEnumerable<T>有没有在 .NET中实现的更快、更轻量级的集合实现?

4

3 回答 3

9

实现的最轻量级的容器IEnumerable<T>是类型化数组。它没有Add方法(因此不会像列表那样动态调整大小),但是如果您预先知道想要多少元素,您可以定义数组并在给定位置插入元素。

var myArray = new int[10];
myArray[0] = 123;
myArray[1] = 234;
于 2012-05-30T11:51:47.340 回答
5

如果您只需要添加和迭代,我相信链表是最轻量级的。我还没有看过 Stack 的实现,很容易创建一个不需要太多空间的。这是一个相当幼稚的解决方案,可以针对大小进行优化。我的观点是实现轻量级集合很简单

public class Stack<T>{
   readonly T _head;
   readonly Stack<T> _tail;
   public Stack(T head,Stack<T> tail){
       _head = head;
       _tail = tail;
   }

   public Stack<T> Push(T element){
       return new Stack<T>(element,this);
   }

   public IEnumerator<T> GetEnumerator(){
         yield return _head;
         var current = _tail;
         while(_tail != null){
             yield return current._head;
             current = current._tail;
         }
   }
}

在性能方面,这将比使用预分配数组的实现慢,因为分配给一个元素比新建一个新对象要快,并且取决于例如如何填充内部数组。清单是这实际上可能会占用更多空间,但是可以通过每次只使用一个新元素来更新一个新数组来换取性能开销,但这在性能方面具有显着的开销。您还可以选择两者之间的平衡,在大多数情况下为许多新元素保留足够的空间会过度分配内存,但在大多数情况下会提高性能。

public class Stack<T>{
   T[] _heads;
   T[] _tail;
   int _next;
   public Stack(T head,T[] tail){
       _heads = new T[tail.length];
       _next = _heads.Length -2; 
       _heads[_heads.Length -1] = head;
       _tail = tail;
   }

   public void Push(T element){
        if(_next < 0){
            var length = _heads.Length;
            var _new = new T[length * 2];
            _heads = new T[length * 2];                
            _next = length * 2-1;
            Array.Copy(_heads,_new,length);
            Array.Copy(_tails,0,_new,length,length);
            _tails = _new;
        } else{
            _heads[_next--] = element;
        }
   }

   public IEnumerator<T> GetEnumerator(){
         yield return _head;
         var current = _tail;
         while(_tail != null){
             yield return current._head;
             current = current._tail;
         }
   }
}

并且您基本上回到了 List 等集合所具有的平衡。它建立在一个内部阵列上,该阵列通常太大而无法在不浪费太多内存的情况下进行高速添加。

因此,与所有优化问题一样,它实际上取决于您希望优化的内容。如果您愿意牺牲性能,您通常可以优化内存,反之亦然

于 2012-05-30T12:35:17.227 回答
2

您究竟在收藏中存储了什么?如果它是一个类型 ( T),那么List<T>你最好的选择是。

对于非泛型类型,考虑使用 a HashSet,它们在某些情况下可以显着提高性能。

正如@RuneFS 所说,正如您要求迭代和放置一样。迭代 HashSet 与迭代 List 是相等的(ish),但是将对象添加到 HashSet 比将其添加到列表中要慢(比较哈希),并且功能也不等效(哈希集中的不同哈希)。

于 2012-05-30T11:47:37.567 回答