Discussion :

[Art19]

je crois que je vais plutot m'orienter vers la solution proposee par sovitec (car je n'ai pas besoin de trier les fichiers)

[Gilbert Geyer]

Résultats de tests effectués avec l'algo de recherche-de-doublons d'Art19

1) Essais avec THashedStringList : impossibles à réaliser, msg "Identificateur non déclaré" : n'existe pas sous Delphi5.
En conséquence je l'ai remplacé par TStringList pour continuer les tests;

2) Essais avec TStringList :
avec lignes.Sorted:=TRUE résultat 112 x plus rapide qu'avec false.
Faudrait qu'Art19 essaye la même chose avec sa THashedStringList

3) Essais avec lecture de chaque chaîne via FileStream puis tests via StringList.IndexOf(s)) :
Gain de vitesse microscopique, la lecture du flux étant interrompue pour chaque chaîne par le test de présence dans la StringList qui accumule les lignes jusqu'à la rencontre du premier doublon.
(pour détecter le 1er doublon situé en fin du fichier de 200 004 lignes, avec ou sans FileStream, cela a quand-même pris 5 minutes 1/2 de Pentium III à 1.13GHz).

4) Fichier de tests utilisé : Fichier de 200 004 lignes entièrement aléatoire à l'exception du ChampN où j'ai remplacé le 1 terminal par le n° de ligne (car auparavent il y apparaissait des vrais-doublons-aléatoires) pour avoir la certitude que le fichier ne comporte qu'un seul et unique doublon-de-fin-de-fichier :

01/16/06,19:38,0.82,0.00,0.65,0.20,0.93,0.96,0.70,0.51,0.53,199998
06/13/00,03:55,0.02,0.26,0.60,0.26,0.27,0.70,0.83,0.59,0.57,199999
02/22/73,18:40,0.74,0.89,0.97,0.90,0.57,0.24,0.42,0.76,0.04,200000
ANAGRAMME
EMMARGANA
<<< MI-DOUBLON >>>
<<< MI-DOUBLON >>>

5) Réponse à Art19 / "je ne sais pas si je pourrais loader tout un fichier dans une THashedStringList" :
Les 200 004 lignes de mon fichier de tests ont été loadées en totalité dans uns StringList en conséquence de quoi elles devraient également tenir dans THashedStringList vu que THashedStringList est plus que certainement un descenndant du TStringList ... et comme t'as bien dit récemment que tes plus gros fichiers c'est 200 000 lignes tu peux être tranquille.
Mais si tu veux faire un test avec davantage de lignes, voiçi le code qui génère le fichier d'essais.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
procedure TForm1.SpeedButton3Click(Sender: TObject);
//        crée 200 000 lignes aléatoires + 2 anagrammes + 2 mi-doublons
//        C:\...\ftAL200000x62.txt : 200000 lignes 12600062 Octets mis : 20818 ms
//        modèle de base 10/28/05,16:04,0.86,0.86,0.86,0.86,1
//        mm/jj/aa,hh:mi,
const     Nmax = 10;
var       FS : TFileStream; NomFichier,LigAl : string;
          numLig : integer; ChronoC : oChrono;
 
          procedure calibrer(var num : shortString);
          begin     while length(num)<2 do num:='0'+num; end;
 
          function DateHeureAl : shortString; // Date et heure Aléatoire
          var      sp,sr : shortString;
          begin    sp:=intToStr(1 + Random(11)); calibrer(sp); sr:=sp+'/';     //mm
                   sp:=intToStr(1 + Random(30)); calibrer(sp); sr:=sr+sp+'/';  //jj
                   sp:=intToStr(0 + Random(99)); calibrer(sp); sr:=sr+sp+',';  //aa
                   sp:=intToStr(0 + Random(24)); calibrer(sp); sr:=sr+sp+':';  //hh
                   sp:=intToStr(0 + Random(59)); calibrer(sp); sr:=sr+sp+',';  //mi
                   Result:=sr;
          end;
 
          function champs1aN(N : integer) : shortString; // champs1aNmoins1 Aléatoires
          var      sp,sr : shortString; i : integer;
          begin    sr:='';
                   for i:=1 to N-1 do // champs 1 à N-1 Aléatoires
                   begin sp:=intToStr(0 + Random(99));
                         calibrer(sp); sp:='0.'+sp; sr:=sr+sp+',';
                   end;
                   //sp:=intToStr(0 + Random(9)); sr:=sr+sp; // champ N Aléatoire
                   // Champ N pris égal au numéro de ligne sinon doublons-aléatoires-perturbateurs
                   Result:=sr;
          end;
 
