Znajduję to SortedList<TKey, TValue> SortedDictionary<TKey, TValue>i Dictionary<TKey, TValue>wdrażam te same interfejsy.

1. Kiedy powinniśmy zdecydować się na SortedListi SortedDictionarynadDictionary ?
2. Jaka jest różnica między SortedListi SortedDictionarypod względem zastosowania?

1. Podczas iteracji po elementach w jednym z dwóch elementów zostaną posortowane. Nie tak z Dictionary<T,V>.

2. MSDN rozwiązuje różnicę między SortedList<T,V>i SortedDictionary<T,V>:

Klasa ogólna SortedDictionary (TKey, TValue) jest binarnym drzewem wyszukiwania z pobieraniem O (log n), gdzie n to liczba elementów w słowniku. Pod tym względem jest podobny do klasy generycznej SortedList (TKey, TValue). Te dwie klasy mają podobne modele obiektów i obie mają pobieranie O (log n). Tam, gdzie te dwie klasy różnią się, jest wykorzystanie pamięci oraz szybkość 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 wypełniana jednocześnie z posortowanych danych, SortedList (TKey, TValue) jest szybsze niż SortedDictionary (TKey, TValue).

Wspomniałbym o różnicy między słownikami.

Powyższe zdjęcie pokazuje, że Dictionary<K,V>jest to w każdym przypadku równe lub szybsze niż Sortedanalogowe, ale jeśli wymagana jest kolejność elementów, np. Do ich wydrukowania,Sorted wybiera się jeden.

Źródło: http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

Podsumowując wyniki testu wydajności - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable , wyniki od najlepszego do najgorszego dla różnych scenariuszy:

Zużycie pamięci:

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

Wstawki:

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

Operacje wyszukiwania:

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

operacje pętli foreach

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>

Widzę, że proponowane odpowiedzi koncentrują się na wydajności. Poniższy artykuł nie zawiera żadnych nowych informacji dotyczących wydajności, ale wyjaśnia podstawowe mechanizmy. Należy również zauważyć, że nie koncentruje się na trzech Collectiontypach wymienionych w pytaniu, ale dotyczy wszystkich typów w System.Collections.Genericprzestrzeni nazw.

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

Ekstrakty:

Słownik <>

Słownik jest prawdopodobnie najczęściej używaną asocjacyjną klasą kontenera. Słownik jest najszybszą klasą do asocjacyjnego wyszukiwania / wstawiania / usuwania, ponieważ używa tablicy skrótów pod okładkami . Ponieważ klucze są hashowane, typ klucza powinien poprawnie implementować GetHashCode () i Equals () lub należy podać zewnętrzny IEqualityComparer do słownika podczas konstrukcji. Czas wstawiania / usuwania / wyszukiwania elementów w słowniku jest amortyzowany jako stały czas - O (1) - co oznacza, że ​​bez względu na to, jak duży jest słownik, czas potrzebny na znalezienie czegoś pozostaje względnie stały. Jest to bardzo pożądane w przypadku szybkiego wyszukiwania. Jedynym minusem jest to, że słownik, z natury korzystający z tablicy skrótów, jest nieuporządkowany, więcnie możesz łatwo przeglądać po kolei elementów w Słowniku .

SortedDictionary <>

SortedDictionary jest podobny do Dictionary w użyciu, ale bardzo różni się implementacją. SortedDictionary wykorzystuje binarne drzewo pod kołdrą aby utrzymać pozycje w kolejności od klucza . W konsekwencji sortowania typ używany dla klucza musi poprawnie implementować IComparable, aby klucze mogły być poprawnie sortowane. Posortowany słownik wykorzystuje trochę czasu wyszukiwania na możliwość utrzymania pozycji w porządku, dlatego czasy wstawiania / usuwania / wyszukiwania w posortowanym słowniku są logarytmiczne - O (log n). Ogólnie rzecz biorąc, w przypadku czasu logarytmicznego można podwoić rozmiar zbioru i wystarczy wykonać tylko jedno dodatkowe porównanie, aby znaleźć element. Użyj SortedDictionary, jeśli chcesz szybko wyszukiwać, ale chcesz również mieć możliwość utrzymywania kolekcji w kolejności według klucza.

SortedList <>

SortedList to inna posortowana asocjacyjna klasa kontenera w kontenerach ogólnych. Po raz kolejny SortedList, podobnie jak SortedDictionary, używa klucza do sortowania par klucz-wartość . Jednak w przeciwieństwie do SortedDictionary elementy w SortedList są przechowywane jako posortowana tablica elementów. Oznacza to, że wstawienia i usunięcia są liniowe - O (n) - ponieważ usunięcie lub dodanie pozycji może wiązać się z przesunięciem wszystkich pozycji w górę lub w dół listy. Jednak czas wyszukiwania wynosi O (log n), ponieważ SortedList może użyć wyszukiwania binarnego, aby znaleźć dowolny element na liście według jego klucza. Więc dlaczego miałbyś kiedykolwiek chcieć to zrobić? Cóż, odpowiedź jest taka, że ​​jeśli zamierzasz załadować SortedList z góry, wstawianie będzie wolniejsze, ale ponieważ indeksowanie tablicy jest szybsze niż śledzenie łączy obiektów, wyszukiwania są nieznacznie szybsze niż SortedDictionary. Ponownie użyłbym tego w sytuacjach, w których chcesz szybko wyszukiwać i chcesz zachować porządek w kolekcji według klucza, a wstawienia i usunięcia są rzadkie.

