Suppression de doublons dans une collection

Bonjour,

Je doit gérer une collection d'objets et je voudrais supprimer de cette collection les doublons. Essentiellement, un objet contient des données sur 20 char. Un objet est égal à un autre objet si les 20 char des 2 objets sont égaux.

La solution à base de hash ne me plait pas trop car avec un hash il est possible d'avoir des collisions (c'est rare mais cela peut arriver) et à ce moment, je pourrai croire à tord que 2 objets sont identiques parce que leurs hash sont identiques.

Pour l'instant, ma collection contient environ 2 000 000 objets avec un certain (probablement grand) nombre de doublons. Au final, je ne connais pas encore le nombre d'objets uniques de ma collection (et je n'ai encore aucun ordre de grandeur).

Actuellement, je vois 2 options possibles :

• soit faire une std::map avec comme clé les 20 char. Est ce que c'est jouable en terme de performance ?
• soit le gérer comme une std::list ou un std::vector (peut m'importe) et ensuite faire du ménage dans cette collection. Mais j'ai peur que cela soit un peu long car pour cela, il faut tester chaque objet avec les autres objets de la liste et supprimer en cas d'égalité.

Si vous avez des idées pour essayer d'organiser un peu cela, je suis preneur

Merci d'avance

As tu testé std::unique ?

Vecteur trié+std::unique >> all

En tout cas c'est ce que j'en ai conclu, il y a quelque temps, quand j'avais eu affaire à cette problématique de l'élimination de doublon.
C'est un résultat assez surprenant, alors pour se convaincre, voici le bench que j'avais utilisé pour comparer les performances d'un vecteur trié face à un std::set.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

#include <stdio.h> #include <vector> #include <set> #include <windows.h> #include <algorithm> #include <time.h>   using namespace std;   struct Chrono { LARGE_INTEGER liStart; LARGE_INTEGER liStop; void TimeStart() { QueryPerformanceCounter(&liStart); } double TimeStop() { QueryPerformanceCounter(&liStop); LONGLONG llTimeDiff = liStop.QuadPart - liStart.QuadPart; // To get duration in milliseconds LARGE_INTEGER Frequency; QueryPerformanceFrequency(&Frequency); return llTimeDiff * 1000.0 / (double) Frequency.QuadPart; } };   double TestSet(int size, int numDiff) { std::vector<int> vec; vec.reserve(size); for(int i = 0 ; i < size ; i++) { vec.push_back(i%numDiff); } std::random_shuffle(vec.begin(), vec.end());   Chrono chrono; chrono.TimeStart(); { std::set<int> set(vec.begin(), vec.end()); } return chrono.TimeStop(); }   double TestVecUnique(int size, int numDiff) { std::vector<int> vec; vec.reserve(size); for(int i = 0 ; i < size ; i++) { vec.push_back(i%numDiff); } std::random_shuffle(vec.begin(), vec.end());   Chrono chrono; chrono.TimeStart(); { std:vector<int> vecTemp(vec.begin(), vec.end()); std::sort(vecTemp.begin(), vecTemp.end()); std::vector<int>::iterator it = std::unique(vecTemp.begin(), vecTemp.end()); vecTemp.erase(it, vecTemp.end()); } return chrono.TimeStop(); }   int main(int, const char **) { srand(time(NULL)); double timeSet; double timeVec; for(int size = 100 ; size < 100000000 ; size*= 10) { printf("Size;%d \n", size); printf("NumDiff;Set;Vec \n"); // cas particulier 1% timeSet = TestSet(size, size / 100); timeVec = TestVecUnique(size, size / 100); printf("%d;%lf;%lf \n", size / 100, timeSet, timeVec); for(int numDiff = size / 10 ; numDiff <= size ; numDiff += size / 10) { timeSet = TestSet(size, numDiff); timeVec = TestVecUnique(size, numDiff); printf("%d;%lf;%lf \n", numDiff, timeSet, timeVec); } printf("\n"); }   return 0; }

---

Et voici les résultats avec :
Size : la taille de la collection avant élimination des doublons
numDiff : le nombre d'élément différents des un des autres (numDoublon = size - numDiff)
Set : élimination des doublons par un set. En milliseconde.
Vec : élimination des doublons par un vecteur trié+unique. En milliseconde.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Size;100 NumDiff;Set;Vec 1;0.009331;0.005186 10;0.021397;0.007217 20;0.031600;0.007408 30;0.078742;0.011280 40;0.114401;0.011898 50;0.119688;0.007535 60;0.143782;0.009559 70;0.160514;0.008126 80;0.151954;0.008059 90;0.164671;0.008691 100;0.175543;0.008111   Size;1000 NumDiff;Set;Vec 10;0.058246;0.062074 100;0.237557;0.056166 200;0.419861;0.065460 300;0.778715;0.075868 400;1.902010;0.081327 500;2.635337;0.085222 600;3.877631;0.094055 700;6.003849;0.097797 800;6.439356;0.068487 900;7.695164;0.074974 1000;8.088372;0.076763   Size;10000 NumDiff;Set;Vec 100;1.244992;0.464496 1000;8.958092;0.762638 2000;10.760756;0.822186 3000;10.022801;0.879980 4000;10.294734;0.869208 5000;26.431818;0.861003 6000;15.297400;0.881147 7000;30.017814;0.897115 8000;34.178131;0.911774 9000;21.579112;0.885079 10000;35.546294;0.971334   Size;100000 NumDiff;Set;Vec 1000;11.385602;6.586281 10000;43.343816;9.487416 20000;61.422820;10.260537 30000;2240.689171;10.437970 40000;104.971388;10.396279 50000;4229.935116;11.202647 60000;153.447866;10.677061 70000;6293.117118;10.647953 80000;1035.541378;10.739640 90000;213.434489;10.849125 100000;1640.188878;10.928529   Size;1000000 NumDiff;Set;Vec 10000;1015.262822;85.749305 100000;512.347524;115.827532 200000;1051.986863;123.923951 300000;1302.595575;124.838696 400000;1584.562308;126.248261 500000;1889.364376;129.221107 600000;2149.818646;129.572463 700000;2411.742239;128.696094 800000;2673.389705;128.797973 900000;2970.527587;136.126063 1000000;3231.641173;132.516706   Size;10000000 NumDiff;Set;Vec 100000;3461.778743;1098.170122 1000000;12810.827493;1388.492879 2000000;17191.687660;1480.408927 3000000;20779.838737;1481.620279 4000000;24020.703445;1492.736466 5000000;27510.376355;1500.716572 6000000;30857.600592;1505.075667 7000000;33551.772354;1533.484095 8000000;36738.283928;1523.860454 9000000;39979.293069;1527.725204 10000000;43934.275632;1534.260277

---

Résultat épatant. Vecteur trié+sort pulvérise le set dans de grande largeur. Avec l'avantage supplémentaire d'avoir un temps d'exécution quasi insensible aux nombres de doublons.

Il y a par contre quelques restrictions pour utiliser un vecteur trié+sort :

• Il faut connaitre à l'avance le nombre d'objet (ou une estimation) pour faire un reserve() sur le vecteur avant de commencer. Évidement, subir une réallocation du vecteur alors qu'on approche les deux millions d'objets serait une catastrophe. :D
• Le trie et l'élimination des doublons ne doit se faire qu'en une seule passe, une fois le vecteur entièrement peuplé.

Un dernier point à considérer:
Le bench est fait avec des int. Je n'ai pas essayé avec des objets plus lourds (comme avec 20 char). Peut être que la différence set/vec s'amortit un peu quand la fonction de comparaison devient plus complexe...

Breaking news !
Je viens d'essayer le même bench avec non plus des int, mais un tableau de 20 char : le set repasse devant !

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

double TestSet(int size, int numDiff) { std::vector<std::tr1::array<char, 20> > vec; vec.reserve(size); for(int i = 0 ; i < size ; i++) { std::tr1::array<char, 20> ar; ar.assign(i%numDiff); vec.push_back(ar); } std::random_shuffle(vec.begin(), vec.end());   Chrono chrono; chrono.TimeStart(); { std::set<std::tr1::array<char, 20> > set(vec.begin(), vec.end()); } return chrono.TimeStop(); }   double TestVecUnique(int size, int numDiff) { std::vector<std::tr1::array<char, 20> > vec; vec.reserve(size); for(int i = 0 ; i < size ; i++) { std::tr1::array<char, 20> ar; ar.assign(i%numDiff); vec.push_back(ar); } std::random_shuffle(vec.begin(), vec.end());   Chrono chrono; chrono.TimeStart(); { std:vector<std::tr1::array<char, 20> > vecTemp(vec.begin(), vec.end()); std::sort(vecTemp.begin(), vecTemp.end()); std::vector<std::tr1::array<char, 20> >::iterator it = std::unique(vecTemp.begin(), vecTemp.end()); vecTemp.erase(it, vecTemp.end()); numDiff = std::distance(vecTemp.begin(), vecTemp.end()); } return chrono.TimeStop(); }

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Size;100 NumDiff;Set;Vec 1;0.017308;0.015112 10;0.049286;0.032823 20;0.066795;0.034032 30;0.058669;0.021670 40;0.071453;0.019612 50;0.122292;0.028977 60;0.148833;0.022059 70;0.191036;0.020653 80;0.312269;0.035360 90;0.224376;0.020888 100;0.358195;0.019489   Size;1000 NumDiff;Set;Vec 10;0.217971;0.206904 100;0.501581;0.274249 200;1.736613;0.259280 300;2.302662;0.274272 400;2.380457;0.263186 500;2.286365;0.242776 600;2.301794;0.262400 700;2.282268;0.256608 800;2.292433;0.252339 900;2.310856;0.291029 1000;2.283502;0.246035   Size;10000 NumDiff;Set;Vec 100;2.750161;2.513143 1000;4.335782;2.785233 2000;4.054918;2.975263 3000;4.076775;3.034078 4000;4.088957;2.980827 5000;4.064455;2.869639 6000;4.156235;2.932072 7000;4.133271;3.037831 8000;4.176716;2.984841 9000;4.082069;2.857005 10000;4.217538;2.902253   Size;100000 NumDiff;Set;Vec 1000;22.701969;25.548583 10000;22.309734;28.005998 20000;22.519964;27.170829 30000;22.527645;27.240139 40000;22.399405;26.453507 50000;22.593565;27.911666 60000;22.325078;27.565069 70000;22.477484;28.228593 80000;22.715172;26.008683 90000;22.453176;28.735274 100000;22.253213;28.811789   Size;1000000 NumDiff;Set;Vec 10000;206.939984;296.880627 100000;204.364704;278.498449 200000;206.658884;281.842623 300000;204.815836;286.686073 400000;206.400708;288.817401 500000;204.296734;266.499626 600000;202.995348;289.643381 700000;205.263873;281.145452 800000;204.421847;299.796947 900000;203.752527;283.942863 1000000;205.044309;296.099794   Size;10000000 NumDiff;Set;Vec 100000;2029.474719;2960.651473 1000000;2027.945160;2713.088658 2000000;2034.837006;2933.232427 3000000;2023.666251;3319.375480 4000000;2026.635644;2825.213376 5000000;2043.045469;2803.486651 6000000;2042.490379;2969.161056 7000000;2038.601650;2830.752725 8000000;2035.688641;2837.979502 9000000;2027.202198;2842.233654 10000000;2038.236167;2785.206475

---

C'est embêtant :aie:
J'imagine que le problème vient du fait que la copie et la comparaison d'int est ultra rapide, contrairement à celles de tableaux de 20 char...
Hé, hé je ne suis pas sûr d'avoir fait avancer le schmilblick au final :aie:

Si tu as vraiment beaucoup de doublons, je pense qu'une solution à base de hash peut en fait être intéressante. Ce qui ne veut pas dire que tu supprimes quand le hash est identique, mais que tu utilises ce hash pour subdiviser ton jeu de données initial, et qu'ensuite tu appliques un algorithme sur sur ces sous jeux de donnée.

Ensuite, effectivement, l'algo classique est un tri + recherche d'éléments uniques (Arzar : Si les objets sont gros, peut-être le vecteur peut-il regagner si on gère uniquement un vecteur de pointeurs ?).

Donc, si on décompose tes N données en M sous groupes de taille n (avec un bon algo de hash, on a environ n = N/M), le coût total est de :
Répartition en groupe + Elimination des doublons de chaque groupe
= O(N) + M*O(n log n)
= O(N) + O(N log(N/M))
A comparer au O(N log N) obtenu en appliquant l'algorithme initial.

Au final, on n'a donc pas perdu en terme de complexité algorithmique, et on peut espérer que les constantes seront favorables, en règlant bien la valeur de M en fonction des données.

Le set, t'es censé mettre les données directement dedans, pas l'utiliser comme copie intermédiaire pour trier.

Citation:

---

Envoyé par JolyLoic

Arzar : Si les objets sont gros, peut-être le vecteur peut-il regagner si on gère uniquement un vecteur de pointeurs ?

---

Ben non :aie:
Les chronos du vecteur sont même un peu plus lent si on passe en vecteur de pointeur.
Pour faire le test, j'ai rajouté une classe Array contenant le tableau de 20 char, puis manipulé des vector<Array*>

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

struct Array { Array(char c) { ar.assign(c); } std::tr1::array<char, 20> ar; };     struct LessThan : public std::binary_function<Array*, Array*, bool> { bool operator()(const Array* e1, const Array* e2) const { return e1->ar < e2->ar; } };   struct FreePointer : public std::unary_function<Array*, void> { void operator()(Array* e) { delete e; } };

---

Et le résultat avec
vector<Array*> face à set<Array*>

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

Size;100 NumDiff;Set;Vec 1;0.022598;0.055758 10;0.036595;0.060570 20;0.066414;0.087949 30;0.059077;0.058351 40;0.106780;0.084118 50;0.082865;0.056245 60;0.108789;0.059582 70;0.282720;0.057277 80;0.210252;0.058665 90;0.336360;0.058778 100;0.238253;0.056488   Size;1000 NumDiff;Set;Vec 10;0.213511;0.652315 100;1.567857;0.708769 200;2.979255;0.701238 300;3.786648;0.710299 400;3.932761;0.713943 500;3.778005;0.766263 600;3.736760;0.724161 700;3.651407;0.709263 800;3.660641;0.773589 900;3.706346;0.702266 1000;3.699858;0.761070   Size;10000 NumDiff;Set;Vec 100;2.587892;6.540932 1000;2.503202;8.580790 2000;5.532117;7.290580 3000;2.461833;8.590959 4000;5.664847;7.277226 5000;2.466364;8.653493 6000;5.555328;6.812255 7000;2.515919;9.142817 8000;5.518348;7.109405 9000;2.556539;9.076785 10000;5.553106;6.864145   Size;100000 NumDiff;Set;Vec 1000;21.270221;96.387545 10000;21.265817;93.811416 20000;20.804486;97.693694 30000;21.604131;92.699682 40000;20.752223;100.211596 50000;23.329336;93.971709 60000;20.920927;93.488656 70000;23.218998;87.173540 80000;21.029525;94.140320 90000;21.737250;91.329802 100000;20.905995;96.727845   Size;1000000 NumDiff;Set;Vec 10000;205.878699;1291.420469 100000;205.235663;1308.169438 200000;205.448239;1375.609228 300000;205.590259;1353.584634 400000;205.271349;1434.734167 500000;206.184548;1431.670023 600000;206.378960;1437.910157 700000;205.850328;1435.395622 800000;207.554765;1492.617657 900000;204.109199;1448.662184 1000000;205.187354;1507.025050   Size;10000000 NumDiff;Set;Vec 100000;2059.328727;20971.176490 1000000;2062.475975;20825.865777 2000000;2058.102517;20680.181394 3000000;2058.974819;20997.587375 4000000;2057.099883;20271.702848 5000000;2062.745727;20657.014035 6000000;2075.983103;20645.505734 7000000;2058.503290;20672.108205 8000000;2068.312837;20399.355212

---

C'est un peu déboussolant. J'essayerais demain de passer un coup de profiler pour comprendre ce qui se passe.

Ha oui, et un autre résultat frappant et un peu mystérieux : Les chronos d'un set<int> varient considérablement en fonction du nombre de doublon, par contre ceux d'un set<array<char, 20>> (ou set<Array*>) sont quasiment constants...

C'est bon, j'ai résolu mon problème

std::sort puis std::unique me vont très bien.

En ce qui concerne la taille, plutôt que faire un gros travail à la fin d'élimination des doublons, je fais plusieurs fois le travail en cours de route. Cela me permet de ne pas avoir un vector énorme à gérer.

Au final, j'ai tout de même 363 480 objets différents parmi une liste de environ 4 000 000 d'objets