Quand utiliser un SortedList <TKey, TValue> sur un dictionnaire trié <TKey, TValue> ?

Question

Cela peut sembler être un double de cette question, qui pose la question "Quelle est la différence entre SortedList et SortedDictionary?" Malheureusement, les réponses ne sont rien de plus que citer la documentation MSDN (qui stipule clairement qu'il y a de la performance et de l'utilisation de la mémoire différences entre les deux) mais ne pas vraiment répondre à la question.

En fait (et donc, cette question n'a pas obtenir les mêmes réponses), selon le site web MSDN:

L' SortedList<TKey, TValue>générique la classe est un arbre de recherche binaire avec O(log n) de récupération, où n est le nombre d'éléments dans le dictionnaire. En cela, il est semblable à l' SortedDictionary<TKey, TValue>générique classe. Les deux classes ont les mêmes modèles d'objet, et les deux ont O(log n) de la récupération. Où les deux classes diffèrent, c'est dans l'utilisation de la mémoire et de la vitesse de l'insertion et le retrait:

• SortedList<TKey, TValue> utilise moins de de mémoire qu' SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue>a plus vite l'insertion et le retrait opérations pour des données non triées, O(log n) contrairement à O(n) pour SortedList<TKey, TValue>.

• Si la liste est remplie tout à la fois à partir de données triées, SortedList<TKey, TValue> est plus rapide que SortedDictionary<TKey, TValue>.

Donc, clairement, ce serait indiqué qu' SortedList<TKey, TValue> est le meilleur choix , sauf si vous avez besoin plus rapidement insérer et supprimer des opérations pour les ménagères de données.

La question demeure, compte tenu des informations ci-dessus quelles sont les pratiques (dans le monde réel, analyse de cas, etc.) raisons pour l'utilisation d'un SortedDictionary<TKey, TValue>? Basé sur l'information sur le rendement, cela impliquerait qu'il n'y a vraiment pas besoin d' SortedDictionary<TKey, TValue> à tous.

Answer 1

Je ne sais pas quelle est la précision de la documentation MSDN est sur SortedList et SortedDictionary. Il semble dire que les deux sont mis en œuvre à l'aide d'un arbre de recherche binaire. Mais si le SortedList utilise un arbre de recherche binaire, pourquoi serait-il beaucoup plus lent sur les ajouts que SortedDictionary?

De toute façon, voici quelques résultats de test de performances.

Chaque test se déroule sur un SortedList / SortedDictionary contenant 10 000 int32 clés. Chaque essai est répété 1.000 fois (Communiqué de construire, exécuter sans Débogage).

Le premier groupe de tests d'ajouter des touches de 0 à 9 999. Le second groupe d'épreuves ajouter hasard en traînant les touches de 0 à 9 999 habitants (chaque numéro est ajouté exactement une fois).

***** Tests.PerformanceTests.SortedTest

SortedDictionary Add sorted: 4411 ms
SortedDictionary Get sorted: 2374 ms


SortedList Add sorted: 1422 ms
SortedList Get sorted: 1843 ms

***** Tests.PerformanceTests.UnsortedTest

SortedDictionary Add unsorted: 4640 ms
SortedDictionary Get unsorted: 2903 ms


SortedList Add unsorted: 36559 ms
SortedList Get unsorted: 2243 ms

Comme avec tout le profilage, l'important, c'est la performance relative, et non pas les chiffres réels.

Comme vous pouvez le voir, sur des données triées de la liste triée est plus rapide que la SortedDictionary. Sur des données non triées de la SortedList est légèrement plus rapide sur la récupération, mais environ 9 fois plus lent sur l'ajout d'.

Si les deux sont à l'aide d'arbres binaires à l'interne, il est assez surprenant que l'opération d'Ajout sur des données non triées est donc mcuh plus lent pour SortedList. Il est possible que la liste triée peut aussi ajouter des éléments à une triés linéaire de la structure de données en même temps, qui serait-il ralentir.

Cependant, vous devez vous attendre à l'utilisation de la mémoire d'un SortedList être de valeur égale ou supérieure ou au moins égale à un SortedDictionary. Mais cela contredit ce que la documentation MSDN dit.

Answer 2

Je ne sais pas pourquoi MSDN dit qu' SortedList<TKey, TValue> utiliser un arbre binaire pour sa mise en œuvre, car si vous regardez le code avec un décompilateur comme Reflector vous vous rendez compte que ses pas vrai.

SortedList<TKey, TValue> est tout simplement un tableau qui se développe au cours du temps.

Chaque fois que vous insérez un élément, vérifiez d'abord si le tableau a une capacité suffisante, si pas, un plus grand tableau est recréé et de vieux éléments sont copiés dans celui-ci (comme List<T>)

Après cela, il recherche où insérer l'élément, à l'aide d'une recherche binaire (c'est possible car le tableau est indexable et déjà trié).

