Was ist der Unterschied zwischen SortedList und SortedDictionary?

Question

Gibt es einen wirklich praktischen Unterschied zwischen einem SortedList<TKey,TValue> und ein SortedDictionary<TKey,TValue> ? Gibt es Situationen, in denen Sie gezielt ein verwenden würde und nicht die anderen?

Answer 1

Ja - ihre Leistungseigenschaften unterscheiden sich deutlich. Es wäre wahrscheinlich besser, sie SortedList und SortedTree zu nennen wie die Umsetzung eng mehr widerspiegelt.

Sehen Sie in der MSDN-Dokumentation für jeden von ihnen ( SortedList , SortedDictionary ) für Details der Leistung für verschiedene Operationen in verschiedenen situtations. Hier ist eine schöne Zusammenfassung (aus dem SortedDictionary docs):

  

Die SortedDictionary<TKey, TValue> generic   Klasse ist ein binärer Suchbaum mit   O (log n) Retrieval, wobei n die ist   Anzahl der Elemente im Wörterbuch.   Dabei ist es ähnlich wie die   SortedList<TKey, TValue> generic   Klasse. Die beiden Klassen haben ähnliche   Objektmodelle, und beide haben O (log n)   Retrieval. Wo die beiden Klassen   unterscheiden, ist in der Speichernutzung und Geschwindigkeit von   Einsetzen und Entfernen:

     

  

• SortedList<TKey, TValue> verbraucht weniger   Speicher als SortedDictionary<TKey, TValue>.

  

• SortedDictionary<TKey, TValue> hat   schnelleres Einsetzen und Entfernen   Operationen für unsortierte Daten, O (log n)   zu O (N) im Gegensatz zum   SortedList<TKey, TValue>.

  

• Wenn die Liste wird auf einmal bevölkert   von sortierten Daten ist SortedList<TKey, TValue> schneller als   SortedDictionary<TKey, TValue>.

  

(SortedList hält tatsächlich ein sortiertes Array, anstatt einen Baum verwendet wird. Es ist immer noch binäre Suche verwendet Elemente zu finden.)

Answer 2

Hier ist eine tabellarische Darstellung, wenn es hilft ...

Aus Leistung Perspektive:

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

Von einer Implementierung Perspektive:

+------------+---------------+----------+------------+------------+------------------+
| 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              |
+------------+---------------+----------+------------+------------+------------------+

ungefähr paraphrasiert, wenn Sie rohe Leistung SortedDictionary erfordern könnte eine bessere Wahl sein. Wenn Sie weniger Speicher-Overhead und indiziert Retrieval SortedList erfordern passt besser. Sehen Sie diese Frage für mehr auf, wenn die verwenden.

Sie können mehr lesen hier hier , hier , hier und hier .

Answer 3

Ich geknackt Reflektor einen Blick auf diese zu haben, wie es scheint ein wenig Verwirrung über SortedList zu sein. Es ist in der Tat nicht ein binärer Suchbaum, es ist ein sortiert (mit Schlüssel) Array von Schlüssel-Wert-Paare . Es gibt auch eine TKey[] keys Variable, die synchron mit den Schlüssel-Wert-Paare und binäre Suche verwendet sortiert wird.

Hier ist einige Quelle (Targeting .NET 4.5) auf meine Backup-Ansprüche.

Privat Mitglieder

// 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++;
}

Answer 4

Überprüfen Sie die MSDN-Seite für SortedList aus:

Von Bemerkungen Abschnitt:

  

Die SortedList<(Of <(TKey, TValue>)>) generische Klasse ist ein binärer Suchbaum mit O(log n) Retrieval, wo n die Anzahl der Elemente im Wörterbuch enthalten ist. Dabei ist es ähnlich wie bei der SortedDictionary<(Of <(TKey, TValue>)>) generischen Klasse. Die beiden Klassen haben ähnliche Objektmodelle, und beide haben O(log n) Retrieval. Wo die beiden Klassen unterscheiden, in der Speichernutzung und die Geschwindigkeit der Einführung und Entfernung:

     

  
• SortedList<(Of <(TKey, TValue>)>) benötigt weniger Speicher als SortedDictionary<(Of <(TKey, TValue>)>).
  

• SortedDictionary<(Of <(TKey, TValue>)>) hat schnellere Einsetzen und Entfernen Operationen für unsortierte Daten, O(log n) wie für O(n) SortedList<(Of <(TKey, TValue>)>) gegenüber.

  

• Wenn die Liste alle auf einmal bevölkert von sortierten Daten, SortedList<(Of <(TKey, TValue>)>) ist schneller als SortedDictionary<(Of <(TKey, TValue>)>).

  

Answer 5

Dies ist die visuelle Darstellung, wie Leistungen miteinander vergleichen.

Answer 6

Genug gesagt wird bereits über das Thema, aber es ist einfach zu halten, hier ist mein nehmen.

Sortiert Wörterbuch sollte verwendet werden, wenn -

• Weitere Einsätze und Löschvorgänge erforderlich sind.
• Daten in ungeordnet.
• Key Zugang genügt und Indexzugriff ist nicht erforderlich.
• Speicher ist kein Engpass.

Auf der anderen Seite, Rasterung sollte verwendet werden, wenn -

• Mehr Lookups und weniger Einsätze und Löschvorgänge erforderlich sind.
• Die Daten werden bereits sortiert (wenn nicht alle, die meisten).
• Indexzugriff erforderlich ist.
• Speicher ist ein Overhead.

Hope, das hilft !!

Answer 7

Index-Zugang (hier erwähnt) ist die praktische Unterschied. Wenn Sie den Nachfolger oder Vorgänger zugreifen müssen, benötigen Sie SortedList. SortedDictionary kann das nicht, so dass Sie ziemlich begrenzt sind mit, wie Sie die Sortierung verwenden können (erste / foreach).