.NETコレクションクラス

Question

パーツリストなどの関連データのグループは、配列（Array of Parts）またはCollectionを使用して処理できます。配列を使用すると、挿入、削除などの操作は、コレクションと比較するとパフォーマンスに影響を与えます。これは、配列がコレクションによって内部的に使用されていないことを意味しますか？そうであれば、List、Collectionなどのコレクションに使用されるデータ構造は何ですか？

コレクションは内部でどのように処理されますか？

Answer 1

シンプルなコレクションを実装するには、2つの基本的な方法があります。

• 連続した配列
• リンクリスト

連続配列はあなたが言及した操作のパフォーマンスの欠点を持っているがためのメモリ空間コレクションは、事前に割り当てられているか、コレクションの内容に基づいて割り当てられています。したがって、削除または挿入は、コレクション全体を連続して適切な順序に保つために、多くの配列要素を移動する必要があります。

リンクされたリストは、コレクション内の項目を連続してメモリに格納する必要がないため、これらの問題を取り除きます。代わりに、各要素には、1つ以上の他の要素への参照が含まれています。したがって、挿入が行われると、問題の項目はメモリ内の任意の場所に作成され、コレクション内に既に存在する要素の1つまたは2つの参照のみが変更される必要があります。例えば

：

LinkedList<object> c = new LinkedList<object>(); // a linked list 
object[] a = new object[] { }; // a contiguous array 

もちろん、これは簡略化されます。 LinkedList<>の内部構造は、単なる単一または二重にリンクされたリストよりも複雑なものではありませんが、それは基本的な構造です。

Answer 2

List<T>は内部配列を使用します。内部配列の内容全体を一方向にシフトする必要があるため、リストの先頭付近で項目を削除/挿入すると、リストの終わり近くで項目を削除するよりもコストがかかります。また、内部リストが一杯になったときに項目を追加しようとすると、新しい大きな配列が作成され、内容がコピーされ、古い配列は破棄されます。

クラスは、パラメータのないコンストラクタで使用される場合、List<T>を内部的に使用します。したがって、ラッピングによるオーバーヘッドを除いて、パフォーマンスは同じです。 （本質的にもう1つのレベルのインダイレクションは、ほとんどのシナリオで無視できる程度です）。

LinkedList<T>は、その名前が示すように、リンクリストです。これは挿入/除去速度のために反復速度を犠牲にする。反復はポインターからポインターへのポインタを無限に移動することを意味するので、これは全体的にもっと多くの作業を必要とします。ポインタトラバーサルとは別に、2つのノードを互いに近くに配置することはできないため、CPU RAMキャッシュの有効性が低下する可能性があります。

ただし、ノードの挿入または削除に必要な時間は、リストの状態に関係なく同じ数の操作を必要とするため、一定です。 （これは、削除するアイテムを実際に見つけるために行う必要がある作業を考慮しないか、挿入ポイントを見つけるためにリストをたどります！）

あなたのコレクションの主な関心事が、コレクションは、代わりにHashSet<T>と考えられます。セットへのアイテムの追加は比較的速く、リストとリンクされたリストへの挿入の間のどこかになります。アイテムの削除は再び比較的速くなります。しかし、実際の利益は検索時間にあります。HashSet<T>に項目が含まれている場合、リスト全体を反復する必要はありません。平均的には、どのリストやリンクリスト構造よりも高速に実行されます。

ただし、HashSet<T>には同等の項目を含めることはできません。あなたの要求の一部が、均等とみなされる（Object.Equals(Object)過負荷によって、またはIEquatable<T>を実装することによって）2つのアイテムがコレクション内に独立して共存する場合、単にHashSet<T>を使用することはできません。また、HashSet<T>は、挿入オーダーを保証していないため、何らかの並べ替えを維持することが重要な場合はHashSet<T>も使用できません。

Answer 3

コレクションクラスの中には、内部的にもリンクされたリストなどでも、配列を使用するものがあると思います。配列の代わりにSystem.Collections名前空間のコレクションを使用する利点は、更新操作を実行するためのコードを書く時間を追加する必要がないことです。

配列は常に軽量になります。非常に優れた検索アルゴリズムが分かっている場合は、さらに効率的に使用できるかもしれませんが、システムのクラスを使用してホイールの再発明を避けることができます。コレクション。これらのクラスは、すでに書かれたコードを何度も書くのを避けるためのものです。そのため、あなた自身で配列を操作することでパフォーマンスが大幅に向上することはありません。

多くの追加、削除、編集を必要としないスタティックコレクションが必要な場合は、コレクションが行う余分なメモリを必要としないため、おそらく配列を使用するのがよいでしょう。