7

次のような一般的に使用されるコレクションの内部実装に関する情報を見つけることができる良いリファレンス（Webサイトまたはさらに良い本）があるかどうか疑問に思っていました

  • Dictionary<TKey, TValue>
  • List<T>
  • Queue<T>
  • Stack<T>
  • 等

内部実装とは、動的配列を使用してデータを保存する方法、サイズ変更の頻度、一般的な操作の時間と空間の複雑さを意味します。

もちろん、このスレッドでこの情報を提供できると感じている人がいれば、大歓迎です!

4

2 に答える 2

3

約List<T>:

List<T>には 2 つのプロパティがCapacityありCount、サイズ変更がいつ行われるかを明確にするのに役立ちます。Capacity任意の時点での内部配列の長さでありCount、List に追加された要素の数です。リストに追加する要素の推定数がある場合は、Capacity(適切なコンストラクターを選択して) 初期化できます。これにより、サイズ変更が少なくなるか、まったくなくなり、パフォーマンスが向上します。

サイズ変更 (つまり、新しい大きな配列の作成と新しい配列への要素の 1 つずつのコピー) は、Add<T>()メソッドが呼び出され、配列が既にいっぱいになっている場合に発生します ( Count == Capacity)。新しい配列の容量は 2 倍になります (最初は、ユーザーが設定していない場合、0 から始まり、次に 4 になり、さらにスペースが必要になるたびに 2 倍になります)。

List<int> list = new List<int>();
//Capacity = 0, Count = 0

list.Add(52);
//Capacity = 4, Count = 1

list.Add(34);
list.Add(2);
list.Add(87);
//Capacity = 4, Count = 4

list.Add(56);
//Capacity = 8, Count = 5

大きなの場合、新しい要素を追加するためnの時間の計算量は償却定数O(1)です。インデックスによる検索は定数O(1)であり、指定されたインデックスでの要素の挿入または削除は線形O(n)です。これは、残りの要素を 1 位置 (それぞれ右または左) にシフトする必要があるためです。内部配列に使用されるスペースはもちろん、配列の要素に対して線形であり、nから2n(または、これが理にかなっている場合: Math.Pow(2, Math.Ceiling(Math.Log(n, 2))):) まで変化します。

についてQueue<T>とStack<T>:

Queue と Stack の内部配列のサイズ変更は、 について説明したものと同様に機能しList<T>ます。一般的な操作は効率的なO(1)です(内部的には、Queue の先頭要素と末尾要素のインデックスが保持されます)。そのため、要素をキューに入れるか、スタックにプッシュするには、償却された一定の時間が必要であり、デキュー/ポップには一定の時間が必要です。

約Dictionary<TKey, TValue>:

Dictionary の動作は異なりますが、ここでうまく説明されています。

于 2013-04-01T22:55:37.180 に答える
1

これらのそれぞれの正確な実装の詳細については、(それぞれについて) 長い説明が必要です。代わりに、J. Albahari の本 C# 5.0 In a Nutshell を参照してください。

ただし、辞書クラスの一般的な操作のメモリ/時間に関する考慮事項の表を提供できます。これらのパフォーマンス時間はミリ秒単位であり、1.5GHz PC で整数のキーと値を持つディクショナリに対して 50,000 回の操作を実行します。

Type                Internal         Retrieve by     Memeory         Speed Random        Speed Seq        Speed Retrieval 
                    Structure        Index?          Overhead        Insertion           Insertion        by Key
Unsorted
Dictionary<T>       Hashtable        No              22              30                  30               20
Hashtable           Hashtable        No              38              50                  50               30
ListDictonary       Linked List      No              36              50,000              50,000           50,000
OrderedDictionary   Hashtable +      Yes             59              70                  70               40
                    Array
Sorted
SortedDictionary    Red-Black        No              20              130                 100              120 
<K, V>              Tree
SortedList <K, V>   2xArray          Yes             2               3,300               30               40
SortedList          2xArray          Yes             27              4,500               100              180

申し訳ありませんが、あなたが必要とする他の人にこれを提供することはできません.

これが何かの役に立てば幸いです。

于 2012-09-06T10:27:03.607 に答える