69

これは、「 SortedListとSortedDictionaryの違いは何ですか?」というこの質問と重複しているように見える場合があります。残念ながら、答えはMSDNのドキュメントを引用するだけであり(パフォーマンスとメモリの使用に違いがあることを明確に述べています)、実際には質問に答えていません.

実際（したがって、この質問は同じ回答を得られません）、MSDN によると：

ジェネリック クラスは、O(log n) 検索を行う二分探索木です。SortedList<TKey, TValue>ここで、n はディクショナリ内の要素の数です。この点では、 SortedDictionary<TKey, TValue>ジェネリック クラスに似ています。2 つのクラスのオブジェクト モデルは類似しており、どちらも O(log n) の取得が可能です。2 つのクラスの違いは、メモリの使用と挿入と削除の速度です。

  • SortedList<TKey, TValue>は より少ないメモリを使用しますSortedDictionary<TKey, TValue>。

  • SortedDictionary<TKey, TValue>の O(n) とは対照的に、O(log n) は、並べ替えられていないデータの挿入および削除操作が高速です SortedList<TKey, TValue>。

  • リストが並べ替えられたデータから一度に入力される場合、SortedList<TKey, TValue>は よりも高速です SortedDictionary<TKey, TValue>。

したがって、並べ替えられていないデータに対してより高速な挿入および削除操作が必要でない限り、明らかにこれがSortedList<TKey, TValue>より良い選択であることを示しています。

上記の情報を考えると、SortedDictionary<TKey, TValue>? パフォーマンス情報に基づいて、実際にはまったく必要がないことを意味しSortedDictionary<TKey, TValue>ます。

4

6 に答える 6

56

SortedListおよびの MSDN ドキュメントがどれほど正確かはわかりませんSortedDictionary。両方とも二分探索木を使用して実装されていると言っているようです。しかし、SortedList が二分探索木を使用している場合、加算が よりもはるかに遅いのはなぜでしょうSortedDictionaryか?

とにかく、ここにいくつかのパフォーマンステスト結果があります。

各テストは、10,000 個の int32 キーを含むSortedList/で動作します。SortedDictionary各テストは 1,000 回繰り返されます (リリース ビルド、デバッグなしで開始)。

テストの最初のグループでは、0 から 9,999 までのキーを順番に追加します。テストの 2 番目のグループでは、0 から 9,999 までのランダムなシャッフル キーが追加されます (すべての数値が 1 回だけ追加されます)。

***** Tests.PerformanceTests.SortedTest

SortedDictionary Add sorted: 4411 ms
SortedDictionary Get sorted: 2374 ms


SortedList Add sorted: 1422 ms
SortedList Get sorted: 1843 ms

***** Tests.PerformanceTests.UnsortedTest

SortedDictionary Add unsorted: 4640 ms
SortedDictionary Get unsorted: 2903 ms


SortedList Add unsorted: 36559 ms
SortedList Get unsorted: 2243 ms

他のプロファイリングと同様に、重要なのは実際の数値ではなく、相対的なパフォーマンスです。

ご覧のとおり、並べ替えられたデータでは、並べ替えられたリストはSortedDictionary. ソートされていないデータでSortedListは、取得はわずかに高速ですが、追加は約 9 倍遅くなります。

両方が内部でバイナリ ツリーを使用している場合、並べ替えられていないデータに対する Add 操作が非常に遅くなるのは非常に驚くべきことですSortedList。並べ替えられたリストが同時に並べ替えられた線形データ構造にアイテムを追加している可能性もあり、これにより速度が低下します。

SortedListただし、 a のメモリ使用量は aと等しいか、それ以上であると予想されSortedDictionaryます。しかし、これは MSDN ドキュメントの内容と矛盾しています。

于 2009-11-18T06:38:44.217 に答える
37

SortedList<TKey, TValue>MSDNがその実装にバイナリ ツリーを使用すると言っている理由がわかりません。逆コンパイラを使用してコードを見ると、そうではないことがわかるからReflectorです。

SortedList<TKey, TValue>時間の経過とともに成長する単なる配列です。

要素を挿入するたびに、最初に配列に十分な容量があるかどうかを確認します。そうでない場合は、より大きな配列が再作成され、古い要素がそこにコピーされます (のようにList<T>)

その後、バイナリ検索を使用して、要素を挿入する場所を検索します (配列はインデックス可能で、既にソートされているため、これが可能です)。

配列をソートしたままにするために、挿入する要素の位置の後にあるすべての要素を 1 つの位置に移動 (またはプッシュ) します( を使用Array.Copy())。

例:

// we want to insert "3" 

2  
4  <= 3
5
8
9
.      
.      
.  

// we have to move some elements first

2
.  <= 3
4 
5  |
8  v
9
.
.

SortedListこれは、ソートされていない要素を挿入すると のパフォーマンスが非常に悪い理由を説明しています。ほとんどの挿入のたびに、いくつかの要素を再コピーする必要があります。実行する必要がない唯一のケースは、要素を配列の最後に挿入する必要がある場合です。

