Question Structures de données .NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary - Vitesse, mémoire et quand les utiliser?


.NET a beaucoup de structures de données complexes. Malheureusement, certains d'entre eux sont assez similaires, et je ne suis pas toujours sûr de savoir quand en utiliser un et quand en utiliser un autre. La plupart de mes livres C # et Visual Basic en parlent dans une certaine mesure, mais ils ne vont jamais vraiment dans les détails.

Quelle est la différence entre Array, ArrayList, List, Hashtable, Dictionnaire, SortedList et SortedDictionary?

Lesquels sont énumérables (IList - peut-on faire des boucles foreach)? Lesquels utilisent des paires clé / valeur (IDict)?

Qu'en est-il de l'empreinte mémoire? Vitesse d'insertion? Vitesse de récupération?

Y a-t-il d'autres structures de données qui valent la peine d'être mentionnées?

Je suis toujours à la recherche de plus de détails sur l'utilisation de la mémoire et la vitesse (notation Big-O).


189
2017-09-24 17:47


origine


Réponses:


Du haut de ma tête:

  • Array* - représente un tableau de mémoire old-school - un peu comme un alias pour un normal type[] tableau. Peut énumérer Ne peut pas croître automatiquement Je suppose que la vitesse d'insertion et de retrival est très rapide.

  • ArrayList - tableau en croissance automatique. Ajoute plus de frais généraux. Peut enum., Probablement plus lent qu'un tableau normal mais toujours assez rapide. Ceux-ci sont beaucoup utilisés dans .NET

  • List - un de mes favs - peut être utilisé avec des génériques, vous pouvez donc avoir un tableau fortement typé, par ex. List<string>. Autre que cela, agit très comme ArrayList

  • Hashtable - plaine vieille hashtable. O (1) à O (n) pire cas. Peut énumérer les propriétés de la valeur et des clés, et faire des paires clé / val

  • Dictionary - même que ci-dessus seulement fortement typé via des génériques, tels que Dictionary<string, string>

  • SortedList - une liste générique triée. Ralentit à l'insertion car il doit déterminer où mettre les choses. Peut enum., Probablement le même sur la récupération car il n'a pas à recourir, mais la suppression sera plus lente qu'une simple liste ancienne.

J'ai tendance à utiliser List et Dictionary tout le temps - une fois que vous commencez à les utiliser fortement typés avec des génériques, il est vraiment difficile de revenir aux standards non génériques.

Il y a aussi beaucoup d'autres structures de données - il y a KeyValuePair que vous pouvez utiliser pour faire des choses intéressantes, il y a un SortedDictionary ce qui peut être utile aussi.


136
2017-09-24 18:00



Si possible, utilisez des génériques.  Ceci comprend:

  • Liste au lieu de ArrayList
  • Dictionnaire au lieu de HashTable

25
2017-09-24 17:52



Tout d'abord, toutes les collections dans .NET implémentent IEnumerable.

Deuxièmement, beaucoup de collections sont des doublons parce que les génériques ont été ajoutés dans la version 2.0 du framework.

Ainsi, bien que les collections génériques ajoutent probablement des fonctionnalités, la plupart du temps:

  • List est une implémentation générique de ArrayList.
  • Le dictionnaire est une implémentation générique de Hashtable

Les tableaux sont une collection de taille fixe que vous pouvez modifier la valeur stockée à un index donné.

SortedDictionary est un IDictionary trié en fonction des clés. SortedList est un IDictionary trié en fonction d'un IComparer requis.

Ainsi, les implémentations IDictionary (celles qui supportent KeyValuePairs) sont: * Hashtable * Dictionnaire * SortedList * SortedDictionary

Une autre collection ajoutée dans .NET 3.5 est le Hashset. C'est une collection qui supporte les opérations de set.

De plus, la propriété LinkedList est une implémentation standard de liste liée (la liste est une liste de tableaux pour une récupération plus rapide).


19
2017-09-24 18:05



