Performance lors de la recherche de doublons

Question

Je travaille sur un projet où je dois parcourir une collection de données et supprimer des entrées contenant la & "clé primaire &"; est dupliqué. J'ai essayé d'utiliser un

List<int>

et

Dictionary<int, bool>

Avec le dictionnaire, les performances étaient légèrement meilleures, même si je n’ai jamais besoin que la valeur booléenne soit étiquetée à chaque entrée. Mon attente est que cela est dû au fait qu'une liste permet un accès indexé et qu'un dictionnaire ne le permet pas. Ce que je me demandais, c'est s'il existe une meilleure solution à ce problème. Je n'ai pas besoin d'accéder à nouveau aux entrées, je n'ai qu'à suivre ce que & "; Clés primaires &"; J'ai vu et m'assure de n'effectuer des travaux supplémentaires que sur les entrées possédant 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 pour que vous puissiez avoir une idée de la mise à l’échelle, dans l’ensemble, je vérifie les doublons environ 1 000 000 de fois dans l’application, mais pas plus de 64 000 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

Edit: Ce n'est pas grave. Je pensais que vous parliez de C ++. Je n'ai aucune idée si mon message 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 utilisée. Cela est particulièrement vrai si votre arbre devient très grand.

Cependant, 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 dictionnaire ne vous fera pas perdre du temps, mais bien dans les millions d'allocations et de désallocations que le dictionnaire fera pour vous.

Vous pouvez constater un facteur 10 d’augmentation de la vitesse en connectant simplement un allocateur de pool au modèle de dictionnaire. Afaik boost contient un composant directement utilisable.

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 plage de 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 effectuée automatiquement) chaque fois que votre ensemble d’entiers change.

Answer 3

Je ne comprends pas vraiment ce que vous demandez.

Tout d’abord, c’est tout le contraire de ce que vous dites. Le dictionnaire a un accès indexé (est une table de hachage) alors que de List n’en 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.

Je pense que vous avez les données stockées dans un autre type de données et que vous les stockez dans le dictionnaire. Si tel 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 4

Si vous recherchez l'unicité des nombres entiers et que la plage de nombres entiers est suffisamment contrainte, vous pouvez simplement utiliser un tableau.

Pour une meilleure compression, vous pouvez implémenter une structure de données bitmap (en gros, un tableau, mais chaque entier du tableau représente 32 ints dans l’espace clé en utilisant 1 bit par clé). Ainsi, si votre nombre maximum est de 1 000 000, vous n’avez besoin que d’environ 30,5 Ko de mémoire pour la structure de données.

Performances d’un bitmap correspondrait à O (1) (par contrôle), ce qui est difficile à battre.

Answer 5

Il y avait une question à propos de suppression des doublons d'un tableau . Pour les besoins de la question, la performance n’a pas été prise en compte, mais vous pouvez regarder les réponses car elles pourraient vous donner quelques idées. De plus, je ne serais peut-être pas au bon endroit ici, mais si vous essayez de supprimer les doublons du tableau, utilisez une commande LINQ telle que Enumerable.Distinct peut vous offrir de meilleures performances que quelque chose que vous écrivez vous-même. En fin de compte, il existe un moyen d'obtenir LINQ travaillant sur .NET 2.0 , ce serait donc une voie à explorer.

Answer 6

Si vous envisagez d'utiliser une liste, utilisez 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 tous les types pour lesquels vous pouvez définir un IComparer en utilisant une surcharge: BinarySearch (élément T, IComparer < T >);