Un dictionnaire générique .NET doit-il être initialisé avec une capacité égale au nombre d'éléments qu'il contiendra?

Question

Si j'ai par exemple 100 éléments qui seront stockés dans un dictionnaire, dois-je l'initialiser ainsi?

var myDictionary = new Dictionary<Key, Value>(100);

Je crois comprendre que le dictionnaire .NET se redimensionne de manière interne lorsqu'il atteint un chargement donné et que le seuil de chargement est défini en tant que rapport de la capacité.

Cela suggérerait que si 100 éléments étaient ajoutés au dictionnaire ci-dessus, il se redimensionnerait lui-même lorsque l'un des éléments serait ajouté. Le redimensionnement d’un dictionnaire est quelque chose que j’aimerais éviter car il a un impact négatif sur les performances et gaspille de la mémoire.

La probabilité de hachage des collisions est proportionnelle au chargement dans un dictionnaire. Par conséquent, même si le dictionnaire ne se redimensionne pas (et utilise tous ses emplacements), les performances doivent se dégrader du fait de ces collisions.

Comment devrait-on décider au mieux de la capacité à initialiser le dictionnaire, en supposant que vous sachiez combien d'éléments seront dans le dictionnaire?

Answer 1

Ce à quoi vous devez initialiser la capacité du dictionnaire dépend de deux facteurs: (1) la distribution de la fonction gethashcode, et (2) Combien d'éléments devez-vous insérer?

Votre fonction de hachage doit être distribuée de manière aléatoire ou doit être spécialement formulée pour votre ensemble d'entrées. Supposons le premier, mais si le second vous intéresse, recherchez des fonctions de hachage parfaites.

Si vous avez 100 éléments à insérer dans le dictionnaire, une fonction de hachage distribuée de manière aléatoire et que vous définissez la capacité sur 100, la probabilité que vous insériez cet élément dans la table de hachage est de (i-1) / 100. que le ième élément entre en collision avec un autre article lors de son insertion. Si vous souhaitez réduire cette probabilité de collision, augmentez la capacité. Le fait de doubler la capacité attendue réduit de moitié le risque de collision.

De plus, si vous savez à quelle fréquence vous allez accéder à chaque élément du dictionnaire, vous pouvez insérer les éléments par ordre de fréquence décroissante, car les éléments que vous insérez en premier seront en moyenne plus rapides à accéder.

Answer 2

J'ai fait un test rapide, probablement pas scientifique, mais si je définissais la taille, il fallait 1,2207780 secondes pour ajouter un million d'éléments et 1,5024960 secondes pour l'ajouter si je ne donnais pas au dictionnaire une taille ... cela semble négligeable pour moi.

Voici mon code de test. Peut-être que quelqu'un peut faire un test plus rigoureux, mais je doute que cela compte.

static void Main(string[] args)
        {
            DateTime start1 = DateTime.Now;
            var dict1 = new Dictionary<string, string>(1000000);

            for (int i = 0; i < 1000000; i++)
                dict1.Add(i.ToString(), i.ToString());

            DateTime stop1 = DateTime.Now;

            DateTime start2 = DateTime.Now;
            var dict2 = new Dictionary<string, string>();

            for (int i = 0; i < 1000000; i++)
                dict2.Add(i.ToString(), i.ToString());

            DateTime stop2 = DateTime.Now;

            Console.WriteLine("Time with size initialized: " + (stop1.Subtract(start1)) + "\nTime without size initialized: " + (stop2.Subtract(start2)));
            Console.ReadLine();
        }

Answer 3

Je pense que vous compliquez exagérément les choses. Si vous savez combien d'éléments seront dans votre dictionnaire, alors précisez-le lors de la construction. Cela aidera le dictionnaire à allouer l’espace nécessaire dans ses structures de données internes afin d’éviter la réaffectation et le remaniement des données.

Answer 4

La spécification de la capacité initiale du constructeur Dictionary augmente les performances car le nombre de redimensionnements appliqués aux structures internes stockant les valeurs du dictionnaire lors des opérations ADD sera moins important.

Considérant que vous spécifiez une capacité initiale de k pour le constructeur Dictionnaire , puis:

1. Le dictionnaire réservera la quantité de mémoire nécessaire pour stocker k éléments;
2. Les performances de QUERY par rapport au dictionnaire ne sont pas affectées et ne seront pas plus rapides ni plus lentes;
3. Les opérations ADD ne nécessiteront pas davantage d’allocation de mémoire (peut-être coûteuse) et seront donc plus rapides.

De MSDN :

  

La capacité d'un dictionnaire (TKey,   TValue) est le nombre d'éléments que   peut être ajouté au dictionnaire (TKey,   TValue) avant de redimensionner est nécessaire.   Comme les éléments sont ajoutés à un   Dictionnaire (TKey, TValue), la capacité   est automatiquement augmenté selon les besoins   en réaffectant le tableau interne.

     

Si la taille de la collection peut être   estimé, en spécifiant la valeur initiale   capacité élimine le besoin de   effectuer un certain nombre de redimensionnement   opérations tout en ajoutant des éléments à   le dictionnaire (TKey, TValue).

Answer 5

Oui, contrairement à une HashTable qui utilise le rehashing comme méthode pour résoudre les collisions, le Dictionnaire utilise le chaînage. Alors oui, il est bon d'utiliser le décompte. Pour un HashTable , vous souhaiterez probablement utiliser count * (1 / fillfactor)

Answer 6

La taille initiale est juste une suggestion. Par exemple, la plupart des tables de hachage aiment avoir des tailles qui sont des nombres premiers ou une puissance de 2.