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;
         }
   }
}

要素への割り当ては、新しいオブジェクトを新しくするよりも高速であり、たとえば内部配列がどのように満たされているかに依存するため、パフォーマンスに関しては、事前に割り当てられた配列を使用する実装よりも遅くなります。リストは、これは実際にはより多くのスペースを占有する可能性がありますが、そのオーバーヘッドは、毎回新しい配列を 1 つの要素だけで新しくすることによってパフォーマンスと引き換えにできますが、パフォーマンスに関してはかなりのオーバーヘッドがあります。また、ほとんどの場合にメモリを過剰に割り当てるが、ほとんどの場合にパフォーマンスを向上させる多くの新しい要素に十分なスペースを確保する 2 つの間のバランスを選択することもできます。

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;
         }
   }
}

基本的に、リストなどのコレクションが持つバランスに戻ります。これは、多くの場合メモリを無駄にせずに高速追加を可能にするには大きすぎる内部配列に基づいて構築されています。

したがって、すべての最適化の質問と同様に、何を最適化するかによって異なります。パフォーマンスを犠牲にしても構わないと思っている場合は、多くの場合、メモリを最適化できます。

于 2012-05-30T12:35:17.227 に答える
2

コレクションには正確に何を保存していますか？それがタイプ ( T)の場合List<T>、最善の策は「はい」です。

非ジェネリック型の場合はHashSet、を使用することを検討してください。特定のケースでは、パフォーマンスが大幅に向上する可能性があります。

AS @RuneFS が言ったように、反復と配置を求めています。HashSet の反復は List の反復と同じですが、オブジェクトを HashSet に追加するのはリストに追加するよりも遅く (ハッシュを比較)、機能的にも同等ではありません (ハッシュセットの個別のハッシュ)。

于 2012-05-30T11:47:37.567 に答える