SortedList と SortedDictionary の違いは何ですか?

StackOverflow https://stackoverflow.com/questions/935621

質問

の間に実際的な違いはありますか? SortedList<TKey,TValue> そして SortedDictionary<TKey,TValue>?特に一方を使用し、他方を使用しない状況はありますか?

役に立ちましたか？

解決

はい、パフォーマンス特性は大きく異なります。電話したほうがいいかもしれません SortedList そして SortedTree これは実装をより厳密に反映しているためです。

それぞれの MSDN ドキュメントを参照してください (SortedList, SortedDictionary) さまざまな状況でのさまざまな操作のパフォーマンスの詳細については、を参照してください。ここに素晴らしい要約があります（ SortedDictionary ドキュメント):

の SortedDictionary<TKey, TValue> Generic Classは、O（log n）検索を備えたバイナリ検索ツリーで、nは辞書の要素の数です。この点では、 SortedList<TKey, TValue> ジェネリッククラス。2つのクラスには同様のオブジェクトモデルがあり、どちらもo（log n）検索があります。2つのクラスが異なるのは、メモリの使用と挿入と取り外しの速度にあります。

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

  • SortedDictionary<TKey, TValue> o（n）とは対照的に、o（log n）のo（log n）の挿入および除去操作が速い SortedList<TKey, TValue>.

  • リストがソートされたデータから一度にすべて入力されている場合、 SortedList<TKey, TValue> よりも速いです SortedDictionary<TKey, TValue>.

(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).

から 実装 視点：

+------------+---------------+----------+------------+------------+------------------+
| Underlying | Lookup        | Ordering | Contiguous | Data       | Exposes Key &    |
| structure  | strategy      |          | storage    | access     | Value collection |
+------------+---------------+----------+------------+------------+------------------+
| 2 arrays   | Binary search | Sorted   | Yes        | Key, Index | Yes              |
| BST        | Binary search | Sorted   | No         | Key        | Yes              |
+------------+---------------+----------+------------+------------+------------------+

に だいたい 生のパフォーマンスが必要な場合は、言い換えます。 SortedDictionary より良い選択になるかもしれません。より少ないメモリオーバーヘッドとインデックス付き取得が必要な場合 SortedList よりよくフィットします。 どちらをいつ使用するかについて詳しくは、この質問を参照してください。

もっと読むことができます ここ, ここ, ここ, ここ そして ここ.

ちょっと混乱しているようなので、リフレクターを開いてこれを見てみました。 SortedList. 。実際には二分探索木ではありません。 これは、キーと値のペアの (キーで) ソートされた配列です。. 。もあります。 TKey[] keys キーと値のペアと同期してソートされ、バイナリ検索に使用される変数。

私の主張を裏付けるソース (.NET 4.5 を対象とする) を以下に示します。

プライベートメンバー

// Fields
private const int _defaultCapacity = 4;
private int _size;
[NonSerialized]
private object _syncRoot;
private IComparer<TKey> comparer;
private static TKey[] emptyKeys;
private static TValue[] emptyValues;
private KeyList<TKey, TValue> keyList;
private TKey[] keys;
private const int MaxArrayLength = 0x7fefffff;
private ValueList<TKey, TValue> valueList;
private TValue[] values;
private int version;

SortedList.ctor(IDictionary, IComparer) 

public SortedList(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer) : this((dictionary != null) ? dictionary.Count : 0, comparer)
{
    if (dictionary == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
    }
    dictionary.Keys.CopyTo(this.keys, 0);
    dictionary.Values.CopyTo(this.values, 0);
    Array.Sort<TKey, TValue>(this.keys, this.values, comparer);
    this._size = dictionary.Count;
}

SortedList.Add(TKey, TValue) :空所

public void Add(TKey key, TValue value)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    int num = Array.BinarySearch<TKey>(this.keys, 0, this._size, key, this.comparer);
    if (num >= 0)
    {
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
    }
    this.Insert(~num, key, value);
}

SortedList.RemoveAt(int) :空所

public void RemoveAt(int index)
{
    if ((index < 0) || (index >= this._size))
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
    }
    this._size--;
    if (index < this._size)
    {
        Array.Copy(this.keys, index + 1, this.keys, index, this._size - index);
        Array.Copy(this.values, index + 1, this.values, index, this._size - index);
    }
    this.keys[this._size] = default(TKey);
    this.values[this._size] = default(TValue);
    this.version++;
}

をチェックしてください SortedList の MSDN ページ:

備考欄より:

の SortedList<(Of <(TKey, TValue>)>) ジェネリッククラスは二分探索木です。 O(log n) 検索、どこで n 辞書内の要素の数です。この点では、 SortedDictionary<(Of <(TKey, TValue>)>) ジェネリッククラス。2 つのクラスには同様のオブジェクト モデルがあり、両方とも O(log n) 検索。2 つのクラスの違いは、メモリ使用量と挿入と削除の速度です。

  • SortedList<(Of <(TKey, TValue>)>) より少ないメモリ使用量 SortedDictionary<(Of <(TKey, TValue>)>).

  • SortedDictionary<(Of <(TKey, TValue>)>) ソートされていないデータの挿入および削除操作が高速になり、 O(log n) とは対照的に O(n) のために SortedList<(Of <(TKey, TValue>)>).

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

これは性能が相互に比較する方法を視覚的に表現されます。

このトピックについてはすでに十分なことが述べられていますが、簡潔にするために、ここで私の見解を述べます。

分類された辞書 以下の場合に使用する必要があります-

  • さらに挿入および削除操作が必要です。
  • データは順序付けされていません。
  • キーアクセスだけで十分であり、インデックスアクセスは必要ありません。
  • メモリはボトルネックではありません。

反対側では、 ソートされたリスト 以下の場合に使用する必要があります-

  • より多くの検索が必要になり、より少ない挿入および削除操作が必要になります。
  • データはすでにソートされています (すべてではないにしても、ほとんど)。
  • インデックスへのアクセスが必要です。
  • メモリはオーバーヘッドです。

お役に立てれば！！

インデックスアクセス（ここでは言及は）現実的な違いがあります。 あなたは後継者や前任者にアクセスする必要がある場合は、SortedListのを必要としています。 SortedDictionaryはそう、あなたがソート（最初/ foreachの）を使用する方法と、かなり限られていることを行うことはできません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top