Voici quelques conseils généraux pour vous:

  • Vous pouvez utiliser foreach sur les types qui mettent en œuvre IEnumerable. IList est essentiellement un IEnumberable avec Count et Item (accéder aux éléments en utilisant un index à base zéro) propriétés. IDictionary D'un autre côté, vous pouvez accéder aux éléments par index indexable.

  • Array, ArrayList et List tous les outils IList. Dictionary, SortedDictionary, et Hashtable mettre en place IDictionary.

  • Si vous utilisez .NET 2.0 ou supérieur, il est recommandé d'utiliser des contreparties génériques des types mentionnés.

  • Pour la complexité en temps et en espace des différentes opérations sur ces types, vous devriez consulter leur documentation.

  • Les structures de données .NET sont en System.Collections espace de nommage. Il existe des bibliothèques de types telles que PowerCollections qui offrent des structures de données supplémentaires.

  • Pour bien comprendre les structures de données, consultez des ressources telles que CLRS.


17
2018-06-17 12:40



Une bonne feuille de triche mentionner les complexités pour les structures de données, les algorithmes, etc.


16
2017-11-11 08:56



Je sympathise avec la question - j'ai aussi trouvé (trouver?) Le choix déconcertant, alors je me suis lancé scientifiquement pour voir quelle structure de données est la plus rapide (j'ai fait le test avec VB, mais j'imagine que C # serait le même, faire la même chose au niveau CLR). Tu peux voir quelques résultats d'analyse comparative menée par moi ici (il y a aussi une discussion sur le type de données qu'il est préférable d'utiliser dans quelles circonstances).


5
2017-10-13 14:56



Structures de données .NET:

Plus à la conversation sur pourquoi ArrayList et List sont réellement différents

Tableaux

Comme l’indique un utilisateur, les tableaux constituent la collection «old school» (oui, les tableaux sont considérés comme une collection mais ne font pas partie de System.Collections). Mais qu'est-ce que "old school" à propos des tableaux par rapport aux autres collections, c'est-à-dire celles que vous avez listées dans votre titre (ici, ArrayList et List (Of T))? Commençons par les bases en regardant les tableaux.

