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 KeyValuePair
s 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.
Vous devez vous connecter pour publier un commentaire.
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 leTValue
type de paramètre) serait plus rapide qu'unSortedList
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).ISet<T>
) et également une autre option dansSortedSet<T>
(qui encore une fois ne pas être particulièrement utile dans ce cas).Si vous voulez simplement savoir si une chaîne est dans l'ensemble l'utilisation
HashSet<string>
Cela ressemble à un travail pour
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.
HashSet<string>
est comme unDictionary
, mais avec uniquement des clés.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)
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.
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.
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).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 commentairesHashSet<>
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 commereturn PropertiesToIgnore.Any(p => p.Equals(propertyName))
ArrayManualLoop: 6.018 ns
ArrayLinq: 59.171 ns
. Linq épines, le cache du processeur en dehors, et tous les gains possibles sont perdus.