Was ist der Unterschied zwischen SortedList und SortedDictionary?

261

Gibt es einen wirklichen praktischen Unterschied zwischen a SortedList<TKey,TValue>und a SortedDictionary<TKey,TValue>? Gibt es Umstände, unter denen Sie speziell das eine und nicht das andere verwenden würden?

Shaul Behr
quelle
13
Ich bin verwirrt. Warum hat SortedList zwei Typparameter SortedList<TKey,TValue>anstelle von einem SortedList<T>? Warum wird es nicht implementiert IList<T>?
Colonel Panic
3
@ColonelPanic, da SortedList funktional eine Karte und keine lineare Sammlung ist. Lass dich nicht vom Namen täuschen. Wie bei einem Wörterbuch geben Sie einen Schlüssel ein und erhalten einen Wert zurück. Während das Wörterbuch ungeordnet ist, wird SortedList in seiner natürlichen sortierten Reihenfolge sortiert.
Nawfal

Antworten:

293

Ja - ihre Leistungsmerkmale unterscheiden sich erheblich. Es wäre wahrscheinlich besser, sie zu nennen SortedListund SortedTreewie spiegelt die Umsetzung näher.

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

Die SortedDictionary<TKey, TValue>generische Klasse ist ein binärer Suchbaum mit O-Abruf (log n), wobei n die Anzahl der Elemente im Wörterbuch ist. In dieser Hinsicht ähnelt es der SortedList<TKey, TValue>generischen Klasse. Die beiden Klassen haben ähnliche Objektmodelle und beide haben einen O (log n) -Abruf. Wo sich die beiden Klassen unterscheiden, ist die Speichernutzung und die Geschwindigkeit des Einfügens und Entfernens:

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

  • SortedDictionary<TKey, TValue>hat schnellere Einfüge- und Entfernungsvorgänge für unsortierte Daten, O (log n) im Gegensatz zu O (n) für SortedList<TKey, TValue>.

  • Wenn die Liste auf einmal aus sortierten Daten gefüllt wird, SortedList<TKey, TValue>ist dies schneller als SortedDictionary<TKey, TValue>.

(verwaltet SortedListtatsächlich ein sortiertes Array, anstatt einen Baum zu verwenden. Es verwendet immer noch die binäre Suche, um Elemente zu finden.)

Jon Skeet
quelle
Vielen Dank an alle für die Hinweise. Ich denke, ich bin RTFM einfach zu faul ... viel einfacher, die netten Leute auf SO zu fragen ...;) Ich habe euch beide für die Antworten gewählt; Jon erhält eine Antwortgutschrift dafür, dass er der erste am Abzug ist. :)
Shaul Behr
2
Ich denke, die SortedList-Definition sollte korrigiert werden, da ich nicht glaube, dass es sich um einen binären Suchbaum handelt ...?
Nchaud
1
Ich habe mit Reflektor gesucht und festgestellt, dass kein binärer Suchbaum verwendet wurde.
Daniel Imms
Ich denke, das Sorteddictionary ist ein AVL-Baum oder Red-Blacktree (alle Operationen kosten O (logn). Und die SortedList ist eine binäre Suche (es kostet im schlimmsten Fall o (n) Zeit) l
Ghoster
105

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

Aus Sicht der Leistung :

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

Aus Sicht der Implementierung :

+------------+---------------+----------+------------+------------+------------------+
| 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 es grob zu paraphrasieren: Wenn Sie Rohleistung benötigen, ist SortedDictionarydies möglicherweise die bessere Wahl. Wenn Sie weniger Speicheraufwand benötigen und der indizierte Abruf SortedListbesser passt. In dieser Frage erfahren Sie mehr darüber, wann Sie welche verwenden sollen.

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

nawfal
quelle
Beachten Sie, dass Sie dies in Betracht ziehen sollten , wenn Sie eine gute Leistung und eine relativ geringe Speichernutzung sowie einen indizierten Abruf wünschenBDictionary<Key,Value> in LoycCore statt in ziehen sollten wünschenSortedDictionary .
Qwertie
1
Ja, schauen Sie sich den unteren Teil dieses Artikels an . Es stellt sich heraus, dass BDictionaryes normalerweise langsamer ist als SortedDictionarybei sehr großen Größen, aber es ist schneller als SortedListbei über 700 Artikeln oder so. Die Speichernutzung sollte nur geringfügig höher sein als SortedList(viel niedriger alsSortedDictionary aufgrund der Verwendung von Arrays in den Blättern des Baums ) sein.
Qwertie
22

Ich habe Reflector aufgeschlagen, um mir das anzusehen, da es ein bisschen Verwirrung zu geben scheint SortedList. Es ist in der Tat kein binärer Suchbaum, sondern ein sortiertes (nach Schlüssel) Array von Schlüssel-Wert-Paaren . Es gibt auch eine TKey[] keysVariable, die synchron mit den Schlüssel-Wert-Paaren sortiert und für die binäre Suche verwendet wird.

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

Private 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): nichtig

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++;
}
Daniel Imms
quelle
13

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

