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?

22
demandé sur Robert Strauch 2013-06-24 18:57:10

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.

35
répondu Servy 2013-06-24 15:04:26

N'utilisez pas List<>. Utiliser Dictionary<> ou HashSet<> à la place!

9
répondu catfood 2013-06-24 14:59:30

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.

MSDN

Ou si l'ordre est important, je vous recommande d'utiliser un SortedSet (. Net 4.5 uniquement)

5
répondu DGibbs 2013-06-24 15:01:16

, 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.

5
répondu p.s.w.g 2013-06-24 15:05:14

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;
     }

    }
1
répondu Amir Javed 2017-11-26 12:16:47

Une table de hachage serait un moyen plus rapide pour vérifier si un élément existe qu'une liste.

0
répondu Zdravko Danev 2013-06-24 14:58:49

Avez-vous essayé:

myList = myList.Distinct()
0
répondu jdehlin 2013-06-24 15:00:59