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 motif donné. Ces chaînes sont stockées dans une liste. Comme aucun doublon n'est autorisé, je le fais 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 confronté à la situation pour générer plusieurs millions de chaînes. Et avec chaque chaîne ajoutée, la vérification des doublons devient de plus en plus lente.
Existe-t-il des moyens plus rapides d'éviter les doublons?
7 réponses
Utilisez une structure de données qui peut déterminer beaucoup plus efficacement 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 avez vraiment besoin des éléments dans unList à la place, ou si vous avez besoin que les éléments de la liste résultante soient dans l'ordre dans lequel ils ont été générés, vous pouvez stocker les données à la fois dans une liste et un hashset; ajouter l'élément aux deux collections s'il n'existe pas actuellement dans HashSet.
N'utilisez pas List<>. Utiliser Dictionary<> ou HashSet<> à la place!
Vous pouvez utiliser un HashSet<string> si l'ordre n'est pas important:
HashSet<string> myHashSet = new HashSet<string>();
for (int i = 0; i < total; i++)
{
string random_string = GetRandomString(pattern);
myHashSet.Add(random_string);
}
La classe HashSet fournit des opérations de jeu hautes performances. Un ensemble est une collection qui ne contient pas d'éléments en double et dont les éléments ne sont pas dans un ordre particulier.
Ou si l'ordre est important, je vous recommande d'utiliser un SortedSet (. Net 4.5 uniquement)
, Le plus simple est d'utiliser ceci:
myList = myList.Distinct().ToList();
Bien que cela nécessiterait de créer la liste une fois, puis de créer une nouvelle liste. Une meilleure façon pourrait être de faire votre générateur à l'avance:
public IEnumerable<string> GetRandomStrings(int total, string pattern)
{
for (int i = 0; i < total; i++)
{
yield return GetRandomString(pattern);
}
}
...
myList = GetRandomStrings(total, pattern).Distinct().ToList();
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'un IEnumerable.
Pas un bon moyen mais une sorte de solution rapide, prenez un bool pour vérifier si dans toute la liste il y a une entrée en double.
bool containsKey;
string newKey;
public void addKey(string newKey){
foreach(string key in MyKeys){
if(key == newKey){
containsKey = true;
}
}
if(!containsKey){
MyKeys.add(newKey);
}else{
containsKey = false;
}
}
Une table de hachage serait un moyen plus rapide pour vérifier si un élément existe qu'une liste.