begin     NomFichier:=ExtractFilePath(Application.ExeName)+'ftAL200000x62.txt';
          if fileExists(NomFichier) then
          begin if MessageDlg( NomFichier+' : existe déjà : Ecraser ?',
                               mtConfirmation, [mbYes, mbNo], 0) = mrYes
                then DeleteFile(NomFichier)
                else NomFichier:= InputBox('Créer fichier aléatoire sous autre nom' , NomFichier, NomFichier);
          end;
 
          FS := TFileStream.Create(NomFichier, fmCreate);
          Sablier;
          ChronoC.Top(Edit1);
          Randomize;
          numLig:=0;
          repeat inc(numLig);
                 LigAl:=DateHeureAl+champs1aN(Nmax)+intToStr(numLig)+#13#10;
                 //redRapport.Lines.Add(ligAl);
                 FS.Write(PChar(LigAl)^, length(LigAl));
          until numLig=200000; //10000;
          LigAl:='ANAGRAMME'+#13#10;
          FS.Write(PChar(LigAl)^, length(LigAl));
          LigAl:='EMMARGANA'+#13#10;
          FS.Write(PChar(LigAl)^, length(LigAl));
          LigAl:='<<< MI-DOUBLON >>>'+#13#10;
          FS.Write(PChar(LigAl)^, length(LigAl));
          FS.Write(PChar(LigAl)^, length(LigAl));
          redRapport.Lines.Add( NomFichier+' : '+intToStr(numLig)
                               +' lignes '+intToStr(FS.size)+' Octets'
                               +' mis : '+intToStr(ChronoC.Mis)+' ms');
          Sablier;
          FS.Free;
end;

[Art19]

Que fait le lignes.Sorted exactement?

bon donc si je supprime mes doublons je ferais mettrai surement lignes.Sorted a true et je loaderai mon fichier dans ma liste avant de faire un SaveToFile..

le SaveToFile est-il efficace?

[Gilbert Geyer]

Réponse / "Que fait le lignes.Sorted exactement?" :

Extrait de l'aide-Delphi /propriété Sorted: Boolean;

Affectez la valeur True à Sorted pour trier automatiquement les chaînes de la liste en ordre croissant.
Si Sorted a la valeur False, les chaînes restent à la position où elles sont insérées. Si Sorted a la valeur False, il est possible, à tout moment, de trier une liste en ordre croissant en appelant la méthode Sort.

Suggestion / "je mettrai surement lignes.Sorted a true" :
Y'a intérêt ! Et y'a encore mieux : Ajoutes sur la ligne suivante lignes.Duplicates:=dupIgnore; cela aura pour effet qu'il ne s'accumulura dans la liste nommée lignes qu'un seul et unique spécimen de chaque string qu'on lui envoie avec Add(s), en bref il n'y aura donc aucun doublon dans la liste nommée lignes. Et si tu achèves la boucle avec lines.SaveToFile(nomFichier); tu retrouveras sur ton disque-dur le petit-frère du fichier-d'origine non seulement trié mais débarassé de tout doublon ... et tout cela avec très peu de lignes.

"le SaveToFile est-il efficace?" : oui!

[Art19]

juste un bemol: avec la THashedStringList, le 'sorted' fou tout en l'air

[Gilbert Geyer]

