Est-il limité à des entrées dans un Dictionnaire<>?

J'ai environ 3000 fichiers différents, j'ai besoin d'organiser, et de récupérer à différents moments au cours du jeu.

J'ai créé ma propre structure de variables.
Je pensais à la création d'un "Dictionnaire"
au début de mon application, et tout simplement le chargement de tous mes fichiers avant que le jeu commence.

Je me demandais à propos de la performance: un dictionnaire avec ce nombre d'entrées en cause ma demande à être lent?
Un grand dictionnaire de rendre "TryGetValue" et "ContainsKey" exécuter plus lentement?

merci pour les conseils!

Essayer, de les mesurer, et de voir!

OriginalL'auteur theoneawaited | 2010-08-11

  1. 14

    TryGetValue et ContainsKey devrait être assez rapide à cette taille, aussi longtemps que la clé a bien distribué les tables de hachage.

    Un Dictionnaire est un indexables nombre de "compartiments". Lorsqu'il ajoute ou se pour une valeur d'une clé, il prendra la valeur retournée par GetHashCode(), hachage de nouveau à moins que le nombre de compartiments (généralement quelque chose de simple comme modulo, mais la mise en œuvre n'est pas défini), et de regarder dans le seau.

    Le seau actuellement avoir zéro, un ou plusieurs éléments. Le dictionnaire de comparer chaque élément avec la clé à l'aide .Equals().

    Le premier bit de trouver le bon seau va être en temps constant O(1). Le deuxième bit de comparaison de la touche avec les touches dans le seau va être dans lineary temps O(n) où n ne concerne que le nombre d'éléments dans ce seau, pas dans l'ensemble de la collection.

    Généralement il devrait y avoir très peu d'éléments dans chaque seau (le nombre de compartiments va croître à essayer de garder ce le cas) de sorte que le fonctionnement est essentiellement constante de temps.

    Toutefois, si vos codes de hachage sont mal mises en œuvre, il y aura beaucoup de touches dans le même seau. La complexité du temps va se rapprocher et plus proche de O(n), comme on peut le voir par l'expérimentation avec un objet avec un délibérément mauvais GetHashCode qui ne renvoie 0 à chaque fois. Dans le pire des cas c'est pire qu'une Liste, comme une Liste est également en O(n), mais le Dictionnaire a plus de surcharge.

    Tout ce que cela signifie, vous devriez vous inquiéter? Non, même relativement naïf de hachage méthodes devraient donner des résultats relativement bons. Si vous utilisez une chaîne de clé, alors il est probablement déjà plus que suffisant. Si vous êtes en utilisant un simple type intégré, puis encore plus.

    Si vous trouvez que l'accès au dictionnaire est lent si, ensuite, vous voulez faire attention à ce et corriger la GetHashCode() la méthode ou de créer un IEqualityComparer (qui permet de définir des règles extérieures pour GetHashCode() et Equals() pour utiliser avec les dictionnaires, hashsets, etc).

    Plus probablement cependant, 3000 n'est rien, ça va être bien.

    OriginalL'auteur Jon Hanna

  2. 12

    3000 entrées est minable pour un Dictionary<>. Qui ne sera pas une source de ralentissement.

    La lecture de 3000 fichiers différents en mémoire au démarrage, sur l'autre main, sera être lent. Vous serez bien mieux de lire des fichiers stockés dans la mémoire qu'au moment où ils sont nécessaires, mais en gardant en mémoire par la suite, pour les demandes d'accès.

    Depuis qu'il parle d'un jeu, cette règle peut ne pas s'appliquer. Selon à quel point ils avaient la charge et la façon dont ils sont gros, il peut être préférable de les charger derrière le démarrage de l'écran de démarrage plutôt que Ashe est d'essayer de frapper une Deadite...
    bon point.
    Sans doute, ils pourraient lancer un thread d'arrière-plan au démarrage qui effectue le processus.

    OriginalL'auteur JSBձոգչ

  3. 7

    Pas il ne sera pas. Il va consommer de la mémoire, mais TryGetValue et ContainKey devrait être assez rapide qu'un dictionnaire est une table de hachage et de l'accès aux éléments par la clé est constant et il ne dépend pas du nombre d'éléments.

    +1 - Bonne réponse

    OriginalL'auteur Darin Dimitrov

  4. 4

    Fournir le hashcode de l'algorithme de la clé de dictionnaire type des écarts de la hashcodes relativement uniformément dans l'ensemble de la Int32 de l'espace, hashcode de recherche n'est pas affectée par la taille du dictionnaire.

    Voir http://en.wikipedia.org/wiki/Hashtable#Performance_analysis pour plus de détails.

    +1 pour préciser que cela ne fonctionne que si le hash n'est pas cassé.

    OriginalL'auteur Paul Ruane

  5. 3

    Il y a une limite, mais 3000 est nulle part près d'elle. Dictionary<> utilise Object.GetHashCode() à oraginise ses clés, qui retourne un int. Par conséquent, vous pouvez stocker un maximum de 2^32 (4,294,967,296) touches avant il y a une collision. Toutefois, en raison de la manière .Net des codes de hachage sont généralement calculées, il y aura probablement beaucoup de collisions comme vous vous approchez de ce nombre magique.

    Ajouter de nouvelles clés ne sera pas ralentir TryGetValue et ContainsKey - ils sont O(1) opérations.

    Vos deux dernières phrases du conflit. Si deux clés entrent en collision, la recherche de l'un prendra plus de temps que d'une clé unique avec un code de hachage.
    Rien à voir avec la manière .NET des codes de hachage sont généralement calculées, et tout à voir avec les mathématiques de base. 1er, si vous avez plus de 2^32 valeurs possibles (vrai pour la plupart des types), alors il est impossible de garantir l'unicité, sauf si vous savez les valeurs à l'avance et peut créer un parfait condensé. Aussi, le dictionnaire ne pas commencer par prendre jusqu'à 16 go de la valeur de pointeur de l'espace de sorte qu'il est possible d'avoir 2^32 slots (peut être plus si ce n'est pas ref types stockés), mais il sera de réduire, donc plus de collisions. En dépit de ce que, bien étaler bits, les collisions seront généralement rares. Un peu de collisions wont' fait beaucoup de mal.

    OriginalL'auteur Callum Rogers

  6. 1

    Des dictionnaires .NET utiliser une table de hachage de recherche de régime, de sorte que l'ajout d'entrées a très peu, voire aucun effet sur les performances de recherche. Le seul problème que vous aurez peut-être l'utilisation de la mémoire. Un dictionnaire de 3000 articles consommera environ 3000 fois l'espace de stockage utilisé par la clé et de la valeur des types. Si c'est juste une simple struct sans d'énormes blobs binaires, 3000, c'est carrément minuscule.

    OriginalL'auteur recursive

  7. 1

    Votre goulot d'étranglement ne sera pas le dictionnaire de la performance, mais plutôt la lecture de 3000 fichiers.

    OriginalL'auteur AndrewC

  8. 1

    Comme avec la plupart des choses avec un ordinateur (et de la performance), "Ça Dépend (tm)"

    Tout dépend de la mise en place de Dictionnaire.

    Il pourrait être fait dans un arbre binaire, dans lequel cas le look devrait être O(log2 N), ce qui signifie recherche de temps de pousse lentement à mesure que la taille du dictionnaire grandit.

    Il pourrait être fait, comme une table de hachage, ce qui, en théorie, est O(1), ce qui signifie qu'une recherche de toujours prendre la même quantité de temps, indépendamment de la taille du dictionnaire, mais c'est la théorie, et dépendent du nombre de seaux et de la qualité du code de hachage. Beaucoup de fin de l'élément dans le même seau, nécessitant un linéaire de recherche, chose va ralentir considérablement, alors que le dictionnaire se développe.

    Cependant, le dictionnaire aurait à croître au-delà de 3000 par plusieurs ordre de grandeur avant de voir une différence notable.

    Dictionnaire<> est spécifié que l'utilisation d'une table de hachage.

    OriginalL'auteur James Curran