Was ist der Unterschied zwischen SortedList und SortedDictionary?
-
06-09-2019 - |
Frage
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?
Lösung
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 dieSortedList<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 alsSortedDictionary<TKey, TValue>
.
SortedDictionary<TKey, TValue>
hat schnelleres Einsetzen und Entfernen Operationen für unsortierte Daten, O (log n) zu O (N) im Gegensatz zumSortedList<TKey, TValue>
.Wenn die Liste wird auf einmal bevölkert von sortierten Daten ist
SortedList<TKey, TValue>
schneller alsSortedDictionary<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.)
Andere Tipps
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.
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++;
}
Ü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 mitO(log n)
Retrieval, won
die Anzahl der Elemente im Wörterbuch enthalten ist. Dabei ist es ähnlich wie bei derSortedDictionary<(Of <(TKey, TValue>)>)
generischen Klasse. Die beiden Klassen haben ähnliche Objektmodelle, und beide habenO(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 alsSortedDictionary<(Of <(TKey, TValue>)>)
.
SortedDictionary<(Of <(TKey, TValue>)>)
hat schnellere Einsetzen und Entfernen Operationen für unsortierte Daten,O(log n)
wie fürO(n)
SortedList<(Of <(TKey, TValue>)>)
gegenüber.Wenn die Liste alle auf einmal bevölkert von sortierten Daten,
SortedList<(Of <(TKey, TValue>)>)
ist schneller alsSortedDictionary<(Of <(TKey, TValue>)>)
.
Dies ist die visuelle Darstellung, wie Leistungen miteinander vergleichen.
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 !!
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).