284

SortedList<TKey,TValue>aとaの間に実際の違いはありSortedDictionary<TKey,TValue>ますか？どちらか一方を具体的に使用し、もう一方を使用しない状況はありますか？

4

7 に答える 7

321

はい-それらのパフォーマンス特性は大幅に異なります。SortedListそれらを呼び出す方がおそらく良いでしょう、そしてそれSortedTreeは実装をより密接に反映しているからです。

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

ジェネリッククラスは、O（log n）検索を使用するバイナリ検索ツリーです。SortedDictionary<TKey, TValue>ここで、nはディクショナリ内の要素の数です。この点では、 SortedList<TKey, TValue>ジェネリッククラスに似ています。2つのクラスには類似したオブジェクトモデルがあり、どちらにもO（log n）検索があります。2つのクラスが異なるのは、メモリの使用と挿入と削除の速度です。

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

  • SortedDictionary<TKey, TValue>のO（n）とは対照的に、ソートされていないデータの挿入および削除操作が高速です SortedList<TKey, TValue>。

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

（SortedListツリーを使用するのではなく、実際にはソートされた配列を維持します。それでも要素を見つけるためにバイナリ検索を使用します。）

于 2009-06-01T16:38:04.353 に答える
121

それが役立つ場合は、これが表形式のビューです...

パフォーマンスの観点から：

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

  * Insertion is O(log n) for data that are already in sort order, so that each 
    element is added to the end of the list. If a resize is required, that element
    takes O(n) time, but inserting n elements is still amortized O(n log n).
    list.
** Available through enumeration, e.g. Enumerable.ElementAt.

実装の観点から：

+------------+---------------+----------+------------+------------+------------------+
| 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が適している場合。いつどちらを使用するかについて詳しくは、この質問を参照してください。

あなたはここ、ここ、ここ、ここ、そしてここでもっと読むことができます。

于 2014-05-20T20:14:29.703 に答える
23

について少し混乱しているように見えるので、これを確認するためにReflectorを開いてみました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）：void

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）：void

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++;
}
于 2013-02-23T05:53:48.467 に答える
13

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>)>)。

于 2009-06-01T16:39:21.060 に答える
13

これは、パフォーマンスが互いにどのように比較されるかを視覚的に表したものです。

于 2014-05-30T08:09:17.960 に答える
11

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

ソートされた辞書は次の場合に使用する必要があります-

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

反対に、ソート済みリストは次の場合に使用する必要があります-

  • より多くのルックアップとより少ない挿入および削除操作が必要です。
  • データはすでに並べ替えられています（すべてではないにしても、ほとんど）。
  • インデックスアクセスが必要です。
  • メモリはオーバーヘッドです。

お役に立てれば！！

于 2016-06-06T15:11:00.943 に答える
1

インデックスアクセス（ここで説明）は実際的な違いです。後続または先行にアクセスする必要がある場合は、SortedListが必要です。SortedDictionaryはそれを行うことができないため、並べ替えの使用方法（first / foreach）にはかなり制限があります。

于 2014-11-15T14:36:47.767 に答える