Jaka jest różnica między SortedList a SortedDictionary?


261

Czy jest jakaś praktyczna różnica między a SortedList<TKey,TValue>a a SortedDictionary<TKey,TValue>? Czy są jakieś okoliczności, w których używałbyś jednego, a nie drugiego?



13
Jestem zmieszany. Dlaczego SortedList ma dwa parametry typu SortedList<TKey,TValue>zamiast jednego SortedList<T>? Dlaczego się nie implementuje IList<T>?
Pułkownik Panic

3
@ ColonelPanic, ponieważ funkcjonalnie SortedList to mapa, a nie kolekcja liniowa. Nie daj się zwieść nazwie. Podobnie jak słownik, przekazujesz klucz, odzyskujesz wartość. Podczas gdy słownik jest nieuporządkowany, SortedList jest uporządkowany w swojej naturalnej kolejności.
nawfal

Odpowiedzi:


294

Tak - ich parametry wydajnościowe różnią się znacznie. Prawdopodobnie byłoby lepiej do nich zadzwonić SortedListi SortedTreejako że odzwierciedla wdrażanie bardziej uważnie.

Przejrzyj dokumentację MSDN dla każdego z nich ( SortedList, SortedDictionary), aby uzyskać szczegółowe informacje na temat wydajności dla różnych operacji w różnych situtacjach. Oto ładne podsumowanie (z SortedDictionarydokumentów):

SortedDictionary<TKey, TValue>Klasa rodzajowy jest wyszukiwanie binarne drzewo z O (log n) pobierania, gdzie n jest liczbą elementów w słowniku. Pod tym względem jest podobny do SortedList<TKey, TValue>klasy ogólnej. Dwie klasy mają podobne modele obiektowe i obie mają pobieranie O (log n). Różnice między tymi dwiema klasami dotyczą wykorzystania pamięci oraz szybkości wstawiania i usuwania:

  • SortedList<TKey, TValue>zużywa mniej pamięci niż SortedDictionary<TKey, TValue>.

  • SortedDictionary<TKey, TValue>ma szybsze operacje wstawiania i usuwania nieposortowanych danych, O (log n) w przeciwieństwie do O (n) dla SortedList<TKey, TValue>.

  • Jeśli lista jest zapełniana naraz od posortowanych danych, SortedList<TKey, TValue>jest szybsza niż SortedDictionary<TKey, TValue>.

( SortedListfaktycznie utrzymuje posortowaną tablicę, zamiast używać drzewa. Nadal używa wyszukiwania binarnego, aby znaleźć elementy.)


Bardzo dziękuję wszystkim za wskazówki. Wydaje mi się, że jestem zbyt leniwy wobec RTFM ... o wiele łatwiej zapytać miłych ludzi na SO ...;) Głosowałem oboje za odpowiedziami; Jon dostaje odpowiedź za bycie pierwszym na spuście. :)
Shaul Behr

2
Myślę, że definicja SortedList powinna zostać poprawiona, ponieważ nie wierzę, że jest to drzewo wyszukiwania binarnego ...?
nchaud

1
Spojrzałem za pomocą reflektora i stwierdziłem, że nie używało ono drzewa wyszukiwania binarnego.
Daniel Imms

