Est-HashSet le conteneur le plus rapide pour consulter?

Question

Je dois vérifier cette chaîne spécifique contient dans l'ensemble des autres:

private bool Contains(string field)
{
   return this.Fields.Contains(field); // HashSet<string> local property
}

Quel est le meilleur type de conteneur à utiliser si une seule tâche de celui-ci - de tenir un certain nombre de chaînes et contrôle ne autre est dans ou ne pas

Answer 1

Oui, HashSet est parfait pour cela, car il contient une valeur pour rechercher la différence d'un dictionnaire qui nécessite une clé et une valeur.

Answer 2

Est-ce que HashSet fonctionne? Sûr. Mais ce n'est pas la question que vous avez posée. Vous avez demandé la la plus rapide possible recherche.

est-il le plus rapide possible? Non, bien sûr que non, et non par aucune mesure.

Tout d'abord, afin de parler de « plus rapide » nous avons besoin de décrire précisément ce que « le plus rapide » signifie. Voulez-vous dire:

• plus petit pire des cas calendrier
• plus petit moyenne timing moyennées sur plusieurs synchronisations
• de durée moyenne plus petit donné un modèle d'utilisation particulière
• quelque chose d'autre

? S'il vous plaît préciser exactement ce que signifie « le plus rapide possible ». Nous pouvons vous mettre au point un algorithme qui est le dans la théorie la plus rapide possible uniquement si nous savons exactement ce que la plus rapide possible signifie pour vous.

Par exemple, supposons que vous écrivez un compilateur. Quelque chose que nous devons faire tout le temps dans les compilateurs est de vérifier si une chaîne particulière est dans une liste de chaînes. Peut-être que nous vérifions pour voir si une chaîne est un mot-clé, nous devons donc rechercher si une chaîne donnée est à l'intérieur de l'ensemble { « int », « double », « pour », « foreach », « classe » ... }

Nous pourrions mettre les dans un jeu de hachage et d'obtenir des performances décentes. Mais si nous voulions que le meilleures performances possibles nous pourrions faire beaucoup mieux. Nous pourrions, par exemple, faire une analyse de quelques milliards de lignes de code source existant pour savoir quels mots-clés étaient les plus courants et qui étaient les moins communs, puis écrire une table de hachage personnalisé optimisé pour (1) rejeter rapidement les choses qui étaient pas les mots clés du tout, et (2) la reconnaissance rapide des mots-clés les plus courants au détriment de la reconnaissance d'autres mots-clés.

Notez que cela nécessite une analyse statique; mais il fonctionne bien sur des cas typiques, il fonctionne mal sur les rares cas où il y a beaucoup de mots-clés utilisés rares. Une autre approche que nous pourrions prendre serait d'écrire un réglage automatique table de hachage que dynamiquement identifié lorsque les chaînes particulières étaient recherchées fréquemment.

Prenons, par exemple, si vous écrivez une implémentation de l'exécution JScript. Il faut souvent chercher une chaîne dans un ensemble de chaînes:

for(i = 0; i < 10; ++i) { foo.bar(i); }

Ici, nous devons regarder la chaîne « bar » dans l'objet identifié par « foo » dix fois. La table de hachage à l'intérieur de « toto » qui implémente cette recherche remarque la première fois à travers la boucle que « bar » a été utilisé, de sorte qu'il tord dynamiquement la structure de la table de hachage de telle sorte que la secondes passage dans la boucle, la recherche est plus rapide. Telle est la stratégie que nous employions dans notre mise en œuvre de JScript.

, qui optimise le cas pour les boucles, mais il fait ce cas potentiellement plus lent que ce pourrait être:

for(i = 0; i < 10; ++i) { foo.bar(i); foo.blah(i); foo.abc(i); }

parce que nous ne faisons pas une analyse plus approfondie et de réaliser « hey, nous venons réoptimisés cette table de hachage trois fois, et maintenant nous allons tout faire à nouveau, peut-être que nous devrions simplement le laisser tel qu'il est. »

Heureusement pour nous, nous n'étions pas, comme vous, la recherche de la la plus rapide possible recherche. Nous étions à la recherche que pour un raisonnablement rapide recherche.

Pouvez-vous décrire soigneusement et complètement exactement ce que votre cas est l'utilisation pour la recherche le plus rapide possible ? Il y a beaucoup d'algorithmes que vous pouvez utiliser pour accélérer les recherches, mais ils deviennent très compliquées.