Des moyens rapides pour éviter les doublons dans une Liste<> en C#
Mon programme C# génère des chaînes aléatoires à partir d'un modèle donné. Ces chaînes de caractères sont stockées dans une liste. Comme pas de doublons sont autorisés que je suis en train de faire comme ceci:
List<string> myList = new List<string>();
for (int i = 0; i < total; i++) {
string random_string = GetRandomString(pattern);
if (!myList.Contains(random_string)) myList.Add(random_string);
}
Comme vous pouvez l'imaginer cela fonctionne très bien pour plusieurs centaines d'entrées. Mais je suis face à la situation de générer plusieurs millions de chaînes. Et à chaque ajout de la chaîne de contrôle de doublon devient plus lent et plus lent.
Y a des manières plus rapides pour éviter les doublons?
- l'utilisation de set pour éviter les doublons
- serait-il plus rapide aussi ajoutez-les tous, puis utiliser Distinct() pour vérifier les doublons, puis ajouter le nombre qui ont été supprimés?
- Cela sonne comme quelque chose de valeur de test pour un jeu de données particulier. Si elle ne s'avèrent être plus rapide, puis un poids serait que l'optimisation de la performance à l'encontre de l'obscurcissement il ajoute au code (qui n'est pas dans ce cas).
- Simplement par curiosité, quels sont exactement vous à l'aide de ces pour?
- J'avais sans doute l'argument théorique qui
HashSet<T>
serait plus rapide car moins de mémoire impact au départ et ne pas avoir à la parcourir entièrement par la suite. Le coût de la vérification de chaque élément existe toujours, mais que la structure de données est optimisé pour cela. - J'ai besoin de ces pour générer des numéros de série pour les documents.
- Pourriez-vous utiliser un
GUID
pour chaque document? - Si vous êtes à la persistance de votre liste à une base de données, vous pouvez également essayer de rendre le champ unique et puis si l'INSERTION échoue, vous pouvez essayer un autre - juste autre chose à considérer
- Non, malheureusement. Le modèle est une sorte de spécial afin de Guid ne va pas aider.
- Faire toute une DB aller-retour juste pour découvrir que la chaîne existe déjà, ce serait... un problème.
- Dépend de la façon dont il est susceptible de conflit. Si le programme est d'avoir à charger la Liste à partir de la DB, en premier lieu, il pourrait être un compromis acceptable.
- Ce qui fait que même un seul DB requête pour déterminer si un élément existe déjà dans la base de données prendra plus de temps que des centaines de milliers, voire des millions de vérifications pour voir si un élément existe dans un hashset dans la mémoire. À l'aide d'un DB pour résoudre ce problème pourrait être facilement plusieurs milliers de fois ralentissement.
- Juste assez, vous êtes probablement correct, il semble logique de toute façon
InformationsquelleAutor Robert Strauch | 2013-06-24
Vous devez vous connecter pour publier un commentaire.
Utiliser une structure de données qui peut de manière beaucoup plus efficace de déterminer si un élément existe, à savoir un
HashSet
. Il peut déterminer si un élément est dans l'ensemble en temps constant, quel que soit le nombre d'éléments dans le jeu.Si vous vraiment besoin les éléments dans un
List
au lieu de cela, ou vous avez besoin d'éléments dans la liste dans l'ordre où ils ont été générés, puis vous pouvez enregistrer les données dans une liste et d'un hashset; ajouter l'élément à la fois des collections, si il n'existe pas encore dans leHashSet
.HashSet
et l'augmentation de vitesse est énorme. Cependant, j'ai un nouveau problème. J'ai besoin d'une certaine quantité d'entrées dans la table de hachage ensemble. Si je utiliser pour pour-boucle dans ma question, puis il s'arrête au bout de 2 000 000 de cycles. Les doublons n'existent pas dans la table de hachage ensemble, mais si un double est frappé de la de hachage qui n'en possède pas 2 000 000 d'entrées. Comment ai-je pu l'éviter?if (myList.Count < 2000000) myList.Add(random_string);
empêche cela, mais est, de nouveau, sorte de lente.for(int i = 0; i < numItems; i++)
suffit d'utiliserfor(int i = 0; set.Count < numItems; i++)
. Ou, si vous n'avez pas besoin dei
à tous, puis il suffit dewhile(set.Count < numItems)
.Ne pas utiliser
List<>
. UtilisationDictionary<>
ouHashSet<>
la place!La façon la plus simple est d'utiliser cette:
Bien que cela nécessiterait la création de la liste une fois, puis la création d'une nouvelle liste. Une meilleure façon peut-être pour faire de votre générateur d'avance:
Bien sûr, si vous n'avez pas besoin d'accéder aux éléments par index, vous pourriez probablement améliorer encore plus l'efficacité en supprimant la
ToList
et simplement à l'aide d'unIEnumerable
..Distinct
pour supprimer plusieurs millions de chaînes dans une liste n'est pas efficace de l'OMI.Distinct
utilise unHashSet
, tout comme d'autres l'ont suggéré. La seule partie inefficace est de la génération de la liste de la première, puis à l'aide distinctes, que j'ai abordé dans la deuxième partie de ma réponse.GetRandomStrings
méthode destinée àyield
la chaîne, pas juste régler un local de le jeter ensuite.GetRandomStrings
générer un infiniment longue séquence, puis utiliserTake
de limite à la taille souhaitée. Vous pouvez ensuite mettre leTake
que ce soit avant ou après laDistinct
, selon que vous voulez spécifier le nombre de chaînes de caractères générées ou le nombre de unique chaînes générées.Vous pouvez utiliser un
HashSet<string>
si l'ordre n'est pas important:MSDN
Ou si la commande est important, je vous recommande d'utiliser un SortedSet (.net 4.5 seulement)
SortedSet<T>
trie les éléments. Si un ensemble ordonné est nécessaire (c'est à dire l'élément de maintien de l'ordre)OrderedDictionary
serait un meilleur choix. L'inconvénient est qu'il n'est pas générique.pas une bonne façon mais genre de solution rapide,
prendre un bool pour vérifier si dans la liste il n'y a aucun doublon.
Une table de hachage serait un moyen plus rapide pour vérifier si un élément existe qu'une liste.
Dictionary
au lieu de cela, si vous avez vraiment besoin d'une carte de la structure. Vous ne devriez jamais utiliser une table de hachage non le code de legs.Avez-vous essayé: