.NET データ構造:ArrayList、List、HashTable、Dictionary、SortedList、SortedDictionary — 速度、メモリ、そしてそれぞれをいつ使用するか?

https://stackoverflow.com/questions/128636

02-07-2019
|

質問

.NET には複雑なデータ構造が多数あります。残念ながら、それらの中には非常に似ているものもあり、どのような場合に一方を使用し、いつ別の機能を使用するかが常にわかりません。私の C# および Visual Basic の本のほとんどは、それらについてある程度説明していますが、実際の詳細にはまったく触れていません。

Array、ArrayList、List、Hashtable、Dictionary、SortedList、SortedDictionary の違いは何ですか?

どれが列挙可能ですか (IList -- 'foreach' ループを実行できます)?キーと値のペア (IDict) を使用するものはどれですか?

メモリ使用量についてはどうですか?挿入速度は？取得速度は？

他に言及する価値のあるデータ構造はありますか?

メモリ使用量と速度 (Big-O 表記) の詳細については、まだ調査中です。

解決

私の頭の上から：

Array* - 古い学校のメモリ配列を表します - 通常のメモリ配列のエイリアスのようなもの type[] 配列。列挙できる。自動的に成長することはできません。挿入と取得の速度が非常に速いと思います。
ArrayList - 自動的に拡張される配列。さらにオーバーヘッドが追加されます。enum できます。おそらく通常の配列より遅いですが、それでもかなり高速です。これらは .NET でよく使用されます
List - 私のお気に入りの 1 つ - ジェネリックスと一緒に使用できるため、厳密に型指定された配列を使用できます。 List<string>. 。それ以外は、非常によく似た動作をします ArrayList
Hashtable - 単純な古いハッシュテーブル。O(1) ～ O(n) の最悪のケース。値とキーのプロパティを列挙し、キーと値のペアを実行できます。
Dictionary - 上記と同様、ジェネリックを介してのみ強く型付けされます。 Dictionary<string, string>
SortedList - ソートされた汎用リスト。どこに物を入れるかを判断する必要があるため、挿入が遅くなります。enum. は可能で、再検索する必要がないため、おそらく取得でも同じですが、削除は単純な古いリストよりも遅くなります。

私がよく使うのは List そして Dictionary 常に - ジェネリックで強く型付けされたものを使い始めると、標準の非ジェネリックのものに戻るのは非常に困難です。

他にもたくさんのデータ構造があります。 KeyValuePair いくつかの興味深いことを行うために使用できます。 SortedDictionary これも役に立ちます。

他のヒント

可能であれば、ジェネリック医薬品を使用してください。 これも：

ArrayList の代わりに List
ハッシュテーブルの代わりに辞書

まず、.NET のすべてのコレクションは IEnumerable を実装します。

次に、フレームワークのバージョン 2.0 でジェネリックが追加されたため、多くのコレクションが重複しています。

したがって、汎用コレクションには機能が追加される可能性がありますが、ほとんどの場合、次のとおりです。

List は ArrayList の汎用実装です。
ディクショナリは Hashtable の汎用実装です

配列は、特定のインデックスに格納されている値を変更できる固定サイズのコレクションです。

SortedDictionary は、キーに基づいて並べ替えられる IDictionary です。SortedList は、必要な IComparer に基づいて並べ替えられる IDictionary です。

したがって、IDictionary 実装 (KeyValuePairs をサポートするもの) は次のとおりです。* hashtable * dictionary * sortedlist * sorteddictionary

.NET 3.5 で追加されたもう 1 つのコレクションは、ハッシュセットです。集合演算をサポートするコレクションです。

また、LinkedList は標準のリンクリスト実装です (List は高速に取得するための配列リストです)。

良いチートシートデータ構造、アルゴリズムなどの複雑さについて言及します。

ここでは、一般的なヒントをいくつか紹介します。

使用できます foreach 実装する型について IEnumerable. IList 本質的には IEnumberable と Count そして Item (ゼロから始まるインデックスを使用して項目にアクセスする) プロパティ。 IDictionary 一方、任意のハッシュ可能インデックスによって項目にアクセスできることを意味します。
Array, ArrayList そして List すべて実装する IList. Dictionary, SortedDictionary, 、そして Hashtable 埋め込む IDictionary.
.NET 2.0 以降を使用している場合は、前述のタイプの汎用のものを使用することをお勧めします。
これらのタイプに対するさまざまな操作の時間と空間の複雑さについては、ドキュメントを参照してください。
.NET データ構造は次のとおりです。 System.Collections 名前空間。などのタイプライブラリがあります。パワーコレクション追加のデータ構造を提供します。
データ構造を完全に理解するには、次のリソースを参照してください。 CLRS.