Wstępne podsumowanie podstawowych procedur

Opinie są mile widziane, ponieważ jestem pewien, że nie wszystko ułożyło się dobrze.

• Wszystkie tablice mają określony rozmiar n.
• Niesortowana tablica = .Add / .Remove to O (1), ale .Item (i) to O (n).
• Posortowana tablica = .Add / .Remove to O (n), ale .Item (i) to O (log n).

Słownik

Pamięć

KeyArray(n) -> non-sorted array<pointer>
ItemArray(n) -> non-sorted array<pointer>
HashArray(n) -> sorted array<hashvalue>

Dodaj

1. Dodaj HashArray(n) = Key.GetHashnr O (1)
2. Dodaj KeyArray(n) = PointerToKeynr O (1)
3. Dodaj ItemArray(n) = PointerToItemnr O (1)

Usunąć

1. For i = 0 to n, znajdź igdzie HashArray(i) = Key.GetHash # O (log n) (posortowana tablica)
2. Usuń HashArray(i)# O (n) (posortowana tablica)
3. Usuń KeyArray(i)# O (1)
4. Usuń ItemArray(i)# O (1)

Zdobądź przedmiot

1. For i = 0 to n, znajdź igdzie HashArray(i) = Key.GetHash# O (log n) (posortowana tablica)
2. Powrót ItemArray(i)

Loop Through

1. For i = 0 to n, powrót ItemArray(i)

SortedDictionary

Pamięć

KeyArray(n) = non-sorted array<pointer>
ItemArray(n) = non-sorted array<pointer>
OrderArray(n) = sorted array<pointer>

Dodaj

1. Dodaj KeyArray(n) = PointerToKeynr O (1)
2. Dodaj ItemArray(n) = PointerToItemnr O (1)
3. For i = 0 to n, znajdź igdzie KeyArray(i-1) < Key < KeyArray(i)(używając ICompare) # O (n)
4. Dodaj OrderArray(i) = n# O (n) (posortowana tablica)

Usunąć

1. For i = 0 to nznajdź, igdzie KeyArray(i).GetHash = Key.GetHash# O (n)
2. Usuń KeyArray(SortArray(i))# O (n)
3. Usuń ItemArray(SortArray(i))# O (n)
4. Usuń OrderArray(i)# O (n) (posortowana tablica)

Zdobądź przedmiot

1. For i = 0 to nznajdź, igdzie KeyArray(i).GetHash = Key.GetHash# O (n)
2. Powrót ItemArray(i)

Loop Through

1. For i = 0 to n, powrót ItemArray(OrderArray(i))

SortedList

Pamięć

KeyArray(n) = sorted array<pointer>
ItemArray(n) = sorted array<pointer>

Dodaj

1. For i = 0 to n, znajdź igdzie KeyArray(i-1) < Key < KeyArray(i)(używając ICompare) # O (log n)
2. Dodaj KeyArray(i) = PointerToKey# O (n)
3. Dodaj ItemArray(i) = PointerToItem# O (n)

Usunąć

1. For i = 0 to nznajdź, igdzie KeyArray(i).GetHash = Key.GetHash# O (log n)
2. Usuń KeyArray(i)# O (n)
3. Usuń ItemArray(i)# O (n)

Zdobądź przedmiot

1. For i = 0 to nznajdź, igdzie KeyArray(i).GetHash = Key.GetHash# O (log n)
2. Powrót ItemArray(i)

Loop Through

1. For i = 0 to n, powrót ItemArray(i)

1. Gdy chcesz, aby kolekcja była sortowana według klucza podczas iteracji po niej. Jeśli nie potrzebujesz sortowania danych, lepiej będzie, jeśli masz tylko słownik, będzie miał lepszą wydajność.

2. SortedList i SortedDictionary robią w zasadzie to samo, ale są zaimplementowane w inny sposób, dlatego mają różne mocne i słabe strony wyjaśnione tutaj .

Próbując przypisać ocenę wydajności do każdego przypadku przedstawionego przez @Lev, użyłem następujących wartości:

• O (1) = 3
• O (log n) = 2
• O (n) = 1
• O (1) lub O (n) = 2
• O (log n) lub O (n) = 1,5

Wyniki są (wyższe = lepsze):

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

Oczywiście każdy przypadek użycia nada większą wagę pewnym operacjom.