Quelle collection .NET fournit la recherche la plus rapide

Question

J'ai 60 000 articles qui doivent être comparés à une liste de consultation de 20 000 articles. Existe-t-il un objet de collection (comme List , HashTable ) qui fournit un système exceptionnellement rapide Contains() méthode ? Ou dois-je écrire la mienne ? En d'autres termes, est-ce que la méthode par défaut Contains() se contente de scanner chaque élément ou utilise-t-elle un meilleur algorithme de recherche ?

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

Note . La liste de consultation est déjà triée.

Answer 1

System.Collections.Generic.HashSet

Answer 2

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

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

Answer 3

Avez-vous envisagé List.BinarySearch(item) ?

Vous avez dit que votre grande collection est déjà triée, donc cela semble être l'opportunité parfaite ? Un hachage serait sans aucun doute le plus rapide, mais cela pose ses propres problèmes et nécessite beaucoup plus d'espace de stockage.

Answer 4

Conservez les deux listes x et y dans un 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 liste soit vide.

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

Ne fais pas ça. exécuter une boucle .Contains (), cela est proportionnel à x * y ce qui est bien pire.

Answer 5

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

De toute façon, si sortable trie 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