Aus dem Abschnitt Bemerkungen:

Die SortedList<(Of <(TKey, TValue>)>)generische Klasse ist ein binärer Suchbaum mit O(log n)Abruf, wobei ndie Anzahl der Elemente im Wörterbuch angegeben ist. In dieser Hinsicht ähnelt es der SortedDictionary<(Of <(TKey, TValue>)>)generischen Klasse. Die beiden Klassen haben ähnliche Objektmodelle und beide haben einen O(log n)Abruf. Wo sich die beiden Klassen unterscheiden, ist die Speichernutzung und die Geschwindigkeit des Einfügens und Entfernens:

  • SortedList<(Of <(TKey, TValue>)>)verbraucht weniger Speicher als SortedDictionary<(Of <(TKey, TValue>)>).
  • SortedDictionary<(Of <(TKey, TValue>)>)hat schnellere Einfüge- und Entfernungsvorgänge für unsortierte Daten O(log n)im Gegensatz zu O(n)für SortedList<(Of <(TKey, TValue>)>).

  • Wenn die Liste auf einmal aus sortierten Daten gefüllt wird, SortedList<(Of <(TKey, TValue>)>)ist dies schneller als SortedDictionary<(Of <(TKey, TValue>)>).

Stephan
quelle
9
Der zitierte Text ist falsch (und wurde auf MSDN aktualisiert): SortedList ist kein "binärer Suchbaum", sondern ein "Array von Schlüssel / Wert-Paaren".
Eldritch Conundrum
12

Dies ist eine visuelle Darstellung des Vergleichs der Leistungen untereinander.

Lev
quelle
Woher haben Sie diese Informationen? Aus diesem Schema können wir erkennen, dass Diktär in irgendeiner Weise besser ist, so dass es keinen Grund für andere gibt, zu existieren.
Alex Kostin
9

Zu diesem Thema ist bereits genug gesagt, aber um es einfach zu halten, hier ist meine Meinung.

Sortiertes Wörterbuch sollte verwendet werden, wenn-

  • Weitere Einfüge- und Löschvorgänge sind erforderlich.
  • Daten unbestellt.
  • Der Schlüsselzugriff ist ausreichend und der Indexzugriff ist nicht erforderlich.
  • Speicher ist kein Engpass.

Auf der anderen Seite sollte die sortierte Liste verwendet werden, wenn

  • Es sind mehr Suchvorgänge und weniger Einfügungen und Löschvorgänge erforderlich.
  • Die Daten sind bereits sortiert (wenn nicht alle, die meisten).
  • Indexzugriff ist erforderlich.
  • Speicher ist ein Overhead.

Hoffe das hilft!!

Prakash Tripathi
quelle
1

Der Indexzugriff (hier erwähnt) ist der praktische Unterschied. Wenn Sie auf den Nachfolger oder Vorgänger zugreifen müssen, benötigen Sie SortedList. SortedDictionary kann das nicht, daher sind Sie ziemlich eingeschränkt in der Verwendung der Sortierung (first / foreach).

Kerl
quelle