Meilleure Collection Rapide de la Chaîne de Recherche

J'ai besoin d'une liste de chaînes de caractères et un moyen de déterminer rapidement si une chaîne est contenue dans cette liste.

Pour améliorer la recherche de vitesse, j'ai considéré SortedList et Dictionary; toutefois, les deux travailler avec KeyValuePairs quand tout ce que je besoin est un seul string.

Je sais que je pourrais utiliser un KeyValuePair et simplement ignorer les Value partie. Mais je préfère être efficace et me demande si il y a une collection mieux adapté à mes besoins.

InformationsquelleAutor Jonathan Wood | 2011-04-03
  1. 32

    Si vous êtes sur .NET 3.5 ou supérieur, utilisez HashSet<String>.

    À défaut, d'un Dictionary<string, byte> (ou quel que soit le type que vous souhaitez pour le TValue type de paramètre) serait plus rapide qu'un SortedList si vous avez beaucoup d'entrées - ce dernier utilise une recherche binaire, de sorte qu'il sera en O(log n) de recherche, au lieu de O(1).

    • Accord - telle est la vie. Dans .NET 4 il y a une interface pour représenter des ensembles (ISet<T>) et également une autre option dans SortedSet<T> (qui encore une fois ne pas être particulièrement utile dans ce cas).
    • Je viens de regarder en arrière à présent. Un O(1) recherche est rapide en effet. Cependant, je devine que cette collection qui met en œuvre une sorte de hachage. Afin de ne pas O(1) n'assument aucune collisions? (BTW, je suis en train de travailler mon chemin à travers votre livre.)
    • Il est O(1) si le hachage est raisonnable, donc il n'y a pas de aussi beaucoup de collisions.
    InformationsquelleAutor Jon Skeet
  2. 10

    Si vous voulez simplement savoir si une chaîne est dans l'ensemble l'utilisation HashSet<string>

    InformationsquelleAutor BrokenGlass
  3. 5

    Cela ressemble à un travail pour 

     var keys = new HashSet<string>();

    Par MSDN: La fonction contains a O(1) de la complexité.

    Mais vous devez être conscient que cela ne donne pas une erreur de doublons lors de l'ajout.

    • Pour être plus précis de la méthode Add ne jette pas une exception, mais elle ne retourne true si la clé a été ajoutée, et false si elle était déjà présente.
    InformationsquelleAutor Henk Holterman
  4. 3

    HashSet<string> est comme un Dictionary, mais avec uniquement des clés.

    InformationsquelleAutor Albin Sunnanbo
  5. 1

    Si vous avez envie de rouler votre propre structure de données, l'utilisation d'un Trie.
    http://en.wikipedia.org/wiki/Trie

    pire des cas est de savoir si la chaîne est présente: O(longueur de chaîne)

    InformationsquelleAutor James
  6. 1

    Je sais que cette réponse est un peu tard pour cette partie, mais j'ai été en cours d'exécution dans un problème où nos systèmes étaient en cours d'exécution lente. Après profilage, nous avons constaté qu'il y avait BEAUCOUP de chaîne de recherches qui se passe avec la façon dont nous avions nos structures de données structurées.

    Nous avons donc fait quelques recherches, est venu à travers ces points de référence, fait nos propres tests, et ont basculé à l'aide de SortedList maintenant. 

    if (sortedlist.ContainsKey(thekey))
{   
//found it.
}

    Même si un Dictionnaire est avéré être le plus rapide, a moins de code, nous avons eu à refactoriser, et l'augmentation de la performance est assez bonne pour nous.

    De toute façon, je voulais partager le site au cas où d'autres personnes sont en cours d'exécution dans des problèmes similaires. Ils font des comparaisons entre les structures de données où la chaîne que vous êtes à la recherche d'une "clé" (comme la table de hachage, Dictionnaire, etc) ou dans une "valeur" (Liste, Tableau, ou dans un Dictionnaire, etc) qui est l'endroit où les nôtres sont stockées.

    InformationsquelleAutor
  7. 1

    Je sais que la question est vieille comme l'enfer, mais j'ai juste eu à résoudre le même problème, seulement pour un très petit ensemble de cordes(entre 2 et 4).

    Dans mon cas, j'ai utilisé le manuel de recherche sur un tableau de chaînes qui s'est avéré pour être beaucoup plus rapide que HashSet<string>(je comparés il). 

    for (int i = 0; i < this.propertiesToIgnore.Length; i++)
{
    if (this.propertiesToIgnore[i].Equals(propertyName))
    {
        return true;
    }
}

    Remarque, que c'est mieux que de hachage fixés que pour les minuscules tableaux!

    EDIT: ne fonctionne qu'avec un manuel for boucle, ne pas utiliser LINQ, les détails dans les commentaires

    • Oui, HashSet<> a des frais généraux. Je ne le recommande lors de la recherche de grandes collections. BTW, votre code pourrait être réduit à quelque chose comme return PropertiesToIgnore.Any(p => p.Equals(propertyName))
    • Malheureusement, à l'aide de Linq ralentit l'exécution d'un facteur de 10! Les résultats d'un Benchmark ArrayManualLoop: 6.018 ns ArrayLinq: 59.171 ns. Linq épines, le cache du processeur en dehors, et tous les gains possibles sont perdus.
    InformationsquelleAutor Artur Krajewski