SortedList<>, SortedDictionary<> et Dictionary<>.

Question

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

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

Answer 1

1. Lorsque l'on itère sur les éléments de l'un ou l'autre, les éléments sont triés. Ce n'est pas le cas avec Dictionary<T,V> .

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

La classe générique SortedDictionary(TKey, TValue) est un recherche binaire arbre avec une récupération de O(log n), où n est le nombre d'éléments dans le le dictionnaire. A cet égard, elle est similaire à la classe générique SortedList(TKey, TValue). Ces deux classes ont des modèles d'objets similaires et les deux permettent une récupération O(log n). Là où les deux classes diffèrent, c'est dans l'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) possède des opérations d'insertion et de suppression plus rapides pour les données non triées. pour les données non triées : O(log n) par opposition à O(n) pour SortedList(TKey, TValue).

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

Answer 2

Je mentionnerais 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 exemple pour les imprimer, Sorted un est choisi.

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

Answer 3

Pour résumer les résultats d'une Test de performance - 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 de boucle foreach

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

Answer 4

Je vois que les réponses proposées se concentrent sur la performance. L'article ci-dessous n'apporte rien de nouveau concernant les performances, mais il explique les mécanismes sous-jacents. Notez également qu'il ne se concentre pas sur les trois Collection types mentionnés dans la question, mais aborde tous les types de la System.Collections.Generic espace de noms.

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

Des extraits :

Dictionnaire<>

Le dictionnaire est probablement la classe de conteneur associative la plus utilisée. Le dictionnaire est la classe la plus rapide pour les recherches/insertions/suppressions associatives parce que il utilise une table de hachage sous les couvertures . Parce que les clés sont hachées, le type de clé doit implémenter correctement GetHashCode() et Equals() de manière appropriée ou vous devez fournir un IEqualityComparer externe au dictionnaire lors de la construction. Le temps d'insertion, de suppression et de consultation des éléments du dictionnaire est un temps constant amorti - O(1) - ce qui signifie que quelle que soit la taille du dictionnaire, le temps nécessaire pour trouver quelque chose reste relativement constant. C'est très souhaitable pour les recherches rapides. Le seul inconvénient est que le dictionnaire, de par la nature de l'utilisation d'une table de hachage, est non ordonné, donc vous ne pouvez pas facilement parcourir les éléments d'un dictionnaire pour .

SortedDictionary<>

Le SortedDictionary est similaire au Dictionary dans son utilisation mais très différent dans son implémentation. Le site SortedDictionary utilise un arbre binaire sous les couvertures pour maintenir les éléments dans l'ordre de la clé. . En conséquence du tri, le type utilisé pour la clé doit implémenter correctement IComparable afin que les clés puissent être correctement triées. Le dictionnaire trié échange un peu de temps de consultation contre la possibilité de maintenir les éléments dans l'ordre, ainsi les temps d'insertion/suppression/ consultation dans un dictionnaire trié sont logarithmiques - O(log n). En général, avec un temps logarithmique, vous pouvez doubler la taille de la collection et il suffit d'effectuer une comparaison supplémentaire pour trouver l'élément. Utilisez le SortedDictionary lorsque vous voulez des recherches rapides mais que vous souhaitez également pouvoir maintenir la collection dans l'ordre de la clé.

Liste triée<>

La SortedList est l'autre classe de conteneurs associatifs triés dans les conteneurs génériques. Encore une fois, SortedList, comme SortedDictionary, utilise une clé pour trier les paires clé-valeur . Contrairement à SortedDictionary, cependant, Les éléments d'une SortedList sont stockés sous la forme d'un tableau d'éléments triés. . Cela signifie que les insertions et les suppressions sont linéaires - O(n) - car la suppression ou l'ajout d'un élément peut impliquer le déplacement de tous les éléments vers le haut ou le bas de la liste. Le temps de recherche, cependant, est O(log n) parce que la SortedList peut utiliser une recherche binaire pour trouver n'importe quel élément de la liste par sa clé. Alors pourquoi vouloir faire cela ? Eh bien, la réponse est que si vous chargez la SortedList à l'avance, les insertions seront plus lentes, mais comme l'indexation des tableaux est plus rapide que le suivi des liens entre objets, les recherches sont légèrement plus rapides qu'avec un SortedDictionary. Une fois de plus, je l'utiliserais dans des situations où vous voulez des recherches rapides et où vous voulez maintenir la collection dans l'ordre de la clé, et où les insertions et les suppressions sont rares.