.NET データ構造:

ArrayList と List が実際に異なる理由についての詳細

配列

あるユーザーが述べているように、配列は「昔ながらの」コレクションです (はい、配列はコレクションの一部ではありませんが、コレクションとみなされます) System.Collections）。しかし、他のコレクション、つまりタイトルに挙げたコレクション (ここでは ArrayList と List(Of T)) と比較して、配列について何が「古い」のでしょうか?配列を見て基本から始めましょう。

始めること、配列 Microsoft .NET の機能は、「複数の [論理的に関連した] 項目を 1 つのコレクションとして扱うことを可能にするメカニズム」です (リンク先の記事を参照)。それはどういう意味ですか？配列は、個々のメンバー (要素) を開始アドレスとともにメモリ内に順番に格納します。配列を使用すると、そのアドレスから順番に格納された要素に簡単にアクセスできます。

それを超えて、101 の一般的な概念のプログラミングとは対照的に、配列は実際には非常に複雑になる可能性があります。

配列には、単一次元、多次元、またはギザギザの配列があります (ギザギザの配列については読む価値があります)。配列自体は動的ではありません。初期化されると、次の配列 n サイズは保持するのに十分なスペースを確保します n オブジェクトの数。配列内の要素の数は増減できません。 Dim _array As Int32() = New Int32(100) 配列に 100 個の Int32 プリミティブ型オブジェクトを含めるのに十分なスペースをメモリブロック上に予約します (この場合、配列は 0 を含むように初期化されます)。このブロックのアドレスは次のように返されます。 _array.

記事によると、共通言語仕様 (CLS) では、すべての配列がゼロベースであることが必要です。.NET の配列は、ゼロベース以外の配列をサポートします。ただし、これはあまり一般的ではありません。ゼロベースの配列の「一般性」の結果、Microsoft は パフォーマンスの最適化に多くの時間を費やす;したがって、単次元のゼロベース (SZ) 配列は「特殊」であり、(多次元などとは対照的に) 配列の実際の実装としては最適です。SZ には配列を操作するための特定の中間言語命令があるためです。

配列は常に (メモリアドレスとして) 参照によって渡されます。これは、知っておくべき配列パズルの重要な部分です。境界チェックを行う間 (エラーがスローされます)、配列では境界チェックを無効にすることもできます。

繰り返しますが、配列の最大の障害は、サイズを変更できないことです。それらには「固定」容量があります。ArrayList と List(Of T) を歴史に導入します。

ArrayList - 非ジェネリックリスト

の配列リスト（とともに List(Of T) - ただし、いくつかの決定的な違いがありますが、後で説明します) - おそらく、(広い意味で) コレクションへの次の追加として考えるのが最もよいでしょう。ArrayList は IList (「ICollection」の子孫) インターフェイス。ArrayList 自体は、かさばる - さらに多くが必要オーバーヘッド - リストよりも。

IList 実装で ArrayList を固定サイズのリスト (配列と同様) として扱うことができるようになります。ただし、ArrayList によって追加される追加機能以外には、この場合 (配列上の) ArrayList の速度が著しく遅いため、固定サイズの ArrayList を使用する利点はありません。

私の読んだところによると、ArrayList はギザギザにすることはできません。「多次元配列を要素として使用する...はサポートされていません。」繰り返しますが、ArrayList の棺にまた釘が刺さりました。ArrayList も「型付き」ではありません。つまり、基本的に ArrayList は単にオブジェクトの動的な配列です。 Object[]. 。これには、ArrayList を実装するときに大量のボックス化 (暗黙的) とアンボックス化 (明示的) が必要となり、やはりオーバーヘッドが増加します。

根拠のない考え:ArrayList は、配列からリスト型のコレクションに移行しようとする試みの、ある意味でたらめな概念の子のようなものである、ということを私の教授の一人から読んだか聞いたか覚えていると思います。かつては配列に対する大幅な改善でしたが、コレクションに関してさらなる開発が行われたため、配列はもはや最良の選択肢ではなくなりました。

リスト(T):ArrayList がどのようになったか (そしてそうなることを望んでいたのか)

