Capacité initiale de types de collection, par exemple, le Dictionnaire, la Liste

Certains types de collection dans .Net disposer en option d'une "Capacité Initiale" paramètre du constructeur. Par exemple:

Dictionary<string, string> something = new Dictionary<string,string>(20);

List<string> anything = new List<string>(50);

Je n'arrive pas à trouver ce que le défaut initial de la capacité d'accueil est de ces objets sur le site MSDN.

Si je sais que je vais seulement le stockage de 12 ou alors des éléments dans un dictionnaire, n'est-il pas logique de définir la capacité initiale de quelque chose comme 20?

Mon raisonnement est, en supposant que la capacité se développe comme il le fait pour un StringBuilder, qui double chaque fois que la capacité est touché, et chaque réaffectation est coûteux, pourquoi ne pas pré-régler la taille de quelque chose que vous savez dans votre prise de données, avec certains chambre supplémentaire juste au cas où? Si la capacité initiale est de 100, et je sais que je vais seulement besoin d'une douzaine ou alors, il semble comme si le reste de la mémoire est allouée pour rien.

InformationsquelleAutor Neil N | 2010-05-03
  1. 70

    Si les valeurs par défaut ne sont pas documentés, la raison en est probablement la meilleure capacité initiale est de un détail de l'implémentation et sous réserve de changements entre les versions framework. Qui est, vous ne devriez pas écrire le code qui suppose une certaine valeur par défaut.

    Le constructeur surcharges avec une capacité pour les cas dans lesquels vous savez mieux que la classe de ce nombre d'éléments sont à prévoir. Par exemple, si vous créez une collection de 50 valeurs et le savoir que ce nombre n'augmente jamais, vous pouvez initialiser la collection avec une capacité de 50, afin de ne pas avoir à redimensionner si la valeur par défaut de la capacité est plus faible.

    Cela dit, vous pouvez déterminer les valeurs par défaut à l'aide de Réflecteur. Par exemple, dans .NET 4.0 (et probablement les versions précédentes ainsi),

    • une Liste<T> est initialisé avec une capacité de 0. Lorsque le premier élément est ajouté, il est réinitialisé à une capacité de 4. Par la suite, chaque fois que la capacité est atteinte, la capacité est doublée.

    • un Dictionnaire<T> est initialisée avec une capacité de 0 ainsi. Mais il utilise un complètement différent de l'algorithme d'augmentation de la capacité: il augmente la capacité de toujours des nombres premiers.

    • Le premier numéro de calcul est susceptible de faire face à des collisions de hachage et de sondage pour l'entrée des lieux. Selon le mécanisme interne si ils ne font que stocker une valeur à chaque hachage puis ils ont besoin secondaires des emplacements de stockage. Si vous n'utilisez pas un nombre premier, alors vous pouvez peut-être trouver un hash que vous pouvez échouer à insérer.
    • Dictionnaire<T> utilise le chaînage. Le premier numéro de la table des tailles de compenser le manque de fonctions de hachage. Bon les fonctions de hachage de produire des distributions aléatoires; puissance de deux dimensions de la table sont modernes utilisent des tables de hachage (l' .net de la table de hachage a été basé sur le Java table de hachage, qui a également utilisé des nombres premiers, parce que c'était une vieille façon de faire, dans les jours de mauvais fonctions de hachage). Parce que Microsoft n'a pas intégré dans hachage de la combinaison de méthodes, de nombreux maison de construction de fonctions de hachage engendrer de mauvaises distributions, de sorte que le nombre premier choix compense, parfois, jusqu'à la fonction de hachage produit des multiples de nombres premiers.
    • de deux dimensions de la table sont modernes utilisent des tables de hachage". La rouille utilise des puissances de deux et de ses tables de hachage sont nettement plus lente .NET est parce qu'il exige beaucoup plus compliqué de fonctions de hachage pour éviter les collisions.
    • Harrop les Collisions sont évitées grâce à la haute qualité en utilisant les fonctions de hachage. La taille de la Table devient alors une variable indépendante.
    InformationsquelleAutor dtb
  2. 9

    La vérification de la source, la valeur par défaut pour les deux List<T> et Dictionary<TKey, TValue> est de 0.

    • Dans .Net 4.5 la capacité supplémentaire est en fait 3. Oui, le constructeur par défaut des appels de surcharger le constructeur avec une valeur de la capacité de 0, mais la quand le constructeur appelle la méthode Initialize de la taille est fixée à 3. La taille réelle du dictionnaire est déterminé à partir d'un appel à HashHelpers.GetPrime(capacité) qui retourne le prochain nombre premier c'est plus de la condition de la capacité. Ainsi, dans .Net 4.5 la capacité initiale d'un Dictionnaire est de 3. Les listes ont un défaut de la capacité de 0, mais la capacité va de 4 après avoir ajouté le premier élément de la liste.
    InformationsquelleAutor SLaks
  3. 9

    Si vous connaissez la taille, puis le dire; un mineur d'optimisation dans la plupart des "petits" des cas, mais utile pour les grandes collections. Je principalement vous inquiéter à ce sujet si je jette un "décent" quantité de données, comme il peut, puis éviter d'avoir à allouer, de copie et de collecter de multiples tableaux.

    La plupart des collections, en effet, utiliser une stratégie de doublement.

    InformationsquelleAutor Marc Gravell
  4. 2

    Un autre problème avec l'ConcurrentDictionary (actuellement) et à l'aide de son constructeur pour définir une taille initiale, c'est que sa performance semble être entravée.

    Par exemple, voici un exemple de code et de repères j'ai essayé.

    J'ai couru le code sur ma machine et a obtenu des résultats similaires.

    Lorsque la taille initiale est spécifié, il ne fait rien pour augmenter la ConcurrentDictionary de la vitesse lors de l'ajout d'objets. Techniquement, je pense qu'il devrait parce qu'il n'a pas à prendre de temps ou de ressources pour redimensionner lui-même.

    Oui, il ne peut pas courir aussi vite que normal d'un Dictionnaire, mais je serais encore attendre un ConcurrentDictionary avec sa taille initiale définie à la cohérence, des performances plus rapides qu'un ConcurrentDictionary qui ne possède pas sa taille initiale, surtout lorsque l'on sait à l'avance le nombre d'éléments qui vont être ajoutés.

    Donc la morale de l'histoire est le réglage de la taille initiale ne garantit pas toujours une amélioration de la performance.

    InformationsquelleAutor