.NET: Comment vérifier efficacement le caractère unique dans une liste <string> de 50 000 articles?

Question

Dans un code de bibliothèque, j'ai une Liste qui peut contenir 50 000 objets ou plus.

Les appelants de la bibliothèque peut invoquer les méthodes qui donnent des chaînes ajoutées à la liste. Comment puis-je vérifier efficacement l'unicité des chaînes de caractères ajoutés?

Actuellement, juste avant d'ajouter une chaîne de caractères, je scanne l'intégralité de la liste et de comparer chaque chaîne à l'ajout de la chaîne. Cela commence à montrer des problèmes d'échelle au-dessus de 10 000 éléments.

Je vais indice de référence de l', mais qui sont intéressés par la compréhension.

• si je remplace la Liste des<>, avec un Dictionnaire<> , seront ContainsKey() être sensiblement plus rapide que la liste s'accroît de 10 000 et au-delà?
• si je reporte le contrôle d'unicité jusqu'à ce que tous les éléments ont été ajoutés, ce sera plus rapide? À ce point, j'aurais besoin de vérifier chaque élément à l'encontre de tous les autres éléments, encore un n^^2 opération.

---

MODIFIER

Certains de base résultats de référence. J'ai créé une classe abstraite qui expose 2 méthodes: Remplissage et d'Analyse. Remplissez seulement remplit la collection avec n éléments (j'ai utilisé de 50 000). Analyse de la liste de m fois (j'ai utilisé 5000) pour voir si une valeur est présente. Ensuite, j'ai fabriqué une mise en œuvre de cette classe pour la Liste, et un autre pour HashSet.

Les cordes utilisées étaient uniformément 11 caractères, et généré de façon aléatoire par l'intermédiaire d'une méthode dans la classe abstraite.

Un très de base micro-benchmark.

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

Donc, pour les chaînes de longueur, HashSet est d'environ 25 x plus rapide que la Liste , lors de la numérisation pour l'unicité. Aussi, pour cette taille de la collection, HashSet a aucune pénalité sur la Liste lors de l'ajout d'éléments à la collection.

Les résultats sont intéressants et pas valide. Pour obtenir des résultats valides, j'avais besoin de faire de chauffe intervalles, de multiples essais, avec une sélection aléatoire de la mise en œuvre. Mais j'ai confiance, qui permettrait de déplacer la barre légèrement.

Merci à tous.

EDIT2

Après l'ajout de la randomisation et de multiples essais, HashSet constamment surpasse la Liste dans ce cas, d'environ 20x.

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

Answer 1

Vous devez utiliser la classe HashSet<T> , spécialement conçue pour ce que vous faites.

Answer 2

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

Answer 3

De mes tests, HashSet<string> ne prend pas de temps comparé à List<string> :)

Answer 4

Peut-être hors sujet, mais si vous souhaitez mettre à l'échelle de très grands ensembles uniques de chaînes (plusieurs millions) de manière indépendante de la langue, vous pouvez essayer les filtres Bloom .

Answer 5

J'ai lu que le dictionnaire<> est implémenté sous la forme d'un tableau associatif. Dans certaines langues (pas forcément tout ce qui est lié .NET), index de chaînes de caractères sont stockées sous forme d'un arbre qui se dédouble à chaque nœud, basée sur le personnage dans le nœud. Veuillez voir http://en.wikipedia.org/wiki/Associative%5Farrays.

Une semblable structure de données a été conçu par Aho et Corasick en 1973 (je pense). Si vous stockez de 50.000 chaînes de caractères dans une telle structure, alors il n'importe pas combien de chaînes que vous stockez. Il est plus important que la longueur des chaînes de caractères. Si ils sont sur la même longueur, alors vous aurez probablement jamais voir un ralentissement dans les recherches, car l'algorithme de recherche est linéaire dans le temps d'exécution à l'égard de la longueur de la chaîne que vous recherchez. Même pour un rouge-noir tree ou arbre AVL, la recherche d'exécution dépend davantage de la longueur de la chaîne que vous recherchez plutôt que le nombre d'éléments dans l'index. Toutefois, si vous choisissez de mettre en œuvre vos clés d'index avec une fonction de hachage, vous avez maintenant incurr le coût de hachage de la chaîne (aller à O(m), m = longueur de la chaîne) et également la consultation de la chaîne dans l'index, ce qui sera probablement sur l'ordre de O(log(n)), n = nombre d'éléments dans l'index.

edit: je ne suis pas un .NET le gourou. D'autres personnes plus expérimentées suggérer une autre structure. Je voudrais prendre leur parole sur les miennes.

edit2: votre analyse est un peu à côté pour comparer l'unicité. Si vous utilisez un hachage de la structure ou de dictionnaire, alors il ne sera pas un O(n^2), parce que le raisonnement que j'ai posté ci-dessus. Si vous continuez à utiliser une liste, alors vous êtes juste qu'il est O(n^2) * (longueur maximale d'une chaîne de caractères dans votre jeu) parce que vous devez examiner chaque élément de la liste à chaque fois.