メモリ使用量の違いは、同じプリミティブ型を含む ArrayList よりも List(Of Int32) が消費するメモリが 56% 少ないほど顕著です (8 MB と上記の紳士のリンクされたデモでは 19 MB:またまたリンクしましたここ) - ただし、これは 64 ビットマシンによってさらに複雑になった結果です。この違いは実際に次の 2 つのことを示しています。まず (1)、ボックス化された Int32 型の「オブジェクト」(ArrayList) は、純粋な Int32 プリミティブ型 (List) よりもはるかに大きいです。2 番目 (2) では、64 ビットマシンの内部動作の結果として、その差は指数関数的になります。

それで、違いは何ですか、そして何ですかリスト(T)? MSDN を定義します List(Of T) として、 "...インデックスによってアクセスできる、厳密に型指定されたオブジェクトのリスト。ここで重要なのは、次の「厳密に型指定された」部分です。List(Of T) は型を「認識」し、オブジェクトをその型として保存します。それで、 Int32 として保存されます Int32 ではありません Object タイプ。これにより、ボックス化およびボックス化解除によって発生する問題が解消されます。

MSDN では、この違いは参照型ではなくプリミティブ型を格納する場合にのみ影響することを指定しています。 また、違いは実際に大規模に発生します。500以上の要素。さらに興味深いのは、MSDN ドキュメントに「ArrayList クラスを使用する代わりに、List(Of T) クラスの型固有の実装を使用すると有利です。」と書かれていることです。

基本的に、List(Of T) は ArrayList ですが、それよりも優れています。これは ArrayList の「一般的な同等物」です。ArrayList と同様に、ソートされるまでソートされることは保証されません (図に進みます)。List(Of T) にはいくつかの追加機能もあります。

この質問には共感します。私も選択に当惑した（発見した？）ため、どのデータ構造が最も速いかを科学的に調べてみました（テストは VB を使用して行いましたが、どちらの言語も同じであるため、C# も同じだと思います） CLR レベルでも同じことを行います)。ご覧いただけますここで私が実施したいくつかのベンチマーク結果 (どのような状況でどのデータ型を使用するのが最適かという議論もあります)。

これらはインテリセンスでかなり詳しく説明されています。入力するだけ システム.コレクション。 または System.Collections.Generics (推奨) すると、利用可能なもののリストと簡単な説明が表示されます。

ハッシュテーブル/ディクショナリのパフォーマンスは O(1) です。これは、パフォーマンスがサイズの関数ではないことを意味します。それを知っておくことが重要です。

編集：実際には、Hashtable/Dictionary<> ルックアップの平均時間計算量は O(1) です。

ジェネリックコレクションは、特に多くの項目を反復処理する場合、非ジェネリックコレクションよりもパフォーマンスが高くなります。これは、ボックス化とボックス化解除が行われなくなったためです。

高頻度のシステマティック取引エンジニアリングにおけるハッシュテーブルとディクショナリに関する重要な注意事項:スレッドの安全性の問題

ハッシュテーブルは、複数のスレッドで使用できるスレッドセーフです。ディクショナリのパブリック静的メンバーはスレッドセーフですが、インスタンスメンバーはスレッドセーフであることが保証されていません。

したがって、この点では Hashtable が「標準」の選択肢のままです。

ジェネリックコレクションと非ジェネリックコレクションの間には、微妙な違いとそれほど微妙ではない違いがあります。それらは単に、異なる基礎となるデータ構造を使用しているだけです。たとえば、Hashtable は、同期なしで 1 つの書き込みと複数の読み取りを保証します。辞書にはありません。

実際のところ、私はそう思います MSDN は、これらすべての質問に対して非常に優れた答えを提供するのに役立ちます。.NET コレクションを検索するだけです。

最も人気のある C# データ構造とコレクション

配列
配列リスト
リスト
リンクリスト
辞書
ハッシュセット
スタック
列
ソートされたリスト

C#.NET にはさまざまなデータ構造があります。たとえば、最も一般的なものの 1 つは配列です。ただし、C# にはさらに多くの基本的なデータ構造が付属しています。使用する正しいデータ構造を選択することは、適切に構造化された効率的なプログラムを作成することの一部です。

この記事では、C#.NET 3.5 で導入された新しいデータ構造を含む、組み込みの C# データ構造について説明します。これらのデータ構造の多くは他のプログラミング言語にも適用できることに注意してください。

配列

おそらく最も単純で最も一般的なデータ構造は配列です。C# の配列は基本的にオブジェクトのリストです。その特徴は、すべてのオブジェクトが (ほとんどの場合) 同じタイプであり、オブジェクトの数が特定であることです。配列の性質により、リスト内の位置 (インデックスとも呼ばれます) に基づいて要素に非常に高速にアクセスできます。C# の配列は次のように定義されます。

[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]

ソースと詳細情報はここで見つけることができます :

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow