Quelle collection .NET fournit la recherche la plus rapide

J’ai 60k éléments à vérifier par rapport à une liste de recherche de 20k. Existe-t-il un object de collection (comme List , HashTable ) qui fournit une méthode Contains() exceptionnellement rapide? Ou devrais-je écrire le mien? En d’autres termes, la méthode Contains() par défaut consiste-t-elle à parsingr chaque élément ou utilise-t-il un meilleur algorithme de recherche.

 foreach (Record item in LargeCollection) { if (LookupCollection.Contains(item.Key)) { // Do something } } 

Note La liste de recherche est déjà sortingée.

Dans le cas le plus général, considérez System.Collections.Generic.HashSet comme votre structure de données par défaut “Contient”, car il faut un temps constant pour évaluer Contains .

La réponse à la question “Qu’est-ce que la collection consultable la plus rapide” dépend de la taille de vos données, de votre ordre de sorting, de votre coût de hachage et de votre fréquence de recherche.

Si vous n’avez pas besoin de commander, essayez HashSet (nouveau dans .Net 3.5)

Si vous le faites, utilisez une List et appelez BinarySearch .

Avez-vous considéré List.BinarySearch(item) ?

Vous avez dit que votre grande collection est déjà sortingée, cela semble être une opportunité parfaite? Un hachage serait certainement le plus rapide, mais cela entraîne ses propres problèmes et nécessite beaucoup plus de temps de stockage.

Vous devriez lire ce blog pour tester rapidement différents types de collections et de méthodes, chacun utilisant des techniques à un ou plusieurs threads.

Selon les résultats, un BinarySearch sur une liste et SortedList étaient les plus performants constamment au coude à coude lorsqu’ils recherchaient quelque chose comme une “valeur”.

Lorsque vous utilisez une collection qui autorise les “clés”, le dictionnaire, ConcurrentDictionary, Hashset et HashTables ont obtenu les meilleurs résultats.

Gardez les deux listes x et y dans l’ordre sortingé.

Si x = y, faites votre action, si x

Le temps d’exécution de cette intersection est proportionnel à min (taille (x), taille (y))

Ne lancez pas de boucle .Contains () proportionnelle à x * y, ce qui est bien pire.

S’il est possible de sortinger vos éléments, il existe un moyen beaucoup plus rapide de le faire, puis de rechercher des clés dans une table de hachage ou une arborescence. Cependant, si vous ne pouvez pas sortinger les objects, vous ne pouvez pas vraiment les placer dans un arbre.

Quoi qu’il en soit, s’il est possible de sortinger les deux listes, il suffit de parcourir la liste de recherche dans l’ordre.

 Walk lookup list While items in check list <= lookup list item if check list item = lookup list item do something Move to next lookup list item 

Si vous ne vous souciez pas de crier toutes les dernières performances, la suggestion d’utiliser une recherche HashSet ou binary est solide. Vos ensembles de données ne sont pas assez grands pour que cela pose problème 99% du temps.

Mais si vous ne le faites que des milliers de fois et que les performances sont critiques (et se sont avérées inacceptables avec HashSet / recherche binary), vous pourriez certainement écrire votre propre algorithme pour faire les comparaisons. Chaque liste serait parcourue au maximum une fois et dans les cas pathologiques ne serait pas mauvais (une fois que vous êtes allé dans cette voie, vous trouverez probablement que la comparaison, en supposant que c’est une chaîne ou une autre valeur non intégrale, serait la dépense réelle et cette optimisation serait la prochaine étape).

Si vous utilisez .Net 3.5, vous pouvez créer un code plus propre en utilisant:

 foreach (Record item in LookupCollection.Intersect(LargeCollection)) { //dostuff } 

Je n’ai pas .Net 3.5 ici et cela n’a pas été testé. Il s’appuie sur une méthode d’extension. Ce n’est pas que LookupCollection.Intersect(LargeCollection) n’est probablement pas la même que LargeCollection.Intersect(LookupCollection) … cette dernière est probablement beaucoup plus lente.

Cela suppose que LookupCollection est un HashSet