Quelle collection .NET fournit la recherche la plus rapide

J'ai 60k éléments qui doivent être comparés à une liste de recherche de 20k. Existe-t-il un objet de collection (comme List, HashTable) qui fournit une Contains()méthode exceptionnellement rapide ? Ou vais-je devoir écrire le mien? En d'autres termes, la Contains()méthode par défaut analyse-t-elle simplement chaque élément ou utilise-t-elle un meilleur algorithme de recherche.

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

Remarque . La liste de recherche est déjà triée.

Dans le cas le plus général, considérez System.Collections.Generic.HashSetcomme votre structure de données «Contient» par défaut, car son évaluation prend un temps constant Contains.

La réponse réelle à "Quelle est la collection de recherche la plus rapide" dépend de la taille de vos données, de l'ordre, du coût de hachage et de la fréquence de recherche.

Si vous n'avez pas besoin de commander, essayez HashSet<Record>(nouveau sur .Net 3.5)

Si vous le faites, utilisez un List<Record>et appelez BinarySearch.

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

Vous avez dit que votre grande collection est déjà triée, donc cela semble être l'occasion idéale? Un hachage serait certainement le plus rapide, mais cela pose ses propres problèmes et nécessite beaucoup plus de frais généraux pour le stockage.

Vous devriez lire ce blog qui a testé plusieurs types de collections et de méthodes pour chacune en utilisant à la fois des techniques simples et multi-threadées.

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

Lors de l'utilisation d'une collection qui autorise l'utilisation de «clés», le Dictionary, ConcurrentDictionary, Hashset et HashTables ont globalement obtenu les meilleurs résultats.

Gardez les deux listes x et y dans l'ordre trié.

Si x = y, faites votre action, si x <y, avancez x, si y <x, avancez y jusqu'à ce que l'une ou l'autre des listes soit vide.

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

Ne lancez pas une boucle .Contains (), c'est proportionnel à x * y, ce qui est bien pire.

S'il est possible de trier vos éléments, il existe un moyen beaucoup plus rapide de le faire, puis d'effectuer des recherches clés dans une table de hachage ou un b-tree. Cependant, si vos éléments ne sont pas triables, vous ne pouvez pas vraiment les mettre dans un arbre b de toute façon.

Quoi qu'il en soit, s'il est possible de trier 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 utilisez .Net 3.5, vous pouvez créer du 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 donc pas été testé. Il repose sur une méthode d'extension. Non, ce LookupCollection.Intersect(LargeCollection)n'est probablement pas la même chose que LargeCollection.Intersect(LookupCollection)... ce dernier est probablement beaucoup plus lent.

Cela suppose que LookupCollection est un HashSet

Si vous ne craignez pas de grincer chaque dernière partie de la performance, la suggestion d'utiliser un HashSet ou une recherche binaire est solide. Vos ensembles de données ne sont tout simplement pas assez grands pour que cela pose un problème 99% du temps.

Mais si vous ne le faites qu'une fois parmi des milliers de fois et que les performances sont essentielles (et s'avèrent inacceptables en utilisant HashSet / recherche binaire), vous pouvez certainement écrire votre propre algorithme qui parcourrait les listes triées en faisant des comparaisons au fur et à mesure. Chaque liste serait parcourue au plus une fois et dans les cas pathologiques, ce ne serait pas mal (une fois que vous avez emprunté cette voie, vous trouverez probablement que la comparaison, en supposant qu'il s'agit d'une chaîne ou d'une autre valeur non intégrale, serait la dépense réelle et cette optimisation serait la prochaine étape).