.NET structures de données: liste de tableaux, Liste, table de hachage, Dictionnaire, SortedList, SortedDictionary - Vitesse de la mémoire, et quand les utiliser?

si possible, utilisez des génériques. comprend:

• Liste au lieu de la liste de tableaux
• Dictionnaire de la place de la table de hachage

tout d'abord, toutes les collections en .net implémenter IEN innombrables.

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

donc, bien que les collections génériques ajoutent probablement des caractéristiques, pour la plupart:

• de la Liste est un générique de mise en œuvre de ArrayList.
• Dictionnaire est un générique de mise en œuvre de Hashtable

tableaux sont une collection de taille fixe que vous pouvez changer la valeur stockée à un indice donné.

SortedDictionary est un IDictionary qui est trié sur la base des clés. SortedList est un IDictionary qui est trié sur la base d'un IComparer requis.

ainsi, les implémentations D'IDictionary (celles supportant les fauteuils Keyvalu) sont: * Table de hachage * Dictionnaire * SortedList * SortedDictionary

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

de plus, la liste de liens est une implémentation de liste liée standard (la liste est un tableau-liste pour une récupération plus rapide).

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ès à des éléments en utilisant un index à base zéro) propriétés. IDictionary d'un autre côté signifie que vous pouvez accéder aux articles par n'importe quel-hashable index.

• Array , ArrayList et List tous implémentent IList . Dictionary , SortedDictionary , et Hashtable implement IDictionary .

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

• pour la complexité temporelle et spatiale de diverses opérations sur ces types, vous devriez consulter leur documentation.

• .NET les structures de données sont dans l'espace de noms System.Collections . Il existe des bibliothèques de type telles que PowerCollections qui offrent des structures de données supplémentaires.

• pour obtenir une compréhension approfondie des structures de données, consultez des ressources telles que CLRS .

Une bonne feuille de triche de mentionner la complexité des structures de données, algorithmes, etc.

je comprends la question - j'ai aussi trouvé (trouver?( j'ai fait le test en utilisant VB, mais j'imagine que C# serait la même chose, puisque les deux langues font la même chose au niveau CLR). Vous pouvez voir quelques résultats d'étalonnage effectués par moi ici (il y a aussi une discussion de quel type de données est le meilleur à utiliser dans quelles circonstances).

. structures de données réseau:

pour en savoir plus sur la différence entre ArrayList et List

matrices

comme l'indique un utilisateur, les tableaux sont la collection" old school "(Oui, les tableaux sont considérés comme une collection mais ne font pas partie de System.Collections ). Mais, ce qui est "vieille école" sur les tableaux en comparaison à d'autres collections, I. e ceux que vous avez énumérés dans votre titre (ici, ArrayList et List (Of T))? Nous allons commencer avec les bases en regardant les Tableaux.

Pour commencer, "1519190920 des" Tableaux de Microsoft .NET sont, "des mécanismes qui permettent de traiter plusieurs [logiquement liées à l'] les points qu'une seule collection," (voir article lié). Qu'est-ce que cela signifie? Les tableaux stockent les membres individuels (éléments) de façon 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 à partir de cette adresse.

au-delà de cela et contrairement à la programmation 101 conceptions communes, les tableaux peuvent vraiment être assez complexes:

les tableaux peuvent être de dimension simple, multidimensionnels, ou jadded (Jagged tableaux are worth reading about). Les tableaux eux-mêmes ne sont pas dynamiques: Une fois initialisés, un tableau de n taille réserve assez d'espace pour contenir n nombre d'objets. Le nombre d'éléments dans le tableau ne peut pas augmenter ou diminuer. Dim _array As Int32() = New Int32(100) réserve suffisamment d'espace sur le bloc mémoire pour que le tableau contienne 100 objets de type primitif Int32 (dans ce cas, le tableau est initialisé pour contenir 0s). L'adresse de ce bloc est renvoyée à _array .