Commencer, Tableaux dans Microsoft .NET sont, "des mécanismes qui vous permettent de traiter plusieurs éléments [logiquement liés] en une seule collection" (voir l'article lié). Qu'est-ce que ça veut dire? Les tableaux stockent des membres individuels (éléments) de manière séquentielle, l'un après l'autre en mémoire avec une adresse de départ. En utilisant le tableau, nous pouvons facilement accéder aux éléments stockés séquentiellement en commençant à cette adresse.

Au-delà de cela et contrairement à la programmation de 101 conceptions communes, Arrays peut vraiment être assez complexe:

Les tableaux peuvent être à une seule dimension, multidimensionnels ou jaddés (les tableaux irréguliers méritent d'être lus). Les tableaux eux-mêmes ne sont pas dynamiques: une fois initialisé, un tableau de n la taille réserve suffisamment d'espace pour contenir n nombre d'objets. Le nombre d'éléments dans le tableau ne peut pas croître ou diminuer. Dim _array As Int32() = New Int32(100) réserve suffisamment d'espace sur le bloc de mémoire pour que le tableau contienne 100 objets de type primitif Int32 (dans ce cas, le tableau est initialisé pour contenir des 0). L'adresse de ce bloc est renvoyée à _array.

Selon l'article, Spécification commune du langage (CLS) requiert que tous les tableaux soient basés sur zéro. Les tableaux dans .NET prennent en charge les tableaux non basés sur zéro; Cependant, c'est moins commun. En raison de la "banalité" des baies de base zéro, Microsoft a dépensé beaucoup de temps pour optimiser leurs performances; par conséquent, les tableaux à dimension unique et à base zéro (SZs) sont "spéciaux" - et constituent la meilleure implémentation d'un tableau (par opposition à multidimensionnel, etc.) - car les SZ ont des instructions de langage intermédiaire spécifiques pour les manipuler.

Les tableaux sont toujours transmis par référence (en tant qu'adresse mémoire) - une pièce importante du puzzle Array à connaître. Alors qu'ils effectuent des vérifications de limites (lanceront une erreur), la vérification des limites peut également être désactivée dans les tableaux.

Encore une fois, le plus grand obstacle aux tableaux est qu'ils ne sont pas redimensionnables. Ils ont une capacité "fixe". Présentation de ArrayList et List (Of T) à notre histoire:

ArrayList - liste non générique

le ArrayList (de même que List(Of T) - bien qu'il y ait quelques différences critiques, expliquées plus loin ici - est peut-être mieux considéré comme le prochain ajout aux collections (au sens large). ArrayList hérite de la IList (un descendant de 'ICollection') interface. ArrayLists, eux-mêmes, sont plus volumineux - nécessitant plus aérien - que les listes.

IList permet à l'implémentation de traiter les tableaux en tant que listes de taille fixe (comme les tableaux); Cependant, au-delà de la fonctionnalité supplémentaire ajoutée par ArrayLists, il n'y a pas de réel avantage à utiliser ArrayLists qui est de taille fixe car les ArrayLists (sur Arrays) dans ce cas sont nettement plus lents.

De mon point de vue, ArrayLists ne peut pas être déchiqueté: "L'utilisation de tableaux multidimensionnels comme éléments n'est pas prise en charge". Encore une fois, un autre clou dans le cercueil de ArrayLists. Les ArrayLists ne sont pas non plus "typés" - ce qui signifie que, sous tout, ArrayList est simplement un tableau dynamique d'objets: Object[]. Cela nécessite beaucoup de boxe (implicite) et unboxing (explicite) lors de l'implémentation de ArrayLists, ce qui ajoute encore à leur surcharge.

Pensée non fondée: Je pense que je me souviens avoir lu ou entendu l’un de mes professeurs que ArrayLists est en quelque sorte l’enfant conceptuel bâtard de la tentative de passer de tableaux à des collections de type liste, c’est-à-dire ils ne sont plus la meilleure option à mesure que le développement des collections

List (Of T): Qu'est-ce que ArrayList est devenu (et espérait être)

La différence d’utilisation de la mémoire est assez importante pour qu’une liste (Of Int32) consomme 56% de mémoire en moins par rapport à une ArrayList contenant le même type primitif (8 Mo contre 19 Mo dans la démonstration liée ci-dessus: ici) - bien que ce soit un résultat composé par la machine 64 bits. Cette différence démontre vraiment deux choses: d'abord (1), un "objet" de type Int32 en boîte (ArrayList) est beaucoup plus gros qu'un type primitif Int32 pur (List); deuxième (2), la différence est exponentielle en raison du fonctionnement interne d'une machine 64 bits.

Alors, quelle est la différence et qu'est-ce qu'un Liste (Of T)? MSDN définit un List(Of T) as, "... une liste fortement typée d'objets accessibles par index." L'importance ici est le bit "fortement typé": un List (Of T) "reconnaît" les types et stocke les objets comme leur type. Donc, un Int32 est stocké en tant que Int32 et pas un Object type. Cela élimine les problèmes causés par la boxe et le déballage.

MSDN spécifie que cette différence entre en jeu uniquement lors du stockage des types primitifs et non des types de référence. Trop, la différence se produit vraiment à grande échelle: plus de 500 éléments. Ce qui est plus intéressant, c'est que la documentation MSDN lit, "Il est à votre avantage d'utiliser l'implémentation spécifique au type de la classe List (Of T) au lieu d'utiliser la classe ArrayList ...."

Essentiellement, List (Of T) est ArrayList, mais mieux. C'est l'équivalent générique de ArrayList. Comme ArrayList, il n'est pas garanti d'être trié jusqu'à trié (allez figure). List (Of T) a également des fonctionnalités supplémentaires.


5
2017-09-24 17:54



Ils sont bien expliqués dans intellisense. Juste taper System.Collections. ou System.Collections.Generics (préféré) et vous obtiendrez une liste et une courte description de ce qui est disponible.


3
2017-09-24 21:04



Hashtables / Dictionnaires sont des performances O (1), ce qui signifie que les performances ne sont pas fonction de la taille. C'est important de savoir.

EDIT: En pratique, la complexité temporelle moyenne des recherches Hashtable / Dictionary <> est O (1).


3
2017-09-28 15:05



Les collections génériques seront plus performantes que leurs homologues non génériques, en particulier lorsqu'elles parcourent de nombreux éléments. C'est parce que la boxe et le désencapsulation ne se produisent plus.


3
2017-08-27 19:59



Une note importante à propos de Hashtable vs Dictionary pour l'ingénierie de trading systématique à haute fréquence: Thread Safety Issue

Hashtable est compatible avec les threads pour une utilisation par plusieurs threads. Les membres statiques du dictionnaire sont thread-safe, mais les membres d'instance ne sont pas garantis d'être ainsi.

Hashtable reste donc le choix «standard» à cet égard.


2
2017-09-24 17:52