.NET: Comment vérifier efficacement pour l'unicité dans une liste de 50.000 articles?

Question

Dans un code de bibliothèque, j'ai une liste qui peut contenir 50.000 articles ou plus.

Les appelants de la bibliothèque peuvent appeler des méthodes qui se traduisent par des chaînes ajoutées à la liste. Comment puis-je vérifier efficacement pour l'unicité des cordes étant ajoutée?

À l'heure actuelle, juste avant d'ajouter une chaîne, je scrute la liste complète et comparer chaque chaîne à la chaîne à être ajoutée. Cela commence à montrer des problèmes d'échelle au-dessus de 10.000 points.

Je vais référence, mais intéressé par un aperçu.

• si je remplace la liste <> avec un dictionnaire <>, sera ContainsKey () est sensiblement plus rapide que la liste augmente à 10.000 points et au-delà?
• si je remettrai le contrôle unique qu'après tous les éléments ont été ajoutés, ce sera plus rapide? À ce moment-là je besoin de vérifier tous les éléments contre tout autre élément, encore un n ^^ 2 opération.

---

EDIT

Quelques résultats de référence de base. J'ai créé une classe abstraite qui expose 2 méthodes: Fill and Scan. Remplissez remplit la collection avec des éléments n (je 50 000). Balaie les temps de liste m (je 5000) pour voir si une valeur donnée est présente. Ensuite, je construit une implémentation de cette classe pour la liste, et un autre pour HashSet.

Les cordes utilisées étaient uniformément 11 caractères de longueur, et générés au hasard par l'intermédiaire d'une méthode dans la classe abstraite.

Un micro-repère très basique.

Hello from Cheeso.Tests.ListTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.4428266
Time to scan: 00:00:13.0291180

Hello from Cheeso.Tests.HashSetTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.3797751
Time to scan: 00:00:00.4364431

Alors, pour les chaînes de cette longueur, HashSet est à peu près 25x plus rapide que la liste, lors de la numérisation pour l'unicité. En outre, pour cette taille de collection, HashSet a peine zéro sur la liste lors de l'ajout d'éléments à la collection.

Les résultats sont intéressants et non valides. Pour obtenir des résultats valables, je dois faire des intervalles de warm-up, de multiples essais, avec une sélection aléatoire de la mise en œuvre. Mais je suis convaincu que cela déplacer la barre légèrement.

Merci à tous.

EDIT2

Après avoir ajouté randomisation et multple essais, HashSet surclasse toujours la liste dans ce cas, d'environ 20x.

Ces résultats ne tiennent pas nécessairement pour les chaînes de longueur variable, des objets plus complexes, ou différentes tailles de collection.

Answer 1

Vous devez utiliser le HashSet<T> classe, qui est spécialement conçu pour ce que vous faites.

Answer 2

Utilisation HashSet<string> au lieu de List<string>, alors il devrait évoluer très bien.

Answer 3

De mes tests, HashSet<string> prend pas de temps par rapport à List<string>:)

Answer 4

Peut-être hors-sujet, mais si vous voulez très grande échelle des ensembles uniques de cordes (en millions) + d'une manière indépendante de la langue, vous pouvez vérifier sur Bloom filtres .

Answer 5

La fonction Contains(T) fonctionne pas pour vous?

Answer 6

J'ai lu que le dictionnaire <> est implémenté comme un tableau associatif. Dans certaines langues (pas nécessairement tout ce qui concerne .NET), les index de chaîne sont stockés sous forme d'une structure arborescente qui bifurque à chaque nœud en fonction du caractère dans le nœud. S'il vous plaît voir http://en.wikipedia.org/wiki/Associative_arrays .

Une structure de données similaire a été conçu par Aho et Corasick en 1973 (je crois). Si vous stockez 50.000 chaînes dans une telle structure, il importe combien de chaînes que vous stockez. Il importe plus la longueur des cordes. Si elles sont sont à peu près la même longueur, alors vous verrez probablement jamais un ralentissement parce que l'algorithme lookups de recherche est linéaire dans l'exécution par rapport à la longueur de la chaîne que vous recherchez. Même pour un arbre rouge-noir ou arbre AVL, l'exécution de la recherche dépend plus de la longueur de la chaîne que vous recherchez plutôt que le nombre d'éléments de l'indice. Toutefois, si vous choisissez de mettre en œuvre vos clés d'index avec une fonction de hachage, vous incurr maintenant le coût de hachage de la chaîne (va être O (m), m = longueur de la chaîne), ainsi que la recherche de la chaîne dans l'index, qui sera probablement de l'ordre de O (log (n)), n = nombre d'éléments dans l'index.

edit: Je ne suis pas un gourou .NET. D'autres personnes plus expérimentés suggèrent une autre structure. Je prendrais leur parole sur le mien.

Edit2: votre analyse est un peu pour les comparaisons avec l'unicité. Si vous utilisez une structure de hachage ou le dictionnaire, il ne sera pas une opération O (n ^ 2) à cause du raisonnement que j'ai posté ci-dessus. Si vous continuez à utiliser une liste, alors vous avez raison qu'il est O (n ^ 2) * (longueur max d'une chaîne dans votre jeu) parce que vous devez examiner chaque élément dans la liste à chaque fois.