SortedList <>, SortedDictionary <> et Dictionary <>

Question

Je trouve que SortedList<TKey, TValue>SortedDictionary<TKey, TValue> et Dictionary<TKey, TValue> implémentent les mêmes interfaces.

1. Quand devrions-nous opter pour SortedList et SortedDictionary sur Dictionary?
2. Quelle est la différence entre SortedList et SortedDictionary en termes d'application?

Answer 1

1. Lorsque itérer sur les éléments dans l'une des deux, les éléments seront triés. Ce n'est pas le cas avec Dictionary<T,V>.

2. MSDN traite de la différence entre SortedList<T,V> et SortedDictionary<T,V>:

Le SortedDictionary (TKey, TValue) classe générique est un binary search tree avec O (log n) la récupération, où n est le nombre d'éléments dans le dictionnaire. À cet égard, il est similaire à la classe générique SortedList (TKey, TValue). Les deux classes ont des modèles d'objets similaires et ont toutes deux une récupération O (log n). Lorsque les deux classes diffèrent est en utilisation de la mémoire et la vitesse d'insertion et de retrait:

SortedList (TKey, TValue) utilise moins de mémoire que SortedDictionary (TKey, TValue ).

SortedDictionary (TKey, TValue) a insertion plus rapide et le retrait opérations pour les données non triés: O (log n) par opposition à O (N) pour SortedList (TKey, TValue).

Si la liste est remplie à la fois à partir de données triées, SortedList (TKey, TValue) est plus rapide que SortedDictionary (TKey, TValue).

Answer 2

1. Lorsque vous voulez que la collection à trier par clé lorsque vous itérer dessus. Si vous n'avez pas besoin de trier vos données, il est préférable d'utiliser uniquement un dictionnaire, car les performances seront meilleures.

2. SortedList et SortedDictionary font pratiquement la même chose, mais sont implémentés différemment, ont donc des forces et des faiblesses différentes explained here.

Answer 3

Je vous signale la différence entre les dictionnaires.

L'image ci-dessus montre que Dictionary<K,V> est égal ou plus rapide dans tous les cas que Sorted analogique, mais si l'ordre des éléments est requis, par ex. pour les imprimer, Sorted on est choisi.

Src: http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

Answer 4

Pour résumer les résultats d'une Performance Test - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable, les résultats du meilleur au pire pour différents scénarios:

Utilisation de la mémoire:

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

Insertions:

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

opérations de recherche:

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

opérations en boucle foreach

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