Was ist der Unterschied zwischen SortedList und SortedDictionary?

Question

Gibt es einen echten praktischen Unterschied zwischen einem SortedList<TKey,TValue> und einem SortedDictionary<TKey,TValue>? Gibt es Umstände, in denen Sie das eine und nicht das andere benutzen würden?

Answer 1

Ja - ihre Leistungsmerkmale unterscheiden sich erheblich. Es wäre wahrscheinlich besser, sie SortedList und SortedTree zu nennen, da dies die Implementierung genauer widerspiegelt.

In den jeweiligen MSDN-Dokumenten (SortedList, SortedDictionary) finden Sie Informationen zur Leistung für verschiedene Vorgänge in verschiedenen Situationen. Hier ist eine schöne Zusammenfassung (aus den SortedDictionary docs):

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

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

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

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

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

Answer 2

Schauen Sie sich die MSDN page for SortedList:

Aus dem Bereich Bemerkungen:

Die generische Klasse SortedList<(Of <(TKey, TValue>)>) ist ein binärer Suchbaum mit O(log n) Abruf, Dabei steht n für die Anzahl der Elemente im Wörterbuch. In dieser ähnelt es der generischen Klasse SortedDictionary<(Of <(TKey, TValue>)>). Die beiden Klassen haben ähnliche Objektmodelle, und beide haben O(log n) Abruf. Wo die beiden Klassen unterscheiden, in die 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 Einfüge- und Entfernungsoperationen für unsortierte Daten, O(log n) im Gegensatz zu O(n) für SortedList<(Of <(TKey, TValue>)>).

• Wenn die Liste gleichzeitig aus sortierten Daten besteht, ist SortedList<(Of <(TKey, TValue>)>) schneller als SortedDictionary<(Of <(TKey, TValue>)>).

Answer 3

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

Hier ist eine Quelle (Targeting .NET 4.5), um meine Ansprüche zu sichern.

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

Hier eine tabellarische Darstellung ist, 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 einem implementation 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    | 
+------------+---------------+----------+------------+------------+------------------+ 

Um etwa paraphrasieren, wenn Sie rohe Leistung benötigen SortedDictionary könnte eine bessere Wahl sein. Wenn Sie geringeren Speicheraufwand und indizierten Abruf benötigen, passt SortedList besser. See this question for more on when to use which.

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

Answer 5

Dies ist eine visuelle Darstellung der Leistungsvergleiche.

Answer 6

Indexzugriff (hier genannt) ist der praktische Unterschied. Wenn Sie auf den Nachfolger oder Vorgänger zugreifen müssen, benötigen Sie SortedList. SortedDictionary kann das nicht tun, so dass Sie ziemlich begrenzt sind, wie Sie die Sortierung verwenden können (first/foreach).

Answer 7

Genug gesagt wird schon zu dem Thema, aber um es einfach zu halten, hier ist meine Aufnahme.

Sortiert Wörterbuch sollte verwendet werden, wenn-

• Weitere Einsätze und Löschvorgänge erforderlich sind.
• Daten in ungeordneter Reihenfolge.
• Der Schlüsselzugriff ist ausreichend und ein Indexzugriff ist nicht erforderlich.
• Speicher ist kein Flaschenhals.

Auf der anderen Seite, Rasterung sollte wenn-

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

Hoffe das hilft !!