Performances lors de la recherche de doublons

Question

J'ai travaillé sur un projet dans lequel je devais parcourir une collection de données et supprimer des entrées où la "clé primaire" est dupliquée. Je l'ai essayé d'utiliser un

List<int> 

et

Dictionary<int, bool> 

Avec le dictionnaire, j'ai trouvé une performance légèrement meilleure, même si je ne dois booléen marqué avec chaque entrée. Mon attente est que c'est parce qu'une liste permet l'accès indexé et non un dictionnaire. Ce que je me demandais, c'est s'il existe une meilleure solution à ce problème. Je n'ai plus besoin d'accéder aux entrées, je n'ai besoin que de suivre les "clés primaires" que j'ai vues et de m'assurer que je ne fais que du travail supplémentaire sur les entrées qui ont une nouvelle clé primaire. J'utilise C# et .NET 2.0. Et je n'ai aucun contrôle sur la fixation des données d'entrée pour supprimer les doublons de la source (malheureusement!). Et donc vous pouvez avoir une idée de la mise à l'échelle, dans l'ensemble, je vérifie les doublons environ 1 000 000 fois dans l'application, mais dans des sous-ensembles de pas plus de 64 000 qui doivent être uniques.

Answer 1

Ils ont ajouté la classe HashSet dans .NET 3.5. Mais je suppose que ce sera à égalité avec le dictionnaire. Si vous avez moins de 100 éléments, une liste fonctionnera probablement mieux.

Answer 2

Je ne comprends pas vraiment ce que vous demandez.

Tout d'abord, c'est juste le contraire de ce que vous dites. Le dictionnaire a indexé l'accès (est une table de hachage) tandis que de liste n'a pas.

Si vous avez déjà les données dans un dictionnaire alors toutes les clés sont uniques, il ne peut y avoir de doublons.

I ssuspect vous avez les données stockées dans un autre type de données et vous le stockez dans le dictionnaire. Si c'est le cas, l'insertion des données fonctionnera avec deux dictionnaires.

foreach (int key in keys) 
{ 
    if (!MyDataDict.ContainsKey(key)) 
    { 
    if (!MyDuplicatesDict.ContainsKey(key)) 
     MyDuplicatesDict.Add(key); 
    } 
    else 
    MyDataDict.Add(key); 
} 

Answer 3

Modifier: Nevermind mon commentaire. Je pensais que vous parlez de C++. Je n'ai aucune idée si mon poste est pertinent dans le monde C#

Une table de hachage pourrait être un peu plus rapide. Les arbres binaires (c'est ce qui est utilisé dans le dictionnaire) ont tendance à être relativement lents à cause de la façon dont la mémoire est accédée. Ceci est particulièrement vrai si votre arbre devient très grand.

Toutefois, avant de modifier votre structure de données, avez-vous essayé d'utiliser un allocateur de pool personnalisé pour votre dictionnaire? Je parie que le temps n'est pas passé à traverser l'arbre lui-même mais dans les millions d'allocations et de désallocations que le dictionnaire fera pour vous.

Vous pouvez voir une augmentation de la vitesse de facteur 10 juste en connectant un simple allocateur de pool dans le modèle de dictionnaire. Afaik boost a un composant qui peut être directement utilisé.

Autre option: Si vous ne connaissez que 64 000 entrées dans vos entiers, vous pouvez les écrire dans un fichier et créer une fonction de hachage parfaite. De cette façon, vous pouvez simplement utiliser la fonction de hachage pour mapper vos entiers dans la gamme 0 à 64.000 et indexer un tableau de bits.

Probablement le moyen le plus rapide, mais moins flexible. Vous devez refaire votre fonction de hachage parfaite (peut être fait automatiquement) chaque fois que votre ensemble d'entiers change.

Answer 4

Si vous vérifiez l'unicité des entiers et que la plage d'entiers est suffisamment limitée, vous pouvez simplement utiliser un tableau. Pour un meilleur conditionnement, vous pouvez implémenter une structure de données bitmap (fondamentalement un tableau, mais chaque int dans le tableau représente 32 ints dans l'espace clé en utilisant 1 bit par clé). Ainsi, si votre nombre maximal est de 1 000 000, vous n'avez besoin que de ~ 30,5 Ko de mémoire pour la structure de données.

Les performances d'un bitmap seraient O (1) (par contrôle) ce qui est difficile à battre.

Answer 5

Il y avait une question un certain temps en arrière sur removing duplicates from an array. Dans le but de la question, la performance n'était pas très importante, mais vous pourriez jeter un coup d'œil aux réponses, car elles pourraient vous donner quelques idées. En outre, je pourrais être hors base ici, mais si vous essayez de supprimer des doublons du tableau alors une commande LINQ comme Enumerable.Distinct pourrait vous donner de meilleures performances que quelque chose que vous écrivez vous-même. Comme il s'avère qu'il y a un moyen d'obtenir LINQ working on .NET 2.0 alors cela pourrait être un itinéraire qui mérite d'être étudié.

Answer 6

Si vous allez utiliser une liste, utilisez le BinarySearch:

// initailize to a size if you know your set size 
List<int> FoundKeys = new List<int>(64000); 
Dictionary<int,int> FoundDuplicates = new Dictionary<int,int>(); 

foreach (int Key in MyKeys) 
{ 
    // this is an O(log N) operation 
    int index = FoundKeys.BinarySearch(Key); 
    if (index < 0) 
    { 
     // if the Key is not in our list, 
     // index is the two's compliment of the next value that is in the list 
     // i.e. the position it should occupy, and we maintain sorted-ness! 
     FoundKeys.Insert(~index, Key); 
    } 
    else 
    { 
     if (DuplicateKeys.ContainsKey(Key)) 
     { 
      DuplicateKeys[Key]++; 
     } 
     else 
     { 
      DuplicateKeys.Add(Key, 1); 
     } 
    } 
} 

Vous pouvez également l'utiliser pour tout type pour lequel vous pouvez définir un IComparer en utilisant une surcharge: BinarySearch (T article, IComparer < T>);