Limites de taille pratiques d'une table de hachage et d'un dictionnaire en c #

12

Quelles sont les limites pratiques du nombre d'éléments qu'un dictionnaire ou une table de hachage C # 4 peut contenir et le nombre total d'octets que ces structures peuvent raisonnablement contenir. Je vais travailler avec un grand nombre d'objets et je veux savoir quand ces structures commencent à rencontrer des problèmes.

Pour le contexte, je vais utiliser un système 64 bits avec des tonnes de mémoire. De plus, je devrai trouver des objets en utilisant un formulaire ou une «clé». Compte tenu des exigences de performances, ces objets devront résider en mémoire et nombre d'entre eux dureront longtemps.

N'hésitez pas à suggérer d'autres approches / modèles, bien que je doive éviter d'utiliser des bibliothèques tierces ou open source. Pour des raisons de spécification, j'ai besoin de pouvoir le construire en utilisant C # natif ( ou C ++ \ CLI ).

JoeGeeky
la source
1
Cela ne devrait prendre qu'une heure ou deux pour se moquer de cela et mesurer les performances d'ajout / suppression / recherche sous différentes utilisations / charges. Je crois que VS2010 fournit même un squelette de test de performance pour vous. Peu importe ce que quelqu'un dit ici, le code que vous écrirez aura votre nom dessus, directement ou dans des métadonnées.
Job

Réponses:

8

Une chose à souligner est que le dictionnaire ne va pas contenir l'objet lui-même (qui peut avoir une grande empreinte mémoire) mais seulement une référence à l'objet, donc si les objets sont complexes, cela n'a aucun impact sur la taille du dictionnaire.

J'ai rassemblé plusieurs milliers d'articles dans un dictionnaire en mémoire et le problème n'est pas la taille du dictionnaire mais la taille des objets eux-mêmes en mémoire. Dans ces cas, le dictionnaire lui-même n'était qu'une infime partie de la mémoire impliquée.

Dans les cas de dictionnaires volumineux, il faut penser à configurer et à gérer manuellement la capacité du dictionnaire. Dans des circonstances normales .Net gère cette amende (dans l'implémentation actuelle s'il manque d'espace, il se redimensionne en un nombre premier qui est au moins deux fois la taille actuelle du dictionnaire). Cependant, si vous savez que vous allez créer un grand dictionnaire ou que vous allez développer le dictionnaire au lieu de deviner .Net et redimensionner le dictionnaire pour vous (ce qui est relativement coûteux), il vaut probablement mieux que vous le fassiez vous-même (certainement avec le premier taille et probablement gérer plus tard redimensionne). Cela peut être fait en gérant la capacité du dictionnaire si vous avez une idée heuristique raisonnable de ce que devrait être la capacité du dictionnaire. Microsoft le recommande surMSDN dans leurs remarques sur l'objet Dictionary . Cependant, il semble y avoir un débat sur la valeur réelle de cette approche, même si je ne suis pas sûr de la rigueur de ce test et s'il existe d'autres optimisations que la plate-forme .Net met en place lorsqu'un dictionnaire se redimensionne extrêmement rapidement.

Il s'agit d'une question utile sur le débordement de pile concernant la taille de l'objet et de la mémoire.

AlexC
la source
2

Les limites pratiques peuvent être relatives à la machine sur laquelle votre logiciel s'exécute ainsi qu'au nombre d'objets que vous prévoyez de contenir dans ces structures de données. Comme Oded l'a mentionné, int.MaxValue est un grand nombre, mais 2 milliards d'articles correspondent-ils à une limite pratique? Stocker autant d'éléments en mémoire n'est probablement pas très pratique.

Bernard
la source
0

Étant donné que la documentation ne dit pas où les données sont physiquement stockées et ne spécifie pas la limite, je vous suggère d'effectuer une expérience avec la taille maximale attendue que vous êtes susceptible d'avoir et de noter la mémoire système avant et après l'allocation de stockage.

Aucune chance
la source
-1

J'ai récemment mis à jour le hash-table-shootout du projet github (ici: https://github.com/jimbelton/hash-table-shootout ). La carte gcc standard non ordonnée a environ 1,8 Go de surcharge pour stocker 40 millions d'objets. Cela me semble assez atroce, mais même le plus performant en termes de mémoire, le Google sparse_hash_map, prend 600 Mo, et vous payez une pénalité de performance pour l'utiliser. Si vous voulez de la vitesse, parmi les algorithmes inclus, le Glib GHashTable est le plus rapide et a de bonnes performances de mémoire (environ 1,3 Go de surcharge). Les résultats de référence sont affichés ici: https://jimbelton.wordpress.com/2015/07/01/hash-table-shootout-on-github/

Jim Belton
la source