---

Résumé provisoire des procédures sous-jacentes

Tout commentaire est le bienvenu, car je suis sûr que je n'ai pas tout compris.

• Tous les tableaux sont de taille n .
• Tableau non trié = .Add/.Remove est O(1), mais .Item(i) est O(n).
• Tableau trié = .Add/.Remove est O(n), mais .Item(i) est O(log n).

Dictionnaire

Mémoire

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

Ajouter

1. Ajouter HashArray(n) = Key.GetHash # O(1)
2. Ajouter KeyArray(n) = PointerToKey # O(1)
3. Ajouter ItemArray(n) = PointerToItem # O(1)

Retirer

1. For i = 0 to n , trouver i donde HashArray(i) = Key.GetHash # O(log n) (tableau trié)
2. Retirer HashArray(i) # O(n) (tableau trié)
3. Retirer KeyArray(i) # O(1)
4. Retirer ItemArray(i) # O(1)

Obtenir un article

1. For i = 0 to n , trouver i donde HashArray(i) = Key.GetHash # O(log n) (tableau trié)
2. Retourner à ItemArray(i)

Boucle à travers

1. For i = 0 to n , retour ItemArray(i)

SortedDictionary

Mémoire

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

Ajouter

1. Ajouter KeyArray(n) = PointerToKey # O(1)
2. Ajouter ItemArray(n) = PointerToItem # O(1)
3. For i = 0 to n , trouver i donde KeyArray(i-1) < Key < KeyArray(i) (en utilisant ICompare ) # O(n)
4. Ajouter OrderArray(i) = n # O(n) (tableau trié)

Retirer

1. For i = 0 to n , trouver i donde KeyArray(i).GetHash = Key.GetHash # O(n)
2. Retirer KeyArray(SortArray(i)) # O(n)
3. Retirer ItemArray(SortArray(i)) # O(n)
4. Retirer OrderArray(i) # O(n) (tableau trié)

Obtenir un article

1. For i = 0 to n , trouver i donde KeyArray(i).GetHash = Key.GetHash # O(n)
2. Retourner à ItemArray(i)

Boucle à travers

1. For i = 0 to n , retour ItemArray(OrderArray(i))

Liste triée

Mémoire

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

Ajouter

1. For i = 0 to n , trouver i donde KeyArray(i-1) < Key < KeyArray(i) (en utilisant ICompare ) # O(log n)
2. Ajouter KeyArray(i) = PointerToKey # O(n)
3. Ajouter ItemArray(i) = PointerToItem # O(n)

Retirer

1. For i = 0 to n , trouver i donde KeyArray(i).GetHash = Key.GetHash # O(log n)
2. Retirer KeyArray(i) # O(n)
3. Retirer ItemArray(i) # O(n)

Obtenir un article

1. For i = 0 to n , trouver i donde KeyArray(i).GetHash = Key.GetHash # O(log n)
2. Retourner à ItemArray(i)

Boucle à travers

1. For i = 0 to n , retour ItemArray(i)

Answer 5

1. Lorsque vous voulez que la collection soit triée par clé lorsque vous l'itérez. Si vous n'avez pas besoin que vos données soient triées, il est préférable d'utiliser un simple dictionnaire, qui sera plus performant.

2. SortedList et SortedDictionary font à peu près la même chose, mais sont implémentés différemment et ont donc des forces et des faiblesses différentes. expliqué ici .