Myślę, że Sorteddictionary to drzewo AVL lub Red-Blacktree (wszystkie operacje kosztują O (logn). A SortedList to wyszukiwanie binarne (w najgorszym przypadku kosztuje o (n) czas) l
Ghoster

105

Oto widok tabelaryczny, jeśli pomaga ...

Z perspektywy wydajności :

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

Z perspektywy wdrożenia :

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

Z grubsza sparafrazując, jeśli potrzebujesz surowej wydajności, SortedDictionarymoże być lepszym wyborem. Jeśli potrzebujesz mniejszego narzutu pamięci i indeksowane pobieranie SortedListlepiej pasuje. Zobacz to pytanie, aby dowiedzieć się więcej o tym, kiedy użyć.

Możesz przeczytać więcej tutaj , tutaj , tutaj , tutaj i tutaj .


Zauważ, że jeśli chcesz mieć dobrą wydajność i stosunkowo niskie zużycie pamięci i indeksowane pobieranie, rozważ BDictionary<Key,Value>w LoycCore zamiast SortedDictionary.
Qwertie

1
Tak, spójrz na dolną część tego artykułu . Okazuje się, że BDictionaryjest zwykle wolniejszy niż SortedDictionaryz wyjątkiem bardzo dużych rozmiarów, ale jest szybszy niż, SortedListjeśli jest około 700 przedmiotów. Wykorzystanie pamięci powinno być tylko nieznacznie wyższe niż SortedList(znacznie niższe niż SortedDictionary), ze względu na użycie tablic w liściach drzewa.
Qwertie,

22

Otworzyłem Odbłyśnik, żeby na to spojrzeć, ponieważ wydaje się, że jest trochę zamieszania SortedList. W rzeczywistości nie jest to drzewo wyszukiwania binarnego, to posortowana (według klucza) tablica par klucz-wartość . Istnieje również TKey[] keyszmienna, która jest sortowana synchronicznie z parami klucz-wartość i używana do wyszukiwania binarnego.

Oto źródło (ukierunkowane na .NET 4.5) do tworzenia kopii zapasowych moich roszczeń.

Członkowie prywatni

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

13

Sprawdź stronę MSDN dla SortedList :

Z sekcji Uwagi:

SortedList<(Of <(TKey, TValue>)>)Klasa rodzajowy jest wyszukiwanie binarne drzewo z O(log n)pobierania, gdzie njest liczbą elementów w słowniku. Pod tym względem jest podobny do SortedDictionary<(Of <(TKey, TValue>)>)klasy ogólnej. Dwie klasy mają podobne modele obiektowe i obie mają O(log n)pobieranie. Różnice między tymi dwiema klasami dotyczą wykorzystania pamięci oraz szybkości wstawiania i usuwania:

  • SortedList<(Of <(TKey, TValue>)>)zużywa mniej pamięci niż SortedDictionary<(Of <(TKey, TValue>)>).
  • SortedDictionary<(Of <(TKey, TValue>)>)ma szybsze operacje wstawiania i wyjmowania dla danych nieposortowane, O(log n)w przeciwieństwie do O(n)o SortedList<(Of <(TKey, TValue>)>).

  • Jeśli lista jest zapełniana naraz od posortowanych danych, SortedList<(Of <(TKey, TValue>)>)jest szybsza niż SortedDictionary<(Of <(TKey, TValue>)>).


9
Cytowany tekst jest niepoprawny (i został zaktualizowany w MSDN): SortedList nie jest „binarnym drzewem wyszukiwania”, ale „tablicą par klucz / wartość”.
Eldritch Conundrum,

12

Jest to wizualna reprezentacja porównania wydajności.


Skąd wziąłeś te informacje? Z tego schematu możemy zobaczyć, że Dictinary jest lepszy w jakikolwiek sposób, więc nie ma powodu, aby istnieć inni.
alex kostin

9

Dość już powiedziano na ten temat, jednak dla uproszczenia, oto moje zdanie.

Posortowanego słownika należy używać, gdy-

  • Wymaganych jest więcej operacji wstawiania i usuwania.
  • Dane w nieporządku.
  • Dostęp do klucza jest wystarczający, a dostęp do indeksu nie jest wymagany.
  • Pamięć nie jest wąskim gardłem.

Z drugiej strony listy posortowanej należy używać, gdy-

  • Wymagane jest więcej wyszukiwań oraz mniej operacji wstawiania i usuwania.
  • Dane są już posortowane (jeśli nie wszystkie, większość).
  • Wymagany jest dostęp do indeksu.
  • Pamięć jest narzutem.

Mam nadzieję że to pomoże!!


1

Dostęp do indeksu (wspomniany tutaj) stanowi praktyczną różnicę. Jeśli potrzebujesz uzyskać dostęp do następcy lub poprzednika, potrzebujesz SortedList. SortedDictionary nie może tego zrobić, więc masz dość ograniczone możliwości korzystania z sortowania (first / foreach).

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.