Si avec THashedStringList, le 'sorted'=true fou tout en l'air
alors faut peser le pour et le contre entre conserver THashedStringList ou le remplacer par TStringList avec 'sorted'=true et 'Duplicates'=dupIgnore et les avantages que cela entraîne.
Dommage que tu n'aies pas mis un chrono dans ta routine avant de dire "1000 fois plus rapide" au moins on saurait de combien il était plus rapide qu'avec la StringList avec sorted=false. (peut-être que c'est seulement 100 au lieu de 1000 ? dans quel cas le choix serait vite fait).
Chez moi, avec ton code en version StringList.sorted=true il est 112 fois plus rapide qu'avec false avec chrono à l'appui.
Mais mon Delphi5 n'a pas la THashedStringList je n'ai donc pas pu tester ton code pour en comparer sa vitesse à celle du même code en version StringList.

Mets donc un chrono dans ton code y'a rien de mieux pour faire un bon diagnostic et pour aider à la prise de décisions. En plus un chrono c'est hyper simple à créer avec GetTickCount.

[Art19]

j'ai essaye avec la THashedStringList mais j'ai une fuite de memoire. Voila mon code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 fichiers.LoadFromFile('doublons.txt');
 
  for i := 0 to fichiers.Count-1 do begin
 
    lignes.Clear();
 
    AssignFile( fich, fichiers[i] );
    Reset( fich );
 
    while not Eof(fich) do begin
       ReadLn( fich, s );
 
       if lignes.IndexOf( s ) = -1 then begin
 
          lignes.Add(s);
 
       end;
 
 
    end;
 
 
 
    CloseFile( fich );
    lignes.SaveToFile(fichiers[i]);
 
 
 
  end;

theoriquement je ne devrais pas avoir plus de 100 000 K de memoire vive utilisee car je ne charge qu'un fichier a la fois et mes fichiers ne sont pas si gros or je me retrouve avec plus de 1 200 000 K et celle ci ne fait qu'augmenter (alors que je fais bien un lignes.Clear())

quelqu'un a une idee?

Apparemment ce n'est pas une fuite de memoire, mais je dois avoir des fichiers beaucoup plus gros que prevu!!! je vous tiens au courant

[Art19]

j'ai un effet de bord bizarre la..: quand je fais mon lignes.Clear sur une grosse liste, j'ai d'abord une augmentation de ma memoire vive avant qu'elle diminue

[Art19]

sur mon

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

while not Eof(fich) do begin

j'ai une erreur I/O. comment puis-je y remedier?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

EInOutError with message 'I/O error 6'

[Gilbert Geyer]

A Sovitec / message du 8 juin 2007, 09h38, sur l'algorithme MD5 :
Merci pour ces infos. J'aime bien la prose de Wikipédia qui dit que "Message Digest 5, est une fonction de hachage cryptographique très populaire"
Si j'avais su , je n'aurais pas posé ma question ici mais j'aurais peut-être interrogé discrètement notre concierge(lol).

Par contre vu la complexité du pseudo-code qu'ils donnent, et qu'ils disent en plus "mais qu'il n'est plus considéré comme un algorithme sûr", je me demande bien à quelle usine-à-gaz les algos plus performants doivent ressembler.

[Gilbert Geyer]

A E-ric / message du 07/06/2007, 10h06 et message du 8 juin 2007, 15h53 :
Dans le 1er message tu dis "Si le fichier fait quelques Go.." et dans le suivant tu nous informes sur "La solution sur laquelle je travaille devrait m'affranchir des limites de taille sur les fichiers à 2 Go".

A toutes fins utiles je te signales qu'Art19 ne parle plus de fichiers de "plusieurs Go" depuis qu'il nous a précisé dans son message du 06/06/2007, 19h53 que ses "plus gros fichiers sont de l'ordre de 200 000 lignes et mes plus petits de l'ordre de 5000 lignes. en moyenne ~ 44 000 lignes" ... en bref le plus gros fichier de 200 000 lignes fait une douzaine de Mo ... ce qui change carrément la problèmatique.

C'est donc plutôt la somme des 19 000 fichiers cités dans son msg du 8 juin 2007, 16h02 qui totalise des Go mais seulement sur le disque.

[Gilbert Geyer]

A Art19 / message du 8 juin 2007, 18h43 :

- Remarque / ligne if lignes.IndexOf( s ) en plein dans la boucle centrale : Comme cette ligne nécessite pour Delphi de comparer chaque nouvelle ligne à toutes celles qui sont déjà présentes dans la liste lignes notamment lorsqu'un doublon est planqué en fin de fichier cela ralentit forcément la moulinette.

- Remarque / "memoire vive utilisee car je ne charge qu'un fichier a la fois et mes fichiers ne sont pas si gros or je me retrouve avec plus de 1 200 000 K et celle ci ne fait qu'augmenter ... quelqu'un a une idee?" :
Bizarre, car on ne trouve dans ton code aucune instruction qui affiche la mémoire vive utilisée et encore moins sa progression. !?

- Remarque / "mais je dois avoir des fichiers beaucoup plus gros que prevu!!!" : Ce serait sympa qu'on sache enfin sur quel pied danser.

- Réponse / message du 8 juin 2007, 15h13 à propos de est-il raisonable de supprimer les doublons en triant, comparant chaque ligne à la ligne précédente et en supprimant s'il y a doublon :
Suite à des essais, Oui. Le code suivant est basé sur ce principe et a subi diverses configurations (de A à E) pour éviter les ralentissements dus entre'autres au if lignes.IndexOf( s ) et la configarion actuelle "E)" est 71 fois plus rapide que les autres. Le détail des résultats est regroupé dans les commentaires situés en fin de ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
93
94
95
96
procedure TForm1.bAlgoSupprDoublonsClick(Sender: TObject);
var       pop,i,j : Integer;
          lignes : TstringList; // Exit THashedStringList
          NomCourtFichier, NomLongFichierOrig, RepAppli : string; chronoA : oChrono;
          NomSauverSous : string;
begin
          lignes := TStringList.Create;
          
          RepAppli:=ExtractFilePath(Application.ExeName);
          OpenDialog1.InitialDir := RepAppli;
          OpenDialog1.Filter:= 'Fichiers Texte (*.txt)|*.TXT';
          if OpenDialog1.Execute then
          begin 
                Application.ProcessMessages;
                ChronoA.Top(Form1.Edit1);
                NomLongFichierOrig:=OpenDialog1.FileName;
                NomCourtFichier:=ExtractFileName(NomLongFichierOrig);
                pop := pos('.',NomCourtFichier);
                if pop>0 then Insert('_noDup',NomCourtFichier,pop)
                         else NomCourtFichier:=NomCourtFichier+'_noDup';
                NomSauverSous:=RepAppli+NomCourtFichier;

                lignes.Clear;
                lignes.Sorted := FALSE;  // insertion plus rapide s'il n'y a pas de recherche simultanée
                lignes.LoadFromFile( NomLongFichierOrig );
                redRapport.lines.add('LoadFromFile : mis : '+intToStr(chronoA.mis)+ ' ms');
                redRapport.Update;

                lignes.Sorted := true;
                lignes.Sort;
                redRapport.lines.add('Tri par Sort : mis : '+intToStr(chronoA.mis)+ ' ms');
                redRapport.Update;

                i := lignes.count - 1;
                repeat j:=i-1;
                       if lignes[i]=lignes[j] then lignes.delete(i);
                       dec(i);
                until i=0;
                redRapport.lines.add('Suppr doublons : mis : '+intToStr(chronoA.mis)+ ' ms');
                redRapport.Update;

                lignes.SaveToFile( NomSauverSous );

                redRapport.lines.add('Durée totale : mis : '+intToStr(chronoA.mis)+ ' ms');
                redRapport.Update;
                Application.ProcessMessages;
                // Résultats comparatifs :
                //Essais de A) à E) avec fichier de tests de 200004 lignes
                //dans tous les cas "mis" signifie temps écoulé depuis le Top-Départ
                //A) Essais avec ancienne version d'Art19 : Durée totale avec if lignes.IndexOf( s ): mis : 335918ms = 5 min 36 sec

                //B) Essais avec sorted=true et dupIgnore pour tri direct :
                // LoadFromFile : mis : 335023 ms
                // Durée totale : mis : 335332 ms = 5 min 35 sec : pas plus rapide

                //C) Essais avec sorted=false pour insertion rapide dans un 1er temps
                //puis élimination des doublons par tri avec sorted=true + dupIgnoredans
                // + méthode Sort un 2ème temps :
                // LoadFromFile : mis : 349 ms
                // Tri : mis : 4268 ms
                //Durée totale : mis : 4594 ms : rapide mais l'élimination n'a pas marché avec Sort

                //D) Essais avec insertion rapide et tri par transfert dans une
                //deuxième liste :
                // LoadFromFile : mis : 353 ms
                // Tri par transfert : mis : 333943 ms
                //Durée totale : mis : 334273 ms = 5 min 34 sec : ok mais pas plus rapide

                //E) Essais avec insertion rapide + tri par Sort puis boucle de
                //comparaison et d'élimination des doublons :
                // LoadFromFile : mis : 350 ms
                // Tri par Sort : mis : 4255 ms   (4255-350 = 3905 ms)
                // Suppr doublons : mis : 4375 ms (4375-4255 = 120 ms)
                // SaveToFile = (4706-4375 = 331 ms)
                //Durée totale : mis : 4706 ms : 4 sec 706 ms
                //soit 334273/4706 = 71 x plus rapide que les cas précédents

                //Ebis) Même essai que E mais avec fichier de tests de 250004 lignes (16.1 Mo) :
                // LoadFromFile : mis : 448 ms
                // Tri par Sort : mis : 6952 ms
                // Suppr doublons : mis : 7098 ms
                //Durée totale : mis : 15856 ms

               //Commentaires suivants ajoutés le 10 juin après essais complémentaires :

               //Eter) Même essai que E mais avec fichier de tests de 44004 lignes (2.8 Mo) :
                // LoadFromFile : mis : 73 ms
                // Tri par Sort : mis : 824 ms
                // Suppr doublons : mis : 853 ms
                //Durée totale : mis : 925 ms

                //Equat) Même essai que E mais avec remplacement du if OpenDialog1.Execute par une boucle de 100 fois le fichier de tests de 44004 lignes :
                // Durée totale : mis : 94381 ms : 1 min 57 sec
                // 100*2.8/94.381 = 2.9667 Mo/sec
          end;
end;

EDIT : Pour info : La procédure de suppression de doublons ci-dessus a encore été améliorée en termes de rapidité en novembre 2007 dans le cadre d'une autre discussion qui a viré en cours de route sur ce thême. Sa remplaçante se trouve ici : http://www.developpez.net/forums/sho...82#post2711082