Pour garder le tableau trié, il se déplace (ou pousse) tous les éléments situés après la position de l'élément à insérer par une position (à l'aide d' Array.Copy()).

Par exemple :

// we want to insert "3" 

2  
4  <= 3
5
8
9
.      
.      
.  

// we have to move some elements first

2
.  <= 3
4 
5  |
8  v
9
.
.

Ce qui explique pourquoi la performance de l' SortedList est si mauvais quand vous insérez des éléments non triés. Il a re-copier certains éléments presque chaque insertion. Le seul cas où il n'a pas à être fait, c'est lorsque l'élément doit être inséré à la fin du tableau.

SortedDictionary<TKey, TValue> est différent et l'utilisation d'un arbre binaire à insérer et récupérer les éléments. Il a également un certain coût à insérer parce que parfois, l'arbre doivent être ré-équilibré (mais pas tous d'insertion).

La Performance est tout à fait similaire, tandis que la recherche d'un élément avec SortedList ou SortedDictionary parce qu'ils utilisent tous deux une recherche binaire.

---

À mon avis, vous devriez ne jamais les utiliser SortedList pour trier un tableau. Sauf si vous avez très peu d'éléments, il sera toujours plus rapide pour insérer des valeurs dans une liste (ou un tableau), puis appelez Sort() méthode.

SortedList est principalement utile lorsque vous avez une liste de valeurs déjà trié (par exemple: à partir de la base de données), vous voulez garder un tri et d'effectuer certaines opérations qui prennent avantage c'est triée (par exemple: Contains() méthode de SortedList effectue une recherche binaire à la place de la recherche linéaire)

SortedDictionary offre les mêmes avantages que d' SortedList mais fonctionne mieux si les valeurs à insérer ne sont pas déjà triées.

---

EDIT : Si vous êtes en utilisant .NET Framework 4.5, une alternative à l' SortedDictionary<TKey, TValue> est SortedSet<T>. Il fonctionne de la même manière qu' SortedDictionary, à l'aide d'un arbre binaire, mais les clés et les valeurs sont les mêmes ici.

Answer 3

Sont-ils fait pour deux fins différentes?

Il n'y a pas beaucoup de différence sémantique de ces deux types de collection dans .FILET de faire. Ils offrent tous deux des incrustée de recherche ainsi que de garder les entrées dans l'ordre de tri des clés. Dans la plupart des cas, vous serez ok avec l'un d'eux. Peut-être le seul élément de différenciation serait la récupération indexée SortedList permis.

Mais la performance?

Cependant il y a une différence de performance qui pourrait être le plus important facteur de choisir entre eux. Voici un tableau de vue de leur complexité asymptotique.

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

Résumé

À peu près résumer, vous voulez un SortedList<K, V> lorsque:

1. vous avez besoin d'indexés de recherche.
2. il est souhaitable d'avoir la moindre surcharge de la mémoire.
3. vos données sont déjà triées (dites que vous obtenir il déjà commandé à partir de db).

Vous voulez plutôt que de privilégier une SortedDictionary<K, V> lorsque:

1. relative globale des questions de rendement (à l'égard de mise à l'échelle).
2. vos données d'entrée n'est pas ordonné.

L'écriture de code

Les deux SortedList<K, V> et SortedDictionary<K, V> œuvre IDictionary<K, V>, donc dans votre code, vous pouvez revenir IDictionary<K, V> à partir de la méthode ou de déclarer la variable comme IDictionary<K, V>. Fondamentalement masquer le détail de l'implémentation, et le code à l'encontre de l'interface.

IDictionary<K, V> x = new SortedDictionary<K, V>(); //for eg. 

À l'avenir, il est plus facile de passer de soit dans le cas où vous n'êtes pas heureux avec des caractéristiques de performance d'une collection.

---

Pour plus d'informations sur les deux types de collection voir l'original question liée.

Answer 4

Représentation visuelle des différences de performance.

Answer 5

C'est tout là est à lui. La récupération des clés est comparable, mais l'addition est beaucoup plus rapide avec les Dictionnaires.

J'essaie d'utiliser SortedList autant que possible, car il me permet d'itérer sur les touches et de la valeur des collections. Ce n'est pas possible avec SortedDictionary autant que je sache.

Je ne suis pas sûr à ce sujet, mais comme je sais que les Dictionnaires de stocker des données dans une structure d'Arbre, alors que la Liste de stocker des données dans des tableaux linéaires. Ce qui explique pourquoi l'insertion et le retrait est beaucoup plus rapide avec les dictionnaires, depuis moins de mémoire doit être déplacé autour de. Il explique également pourquoi vous pouvez effectuer une itération sur SortedLists mais pas SortedDictionary.