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

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?

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

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 .

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

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

Jest to wizualna reprezentacja porównania wydajności.

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

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