Selon l'article, Common Language Specification (CLS) exige que tous les tableaux être basé sur zéro. Les tableaux en .NET prennent en charge les tableaux non-zéro; cependant, cela est moins courant. Comme un résultat de la "commune-ness" de tableaux à base zéro, Microsoft a passé beaucoup de temps à optimiser leurs performances ; par conséquent, les tableaux à base unique, à base zéro (SZs) sont" spéciaux " -et vraiment la meilleure mise en œuvre d'un tableau (par opposition à multidimensionnel, etc.)- parce que les SZs ont des instructions spécifiques de langue intermédiaire pour les manipuler.

tableaux sont toujours passés par référence (comme une adresse de mémoire) - une pièce importante du puzzle de tableau à savoir. Alors ils font la vérification des limites (lancera une erreur), la vérification des limites peut aussi être désactivée sur les tableaux.

encore une fois, le plus grand obstacle aux tableaux est qu'ils ne sont pas re-taille. Ils ont une capacité" fixe". Introduction D'ArrayList et de List (Of T) à notre histoire:

ArrayList - non générique de la liste

le ArrayList (avec List(Of T) - bien qu'il y ait quelques différences critiques, ici, expliqué plus tard), est peut - être mieux pensé que le prochain ajout à la collection (au sens large). ArrayList hérite de l'interface IList (un descendant de "ICollection"). Les ArrayLists, eux - mêmes, sont bulkier - exigeant plus overhead - que les listes.

IList ne permet pas la mise en œuvre de traiter les tableaux comme des listes de taille fixe (comme les tableaux); toutefois, au-delà de la fonctionnellement ajouté par les ArrayLists, il n'y a pas d'avantages réels à utiliser les ArrayLists qui sont de taille fixe comme ArrayLists (over Arrays) dans ce cas sont nettement plus lents.

D'après ma lecture, les ArrayLists ne peuvent pas être déchiquetés: "en utilisant des tableaux multidimensionnels comme éléments... n'est pas pris en charge". Encore un clou dans le cercueil des ArrayLists. Les ArrayLists ne sont pas non plus "typés" - ce qui signifie que, sous tout, un ArrayList est simplement un tableau dynamique D'objets: Object[] . Ce exige beaucoup de boxe (implicite) et unboxing (explicite) lors de la mise en œuvre ArrayLists, à nouveau l'ajout à leur tête.

pensée non corroborée: je pense que je me souviens soit avoir lu ou avoir entendu d'un de mes professeurs que les ArrayLists sont en quelque sorte l'enfant conceptuel bâtard de la tentative de passer des tableaux à des Collections de type Liste, c.-à-d. bien qu'ayant été une grande amélioration aux tableaux, ils ne sont plus la meilleure option que plus tard développement des collections

List(Of T): Ce Dernier est devenu (et espère)

la différence dans l'utilisation de la mémoire est assez significative pour qu'une liste (de Int32) consomme 56% moins de mémoire qu'un ArrayList contenant le même type primitif ( 8 MB contre 19 MB dans la démonstration liée de Monsieur ci-dessus: encore une fois, lié ici ) - bien que ce soit un résultat aggravé par le 64-bit machine. Cette différence démontre vraiment deux choses: premièrement( 1), un "objet" de type Int32 (ArrayList) est beaucoup plus grand qu'un type primitif Int32 pur (List); deuxièmement (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'une liste(de T) ? MSDN définit un List(Of T) comme "... une liste fortement tapée d'objets auxquels on peut accéder par index."L'importance ici est le bit "fortement tapé": une liste(de T) 'reconnaît' les types et stocke les objets comme leur type. Donc, un Int32 est stocké comme un Int32 et non un "151990920 de type". Ceci élimine les problèmes causés par boxing et unboxing.

MSDN spécifie que cette différence n'entre en jeu que lorsque l'on stocke des types primitifs et non des types de référence. aussi, la différence se produit vraiment sur une grande échelle: plus de 500 élément. Ce qui est plus intéressant, c'est que la documentation MSDN se lit comme suit: "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 en mieux. C'est l ' "équivalent générique" de ArrayList. Comme ArrayList, il n'est pas garanti d'être triée jusqu'triés (allez comprendre). List (Of T) a aussi quelques fonctionnalités ajoutées.

c'est assez bien écrit dans intellisense. Il suffit de taper système.Collection. Système ou .Collection.Génériques (de préférence) et vous obtiendrez une liste et une brève description de ce qui est disponible.

tables de hachage/Dictionnaires sont en O(1) de la performance, ce qui signifie que la performance n'est pas fonction de la taille. C'est important de le savoir.

EDIT: Dans la pratique, la durée moyenne de la complexité de la table de hachage/Dictionnaire<> recherches est O(1).

les collections génériques seront plus performantes que leurs contreparties non-génériques, en particulier lors de l'itération de nombreux articles. C'est parce que la boxe et la non-boxe ne se produisent plus.

Une remarque importante à propos de table de hachage vs Dictionnaire pour la haute fréquence systématique de négociation de l'ingénierie: Fil d'un Problème de Sécurité

table de hachage est thread-safe pour une utilisation par plusieurs threads. Les membres statiques de public de dictionnaire sont thread safe, mais les membres de n'importe quelle instance ne sont pas garantis pour être ainsi.

donc Hashtable reste le choix "standard" à cet égard.

en fait, je pense que MSDN aide à fournir des réponses assez bonnes à toutes ces questions. Il suffit de regarder.net collections.

il existe des différences subtiles et moins subtiles entre les collections génériques et non génériques. Ils utilisent simplement différentes structures de données sous-jacentes. Par exemple, Hashtable garantit un écrivain-plusieurs-lecteurs sans synchronisation. Le dictionnaire ne fonctionne pas.

les Plus populaires C# Structures de Données et des Collections

• Array
• ArrayList
• liste
• LinkedList
• Dictionnaire
• HashSet
• Pile
• file
• Sortlist

C#.NET a beaucoup de structures de données différentes, par exemple, l'un des plus communs est un tableau. Cependant C# vient avec beaucoup plus de structures de données de base. Le choix de la structure de données correcte à utiliser fait partie de la rédaction d'un programme bien structuré et efficace.

dans cet article je vais passer en revue les structures de données intégrées C#, y compris les nouveaux introduit en C#.NET 3.5. Notez que bon nombre de ces structures de données s'appliquent à d'autres langages de programmation.

Array

la structure de données peut-être la plus simple et la plus commune est le tableau. Un tableau C# est essentiellement une liste d'objets. Ses traits de définition sont que tous les objets sont du même type (dans la plupart des cas) et il existe un certain nombre d'entre eux. La nature d'un tableau permet un accès très rapide aux éléments basés sur leur position dans la liste (aussi connu sous le nom d'index). Un tableau C# est défini comme ceci:

[object type][] myArray = new [object type][number of elements]

quelques exemples:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

Comme vous pouvez le voir dans l'exemple ci-dessus, un tableau peut être initialisée avec aucun élément ou d'un ensemble de valeurs existantes. Insertion de valeurs dans un tableau est simple tant qu'ils s'inscrivent. Opération devient cher quand il y a plus d'éléments que la taille de la matrice, la matrice doit être élargi. Cela prend plus de temps parce que tous les éléments existants doivent être copiés sur le nouveau, plus grand tableau.

ArrayList

la structure de données C#, ArrayList, est un tableau dynamique. Cela signifie qu'un ArrayList peut avoir n'importe quelle quantité d'objets et de n'importe quel type. Cette structure de données a été conçue pour simplifier processus d'ajout de nouveaux éléments dans un tableau. Sous le capot, un ArrayList est un réseau dont la taille est doublée chaque fois qu'il manque de place. Doubler la taille du tableau interne est une stratégie très efficace qui réduit la quantité de copie d'éléments à long terme. Nous n'entrerons pas dans la preuve ici. La structure des données est très simple à utiliser:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

l'inconvénient de la structure de données ArrayList est que l'on doit jeter les valeurs récupérées de nouveau dans leur type original:

int arrayListValue = (int)myArrayList[0]

Sources et plus d'informations vous pouvez trouver ici :

• C# De Structures De Données
• Collections et structures de données
• liste vs IEnumerable vs IQueryable vs ICollection vs IDictionary
• système.Collection.Générique L'espace de noms
• système.Les Collections De L'Espace De Noms