.NET には多くの複雑なデータ構造があります。残念ながら、それらのいくつかは非常によく似ており、あるものをいつ使用し、いつ別のものを使用するかは常にわかりません. 私の C# と VB の本のほとんどは、それらについてある程度説明していますが、実際の詳細についてはまったく触れていません。
Array、ArrayList、List、Hashtable、Dictionary、SortedList、SortedDictionary の違いは何ですか?
列挙可能なものはどれですか (IList -- 'foreach' ループを実行できます)? キーと値のペア (IDict) を使用するのはどれですか?
メモリフットプリントはどうですか？挿入速度？取得速度は？
言及する価値のある他のデータ構造はありますか?
メモリ使用量と速度 (Big-O 表記法) の詳細についてはまだ調査中です。
私の頭の上から：
Array* - 古い学校のメモリ配列を表します - 通常の配列のエイリアスのようなものtype[]です。列挙できます。自動的に成長することはできません。挿入と取得の速度が非常に速いと思います。
ArrayList- 自動的に成長する配列。オーバーヘッドが追加されます。列挙できます。おそらく通常の配列より遅いですが、それでもかなり高速です。これらは .NET でよく使用されます
List-私のお気に入りの1つ-ジェネリックで使用できるため、厳密に型指定された配列を使用できますList<string>。それ以外は、非常によく似ていますArrayList
Hashtable- 普通の古いハッシュテーブル。O(1) から O(n) の最悪のケース。値とキーのプロパティを列挙し、キーと値のペアを実行できます
Dictionary- 上記と同じで、次のようなジェネリックを介してのみ強く型付けされますDictionary<string, string>
SortedList- ソートされた汎用リスト。物を置く場所を把握する必要があるため、挿入が遅くなります。並べ替える必要がないため、おそらく検索時に同じですが、削除は単純な古いリストよりも遅くなります。
List私は常にandを使用する傾向がありDictionaryます-ジェネリックで強く型付けされたものを使い始めると、標準の非ジェネリックに戻るのは非常に困難です。
他にもたくさんのデータ構造がありKeyValuePairます。興味深いことを行うために使用できるものや、SortedDictionary同様に役立つ可能性のある があります。
可能であれば、ジェネリックを使用してください。 これも：
まず、.NET のすべてのコレクションは IEnumerable を実装しています。
次に、フレームワークのバージョン 2.0 でジェネリックが追加されたため、多くのコレクションが重複しています。
したがって、一般的なコレクションは機能を追加する可能性がありますが、ほとんどの場合:
配列は、特定のインデックスに格納されている値を変更できる固定サイズのコレクションです。
SortedDictionary は、キーに基づいてソートされる IDictionary<T,K> です。SortedList は、必要な IComparer に基づいて並べ替えられる IDictionary<T,K> です。
したがって、IDictionary の実装 (KeyValuePairs をサポートするもの) は次のとおりです。
.NET 3.5 で追加された別のコレクションは、ハッシュセットです。集合操作をサポートするコレクションです。
また、LinkedList は、標準のリンク リストの実装です (List は、取得を高速化するための配列リストです)。
ここにあなたのためのいくつかの一般的なヒントがあります：
foreachを実装する型で使用できますIEnumerable。IList基本的にIEnumberablewithCountおよびItem（ゼロベースのインデックスを使用してアイテムにアクセスする）プロパティです。IDictionary一方、ハッシュ可能なインデックスでアイテムにアクセスできることを意味します。
Array、ArrayListおよびListすべてが実装しIListます。
Dictionary、、SortedDictionaryおよびをHashtable実装しIDictionaryます。
.NET 2.0以降を使用している場合は、前述のタイプの一般的な対応物を使用することをお勧めします。
これらのタイプのさまざまな操作の時間とスペースの複雑さについては、それらのドキュメントを参照してください。
.NETデータ構造はSystem.Collections名前空間にあります。追加のデータ構造を提供するPowerCollectionsなどのタイプライブラリがあります。
データ構造を完全に理解するには、CLRSなどのリソースを参照してください。
あるユーザーが述べているように、配列は「古い学校」のコレクションです (はい、配列は の一部ではありませんが、コレクションと見なされますSystem.Collections)。しかし、他のコレクション、つまりタイトルにリストしたもの (ここでは ArrayList と List(Of T)) と比較して、配列についての「古い学校」とは何ですか? 配列を見て基本から始めましょう。
まず、Microsoft .NET の配列は、「複数の [論理的に関連する] アイテムを 1 つのコレクションとして扱うことを可能にするメカニズム」です (リンクされた記事を参照)。どういう意味ですか？配列は、個々のメンバー (要素) を順番に格納し、開始アドレスを使用してメモリ内に 1 つずつ順番に格納します。配列を使用することで、そのアドレスから順番に格納された要素に簡単にアクセスできます。
それを超えて、101 の一般的な概念をプログラミングすることに反して、配列は実際には非常に複雑になる可能性があります。
配列は、1 次元、多次元、またはジャッド配列にすることができます (ジャグ配列については、読む価値があります)。配列自体は動的ではありません。初期化されると、 nサイズの配列は、 n個のオブジェクトを保持するのに十分なスペースを予約します。配列内の要素の数は増減できません。Dim _array As Int32() = New Int32(100)配列が 100 個の Int32 プリミティブ型オブジェクトを格納できるようにメモリ ブロックに十分なスペースを予約します (この場合、配列は 0 を格納するように初期化されます)。このブロックのアドレスが に返され_arrayます。
この記事によると、共通言語仕様(CLS) では、すべての配列が 0 から始まる必要があります。.NET の配列は、非ゼロ ベースの配列をサポートします。ただし、これはあまり一般的ではありません。ゼロから始まる配列の「共通性」の結果として、Microsoft はパフォーマンスの最適化に多くの時間を費やしてきました。したがって、1 次元のゼロベース (SZ) 配列は「特別」であり、(多次元などとは対照的に) 配列の実際の実装としては最適です。SZ には、それらを操作するための特定の中間言語命令があるためです。
配列は常に参照によって (メモリ アドレスとして) 渡されます。これは、知っておくべき配列パズルの重要なピースです。それらは境界チェックを行いますが (エラーをスローします)、配列で境界チェックを無効にすることもできます。
繰り返しになりますが、配列の最大の障害は、サイズを変更できないことです。それらには「固定」容量があります。ArrayList と List(Of T) を歴史に紹介します。
ArrayList (いくつかのList(Of T)重要な違いがありますが、ここでは後で説明します) は、(広い意味で) コレクションへの次の追加としておそらく最もよく考えられています。ArrayList は、IList ('ICollection' の子孫) インターフェイスから継承します。ArrayLists 自体は、Listsよりもかさばり、より多くのオーバーヘッドが必要です。
IListArrayLists を固定サイズのリスト (Arrays など) として処理する実装を有効にします。ただし、ArrayLists によって追加された追加の機能を超えて、固定サイズの ArrayLists を使用しても実際の利点はありません。この場合、ArrayLists (Arrays よりも) は著しく遅くなります。
私の読書から、ArrayListsはギザギザにすることはできません：「多次元配列を要素として使用する...サポートされていません」。繰り返しますが、ArrayLists の棺桶に別の釘が刺さっています。ArrayList も「型指定」されていません。つまり、すべての下にある ArrayList は、単純にオブジェクトの動的配列ですObject[]。これには、ArrayLists を実装するときに多くのボックス化 (暗黙的) およびボックス化解除 (明示的) が必要であり、これもオーバーヘッドに追加されます。
根拠のない考え: ArrayLists は、Arrays から List-type Collections に移行しようとする試みの概念的な子のようなものであると読んだり、教授の 1 人から聞いたりしたことを覚えていると思います。コレクションに関してさらなる開発が行われたため、それらはもはや最良の選択肢ではありません
メモリ使用量の違いは、List(Of Int32) が同じプリミティブ型を含む ArrayList よりも 56% 少ないメモリを消費するほど十分に重要です (上記の紳士のリンクされたデモンストレーションでは 8 MB 対 19 MB : 再びここにリンクされています) - ただしこれは、64 ビット マシンによって複合化された結果です。この違いは 2 つのことを示しています。まず (1)、ボックス化された Int32 型の「オブジェクト」(ArrayList) は、純粋な Int32 プリミティブ型 (List) よりもはるかに大きくなります。2 番目 (2)、違いは 64 ビット マシンの内部動作の結果として指数関数的です。
では、違いは何ですか? List(Of T)とは何ですか? MSDNはList(Of T)、「... インデックスによってアクセスできる厳密に型指定されたオブジェクトのリスト」と定義しています。ここで重要なのは、「厳密に型指定された」ビットです。List(Of T) は型を「認識」し、オブジェクトをその型として格納します。したがって、 anは型ではなくInt32として格納されます。これにより、ボックス化とボックス化解除によって引き起こされる問題が解消されます。Int32Object
MSDN では、参照型ではなくプリミティブ型を格納する場合にのみ、この違いが生じると規定しています。また、違いは実際には大規模に発生します: 500 以上の要素です。さらに興味深いのは、MSDN のドキュメントに、「ArrayList クラスを使用する代わりに、List(Of T) クラスの型固有の実装を使用する方が有利です....」と書かれていることです。
基本的に、List(Of T) は ArrayList ですが、より優れています。これは、ArrayList の「一般的な同等物」です。ArrayList と同様に、ソートされるまでソートされることは保証されません (図を参照)。List(Of T) には、いくつかの追加機能もあります。
私は質問に共感します-私も選択が当惑するのを見つけました（見つけましたか？）ので、どちらのデータ構造が最速であるかを科学的に調べました（私はVBを使用してテストを行いましたが、C＃は両方の言語で同じになると思いますCLRレベルでも同じことを行います）。ここで私が行ったベンチマーク結果を見ることができます（どのデータ型がどの状況で使用するのが最適かについての議論もあります）。
それらはインテリセンスでかなりうまく綴られています。System.Collectionsと入力するだけです。またはSystem.Collections.Generics (推奨) を使用すると、利用可能なものの一覧と簡単な説明が表示されます。
ジェネリック コレクションは、特に多くのアイテムを反復処理する場合に、非ジェネリック コレクションよりもパフォーマンスが高くなります。これは、ボックス化とボックス化解除が行われなくなったためです。
ハッシュテーブル/辞書は O(1) パフォーマンスです。つまり、パフォーマンスはサイズの関数ではありません。それは知っておくことが重要です。
編集: 実際には、Hashtable/Dictionary<> ルックアップの平均時間の複雑さは O(1) です。
高頻度の体系的な取引エンジニアリングのための Hashtable と Dictionary に関する重要な注意事項: スレッドの安全性の問題
Hashtable は、複数のスレッドで使用できるスレッド セーフです。Dictionary public static メンバーはスレッド セーフですが、インスタンス メンバーはスレッド セーフであるとは限りません。
したがって、Hashtable はこの点で「標準」の選択のままです。
最も一般的な C# データ構造とコレクション
C#.NETにはさまざまなデータ構造があります。たとえば、最も一般的なものの 1 つは配列です。ただし、C# にはさらに多くの基本的なデータ構造が付属しています。適切に構造化された効率的なプログラムを作成するには、使用する正しいデータ構造を選択する必要があります。
この記事では、C#.NET 3.5 で導入された新しいものを含め、組み込みの C# データ構造について説明します。これらのデータ構造の多くは、他のプログラミング言語にも適用されることに注意してください。
配列
おそらく最も単純で最も一般的なデータ構造は配列です。AC# 配列は、基本的にオブジェクトのリストです。その決定的な特徴は、すべてのオブジェクトが (ほとんどの場合) 同じ型であり、特定の数のオブジェクトがあることです。配列の性質により、リスト内の位置 (インデックスとも呼ばれます) に基づいて要素に非常に高速にアクセスできます。AC# 配列は次のように定義されます。
[object type][] myArray = new [object type][number of elements]
いくつかの例：
int[] myIntArray = new int[5];
int[] myIntArray2 = { 0, 1, 2, 3, 4 };
上記の例からわかるように、配列は要素なしで、または既存の値のセットから初期化できます。値が収まる限り、配列への値の挿入は簡単です。配列のサイズよりも多くの要素がある場合、操作のコストが高くなり、その時点で配列を拡張する必要があります。既存のすべての要素を新しいより大きな配列にコピーする必要があるため、これには時間がかかります。
配列リスト
C# データ構造 ArrayList は動的配列です。つまり、ArrayList は任意の数の任意の型のオブジェクトを持つことができます。このデータ構造は、新しい要素を配列に追加するプロセスを簡素化するために設計されました。内部的には、ArrayList は、スペースがなくなるたびにサイズが 2 倍になる配列です。内部配列のサイズを 2 倍にすることは、長期的には要素のコピーの量を減らす非常に効果的な戦略です。ここではその証明には入りません。データ構造は非常に簡単に使用できます。
ArrayList myArrayList = new ArrayList();
myArrayList.Add(56);
myArrayList.Add("String");
myArrayList.Add(new Form());
ArrayList データ構造の欠点は、取得した値を元の型にキャストする必要があることです。
int arrayListValue = (int)myArrayList[0]
ここで見つけることができるソースと詳細情報：
ジェネリックコレクションと非ジェネリックコレクションの間には、微妙な違いとそれほど微妙ではない違いがあります。それらは単に異なる基礎となるデータ構造を使用します。たとえば、Hashtableは、同期なしで1人のライターと多くのリーダーを保証します。辞書はしません。