SortedDictionary<TKey, TValue>は異なり、二分木を使用して要素を挿入および取得します。また、ツリーのバランスを再調整する必要がある場合があるため、挿入時にいくらかのコストがかかります (ただし、すべての挿入ではありません)。

SortedListまたはで要素を検索するときのパフォーマンスはSortedDictionary、どちらもバイナリ検索を使用するため、非常に似ています。

私の意見では、配列を単にソートするために使用するべきではありません。SortedList要素がほとんどない場合を除き、値をリスト (または配列) に挿入してからSort()メソッドを呼び出す方が常に高速です。

SortedListすでに並べ替えられた値のリストがある場合 (例: データベースから)、並べ替えられた状態を維持し、並べ替えられていることを利用するいくつかの操作を実行したい場合 (例:線形検索の代わりに二分検索Contains()を実行する方法)SortedList

SortedDictionarySortedList挿入する値がまだソートされていない場合と同じ利点がありますが、パフォーマンスが向上します。

EDIT : .NET Framework 4.5 を使用している場合、代わりSortedDictionary<TKey, TValue>にSortedSet<T>. 二分木を使用して と同じように機能しSortedDictionaryますが、ここではキーと値は同じです。

于 2012-03-01T14:19:10.807 に答える
11

それらは2つの異なる目的のためのものですか？

.NET でのこれら 2 つのコレクション タイプのセマンティック上の違いはあまりありません。どちらもキー付きルックアップを提供するだけでなく、エントリをキーのソート順で保持します。ほとんどの場合、どちらでも問題ありません。おそらく唯一の差別化要因は、索引付けされた検索SortedList許可です。

しかし、パフォーマンス？

ただし、どちらかを選択するより強力な要因となるパフォーマンスの違いがあります。以下は、それらの漸近的な複雑さを表形式で示したものです。

+------------------+---------+----------+--------+----------+----------+---------+
| Collection       | Indexed | Keyed    | Value  | Addition |  Removal | Memory  |
|                  | lookup  | lookup   | lookup |          |          |         |
+------------------+---------+----------+--------+----------+----------+---------+
| SortedList       | O(1)    | O(log n) | O(n)   | O(n)*    | O(n)     | Lesser  |
| SortedDictionary | n/a     | O(log n) | O(n)   | O(log n) | O(log n) | Greater |
+------------------+---------+----------+--------+----------+----------+---------+

* Insertion is O(1) for data that are already in sort order, so that each 
  element is added to the end of the list (assuming no resize is required).

概要

大まかに要約すると、次の場合が必要ですSortedList<K, V>。

  1. インデックス付きルックアップが必要です。
  2. メモリのオーバーヘッドが少ないことが望ましいです。
  3. 入力データは既にソートされています (db から既にソートされているとします)。

代わりに when を好むでしょうSortedDictionary<K, V>:

  1. 相対的な全体的なパフォーマンスが重要です (スケーリングに関して)。
  2. 入力データは順不同です。

コードを書く

との両方SortedList<K, V>をSortedDictionary<K, V>実装IDictionary<K, V>するため、コードIDictionary<K, V>でメソッドから戻るか、変数を として宣言できますIDictionary<K, V>。基本的に実装の詳細を非表示にし、インターフェースに対するコードを作成します。

IDictionary<K, V> x = new SortedDictionary<K, V>(); //for eg.

将来、1 つのコレクションのパフォーマンス特性に満足できない場合に備えて、どちらからでも簡単に切り替えることができます。

2 つのコレクション タイプの詳細については、リンクされている元の質問を参照してください。

于 2014-05-22T17:21:29.737 に答える
4

パフォーマンスの違いを視覚的に表現。

ここに画像の説明を入力

于 2014-05-30T08:10:48.967 に答える
2

それだけです。キーの取得は同等ですが、追加は辞書を使用するとはるかに高速です。

キーと値のコレクションを反復処理できるため、SortedList をできる限り使用するようにしています。私の知る限り、これは SortedDictionary では不可能です。

これについてはよくわかりませんが、私が知る限り、辞書はデータをツリー構造に格納しますが、リストはデータを線形配列に格納します。これは、メモリの移動が少なくて済むため、辞書を使用すると挿入と削除がはるかに高速になる理由を説明しています。また、SortedLists を反復処理できるが、SortedDictionary を反復処理できない理由についても説明します。

于 2009-09-04T02:38:56.490 に答える
0

私たちにとって重要な考慮事項は、小さな辞書 (100 要素未満) を使用することが多く、現在のプロセッサはシーケンシャル メモリへのアクセスがはるかに高速であり、予測が困難な分岐をほとんど実行しないという事実です。(つまり、ツリーをトラバースするのではなく、線形配列を反復します) したがって、ディクショナリの要素が約 60 未満の場合、SortedList<> は多くのユース ケースで最も高速で最もメモリ効率の高いディクショナリです。

于 2018-10-16T19:18:20.603 に答える