Dédoubler un fichier texte rapidement

**Gilbert Geyer** · 20/11/2007, 16h31

Bonjour,

A PapyJohn : J'ai réussi à régler le Problème n°1 cité dans mon message précédent à propos de ta procédure de tri dont j'ai simplement modifié les bornes de démarrage et le bug que j'avais signalé a disparu et je l'ai encapsulée dans la procedure de suppression des doblons comme suit :

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
procedure DoublonsPapyJohn3(const nomFiSource, NomFiDest : string);
var      i, NbLignes : longint;
         L : TStringList; FS : TFileStream; ChronoB : oChrono;

         procedure Tri_3;
         var       s, sj, sl, sr, j,k: Longint;
                   Code: string;
                   Resa: string;
                   St  : array[0..5000, 0..1] of Longint;
                   
         begin S:=0; //S := 1;
               st[S, 0] := 0; //st[S, 0] := 1;
               st[S, 1] := nbLignes-1; //st[S, 1] := nbLignes;
               repeat
                  sl := st[S, 0];
                  sr := st[S, 1];
                  Dec(S);
                  repeat
                     j := sl;
                     sj:= sr;
                     Code := L[(sl + sr) shr 1];
                     repeat
                        while (L[J] < Code)  do Inc(j);
                        while (Code < L[Sj]) do Dec(sj);
                        if j <= sj then
                        begin
                          Resa := L[j];
                          L[j] := L[Sj];
                          L[Sj] := Resa;
                          Inc(j);
                          Dec(sj);
                        end;
                     until j > sj;
                     if j < sr then
                     begin
                       inc(S);
                       St[S, 0] := j;
                       St[S, 1] := sr;
                     end;
                       sr := sj;
                  until sl >= sr;
               until S < 0; //until S < 1;
         end; // Tri_3

begin    L:=TStringList.create;
         L.Sorted := FALSE;
         L.LoadFromFile(nomFiSource);

         NbLignes:=L.Count; //-1
         ChronoB.Top(frmGen.Edit1);
         //L.Sort;
         Tri_3;
         frmGen.redRapport.lines.add('Durée Tri : mis : '+intToStr(chronoB.mis)+ ' ms');
         //L.SaveToFile(NomFiDest); EXIT (< vérif qualité du tri)

         if L.Count>0 then
         begin FS := TFileStream.Create(NomFiDest, fmCreate);
               i := 0;
               FS.Write(PChar(L[i]+#13#10)^, length(L[i]+#13#10));
               for i:=0 to L.Count-2
               do if L[i]<>L[i+1] // alors directos vers disque
                  then FS.Write(PChar(L[i+1]+#13#10)^, length(L[i+1]+#13#10));
               FS.Free;
         end;
         L.Free;
end;

... et voiçi les résultats des tests comparatifs de vitesse :
1) : Avec le fichier de 10000 lignes dont une ligne sur deux est du texte aléatoire de 62 caractères et une ligne sur deux est égale à la chaîne '<<< MI-DOUBLON >>>' :
- Durée totale : mis : 259 ms avec DoublonsPapyJohn
- Durée totale : mis : 175 ms avec DoublonsPapyJohn2
- Durée totale : mis : 113 ms avec SupprDoublonsDansFI3
- avec DoublonsPapyJohn3 et tri avec Tri-3 : mis : 50 ms pour le tri dans Durée totale : mis : 105 ms
- avec DoublonsPapyJohn3 et tri avec Sort : mis : 125 ms pour le tri dans Durée totale : mis : 179 ms

2) avec fichier de 200000 lignes dont une ligne sur deux est du texte aléatoire de 62 caract et une ligne sur deux est égale à la chaîne '<<< MI-DOUBLON >>>' (8540 Ko) :
- Durée totale : mis : 410874 ms avec DoublonsPapyJohn
- Durée totale : mis : 55879 ms avec SupprDoublonsDansFI3
- Durée totale : mis : 4596 ms avec DoublonsPapyJohn2
- avec DoublonsPapyJohn3 et tri avec Tri_3 : mis : 1555 ms pour le tri dans Durée totale : mis : 2652 ms : soit 1,73 fois plus rapide que DoublonsPapyJohn2
- avec DoublonsPapyJohn3 et tri avec Sort : mis : 3495 ms pour le tri dans Durée totale : mis : 9608 ms

On constate une nette amélioration par rapport au score précédent.

Reste le problème à clarifier concernant le dimensionnement de la varaiable St : array[0..5000, 0..1] of Longint; afin que la procédure reste utilisable dans le cas de gros fichiers.
Pour l'instant j'ai remarqué que 'S' reste inférieur à 24 avec le fichier de 200000 lignes et inférieur à 30 avec un fichier similaire de 500000 lignes, mais je me demande si la valeur de 5000 resterait suffisante dans le cas des gros fichiers de Bilbo194 dont il disait en début de discussion :

...fichiers textes plutot imposants (jusqu'à plusieurs millions de lignes). Suivant le type de fichier, chaque ligne peut avoir de 10 à 200 caracteres

?????

A+

**PapyJohn** · 20/11/2007, 16h49

Maintenant que tu as mon mail envoie moi ton fichier on parlera de la même chose d'autaat plus que j'ai améliorè les perfs!!!

Ta modif dans le tri est juste: je n'utilise que des tables commençant à 1 ou plus jamais 0( je les laisses au C)
Pour ce qui est de la table ST elle sert de récursivité . Pus exactement sa taille correspond au nombre maximum de rappel dans dépilage
Plus le fichier est en désordre plus S grandit. J'ai réussi a avoir 1600 c'est pour cela quand mettent 5000 on dort tranquille
De même des longInt c'est du confort.
En usage standard 100 Integer est largement suffisant les fichiers étant rarement en permanence en désordre. Surtout les très gros

Jérôme

**Gilbert Geyer** · 20/11/2007, 17h14

Re-bonjour,

A PapyJohn :

Maintenant que tu as mon mail envoie moi ton fichier on parlera de la même chose d'autaat plus que j'ai améliorè les perfs!!!

... tu veux quel fichier ? Comme tu peux récupérer ici le Code de la procedure DoublonsPapyJohn3 avec un simple Ctrl-C je suppose que tu veux les fichiers de tests : Oui/Non ?

Plus le fichier est en désordre plus S grandit.

... j'aimerais générer un ficher où le désordre est maximal et où donc S est maximal. Quelles sont les caractéristiques d'un tel désordre pour tester dans les conditions les plus défavorables ???

En tous cas c'est déjà rassurant qu'on ne soit pas obligés de remplacer le 5000 par la valeur de nbLignes.

A+

EDIT : Plutôt que de t'envoyer les fichiers de tests tu peux récupérer dans mon message du 15/11/2007, 11h21 la procedure TfrmGen.bCreerFichierTxtAleatoireClick(Sender: TObject) avec laquelle je les génère ( on doit modifier le nombre de lignes souhaitées dans le code même).

**PapyJohn** · 20/11/2007, 22h09

En réalité le fonctionnement d'un QS est le fait de deplacer des elements éloignes les uns des autres
Aussi si les déplacements sont courts la tri risque de ramer et c'est cela qui t'inverse non?

donc 21 43 65 87 10 9 12 11 me semble pas mal (tu tries et tu poermutes I et I+1;

J'ai remarque aussi qu'il n'aimait pas les fichiers duplique: deux fois les meme
1
2
4
6
1
2
4
6

De toutes façons j'ai trouve une méthode élégante ,rapide et économique en mémoire pour gérer ST: je te laisse chercher un peu..

Oui les fichiers dont j'ai besoin ce son les <<< MY DOUBLON >>> et consorts
mais si tu n'es pas gentil j'optimise ton code!!!!

PapyJohn

**Gilbert Geyer** · 21/11/2007, 12h28

Bonjour,

A PapyJohn :

En réalité le fonctionnement d'un QS est le fait de deplacer des elements éloignes les uns des autres Aussi si les déplacements sont courts la tri risque de ramer et c'est cela qui t'inverse non?

... depuis que j'ai rectifié les bornes de démarrage du tri comme suit:

Code :

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

1
2
3
4
 
               S:=0; //S := 1;
               st[S, 0] := 0; //st[S, 0] := 1;
               st[S, 1] := nbLignes-1; //st[S, 1] := nbLignes;

le résultat du tri est correct.

J'ai remarque aussi qu'il n'aimait pas les fichiers duplique: deux fois les meme

... quand tu dis "il n'aimait pas" cela signifie quoi ? Que cela augmente la valeur prise par S dans st[S, 0] et st[S, 1] ?

De toutes façons j'ai trouve une méthode élégante ,rapide et économique en mémoire pour gérer ST: je te laisse chercher un peu..

... inutile de chercher, comme un bon sommeil porte conseil, j'avais eu l'idée de virer ST[] pour gérer la récusivité par des appels récursifs en revenant à un QuikSort conventionnel mais en évitant d'y utiliser CompareStr() qui rame et dont on n'a nullement besoin ici puisque l'objectif dans la suppression des doublons n'est pas réellement de trier dans un croissant ou décroissant mais de regrouper le chaines qui forment des doublons. Un algo rapide qui produirait ces regroupements comme suit suffirait:

Code :

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

En fait l'idée de revenir à un QuikSort conventionnel m'est venue surtout pour régler le problème concernant le pré-dimensionnement de var St : array[0..5000, 0..1] of Longint car je crains que dans certains cas 'S' pourrait prendre une valeur supérieure à 5000.

Oui les fichiers dont j'ai besoin ce son les <<< MY DOUBLON >>> et consorts

... pour l'instant je viens de t'envoyer par mail un Zip qui contient le fichier ProcCreerFichierTest.txt que tu pourras copier-coller dans ton unité : c'est la procédure avec laquelle je créé les fichiers <<< MI-DOUBLON >>> avec le nombre de lignes souhaité.
... mais qu'entends-tu par "et consorts" ?

mais si tu n'es pas gentil j'optimise ton code!!!!

... Super! Si je comprends bien suffit de ne pas être gentil avec toi et hop tu fais le boulot à ma place!.

A+

**PapyJohn** · 21/11/2007, 12h48

Je vois que tu es comme mes fils un bon sommeil et papa donnera la solution (mes fils sont d'horribles informaticiens)

Voici donc une solution élégante :

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
Procedure Tri;
var St:array of integer;
     TailleSt : integer
begin
TailleSt :=100;
Seet lengh(St, TailleSt - sizeof(integer))
 
 ..
..
..
 
if S= TailleSt then
begin
 TailleSt :=TailleSt +100;   // ou 1000 
 Set lengh(St, TailleSt - sizeof(integer))
end;

Et là tu n'occuperas que la mémoire dont tu as réellement besoin.
Élégant et efficace non ?

Quand je dis que le tri n'aime pas c'est de fait que S part en vrille et que la table ST explose. Mais c'était avant la table dynamique.

Papy john

**Gilbert Geyer** · 21/11/2007, 14h32

Bonjour,

A PapyJohn :

mes fils sont d'horribles informaticiens

Bigre, toute une famille d'informaticiens! Cela doit être sympa.

A propos de var St:array of integer : en fait tu fais une sorte de "Grow" en augementant la taille par tranches de 100 ou de 1000 avec des SetLength pour éviter le ralentissements dûs à des SetLength trop répétitifs.
Effectivement c'est efficace et ça n'occupera que la mémoire dont on a réellement besoin. Reste plus qu'à ajouter :

Code :

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

1
2
3
4
5
 
    if memViveDispo<TailleTranche then
    begin  ShowMessage('Le traitement de ce fichier nécessite davantage de mem-vive-dispo' );
           EXIT;
    end;

Lorsque j'avais fait un essai avec St : array[0..200000, 0..1] of Longint j'ai dépassé le seuil de ma mem-Vive-Disponible.

Quand je dis que le tri n'aime pas c'est de fait que S part en vrille et que la table ST explose . Mais c'était avant la table dynamique

... ok, moi je pensais que S partait en vrille dans le cas où le fichier-source se trouve d'origine à peu près classé dans l'ordre inverse à celui produit par la procédure de tri utilisée et beaucoup moins dans le cas de "fichiers dupliqués".
... ça me donne envie de faire des tests avec de fichiers dupliqués et des fichiers pré-classés dans l'ordre inverse pour suivre l'évolution de S.

L'avantage de ta solution pour ST c'est, en plus de ce qui a déjà été dit, quelle permet d'envoyer aisément le ShowMessage d'avertissement précité.
Alors que si je vire carrément la table ST pour utiliser un QuickSort où la récursivité est gérée par simples appels à elle même on gagne carrément la mémoire utilisée par ST et l'utilisateur est averti du dépassement de mem-vive-dispo par un simple plantage.

A+

**PapyJohn** · 21/11/2007, 15h15

Ou tu commes une erreur ou nous n'avons pas les mimes sources du Quick Sort
Le mien est recurssif. Ou bien alors je n'ai rien compris!

Pour la famille que des pas triste
3 fils: un ingenieur en architecture Microprocesseur, un Technicien sup (BTS+DUT, et un autre responsable d'un parc de 150 machines)
Quand j'étais jeune les filles nous écoutaient parler moto
a la maisoin on parle IP,Protocole, cycles... Ma pauvre fille a été obligée de s'y mettre.
je te racontes pas les descentes de la cuber police à la maison pour fouiller mes disques durs. Magic Windows (un de mes fils, ancien assembleur) leur a explique Windows! Un instant mémorable!
Quand il ont découverts l'armoire avec les HD ils ont palis.

Si cela intéresse du monde je pourrais vous faire un topo un jour sur les techniques que j'ai vu sur les recherche de MP3 sur un 250 GIGA cela amuse.
(j'ai eu droit a 3 descentes en 1 an et rien trouve bien sur! Champion du Monde!!!)

**Gilbert Geyer** · 21/11/2007, 17h24

Re-bonjour,

A PapyJohn :

Ou tu commes une erreur ou nous n'avons pas les mimes sources du Quick Sort
Le mien est recurssif. Ou bien alors je n'ai rien compris!

... tu gères la récursivité via la var ST alors qu'on peut également gérer la résursivité avec une procédure à l'intérieur de laquelle celle-ci s'appelle elle même. Voiçi le QuikSort que je viens d'utiliser pour éviter l'utilisation de ST c'est justement une variante de ce type dans la quelle QuickSortRec() s'appelle elle-même :

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
 
procedure QuickSortB( var SL: TStringList; sens2tri : boolean);
 
   procedure QuickSortRec( var SL: TStringList; lDeb,lFin: Integer);
 
             procedure PermuterLignes(li1,li2: Integer);
             var       s: string;
             begin     s:= SL[li1]; SL[li1]:= SL[li2]; SL[li2]:= s; end;
 
   var       Lo, Hi, Mi: Integer;
   begin     Lo := lDeb;
             Hi := lFin;
             Mi := (lDeb + lFin) shr 1;
             repeat
                 if sens2tri then // tri ordre croissant
                 begin while SL[Lo]<SL[Mi] do Inc(Lo);
                       while SL[Hi]>SL[Mi] do Dec(Hi);
                 end else // tri ordre décroissant
                 begin while SL[Lo]>SL[Mi] do Inc(Lo);
                       while SL[Hi]<SL[Mi] do Dec(Hi);
                 end;
                 if Lo <= Hi then
                 begin
                      PermuterLignes(Lo, Hi);
                      if Mi = Lo then Mi := Hi
                      else if Mi = Hi then Mi := Lo;
                      Inc(Lo);
                      Dec(Hi);
                 end;
             until Lo > Hi;
             if Hi > lDeb then QuickSortRec(SL, lDeb, Hi); //< ici les appels récursifs
             if Lo < lFin then QuickSortRec(SL, Lo, lFin); //< ici les appels récursifs
 
   end;
begin
             QuickSortRec(SL, 0, SL.count-1);
end;

... mais manque de chance ce QuickSort est environ deux fois plus lent que le tien sinon il nous aurait permis de se passer de la var ST.

a la maisoin on parle IP,Protocole, cycles... Ma pauvre fille a été obligée de s'y mettre.

... je la plains.

je te racontes pas les descentes de la cuber police à la maison pour fouiller mes disques durs. Magic Windows (un de mes fils, ancien assembleur) leur a explique Windows! Un instant mémorable!
Quand il ont découverts l'armoire avec les HD ils ont palis...

... cela a effectivement dû être mémomarable car ils ont essentiellement une formation d'utilisateurs mais ils sont encadrés ou conseillés par des informaticiens professionnels.

j'ai eu droit a 3 descentes en 1 an et rien trouve bien sur!

... Bigre! Et ils espéraient trouver quoi dans tes HD ?

Pour en revenir à notre problème de doublons j'ai fait un test avec un fichier de 1000 lignes dont la deuxième moité était le duplication de la première moitié et S a seulement atteint la valeur Smax=3, je m'attendais à Smax=500.

Ensuite j'ai fait un essai avec un fichier de 26 lignes de 'Z' à 'A' c'est à dire l'inverse de l'ordre alphabétique et l'inverse du résultat que produit ta procédure de tri : alors que je m'attendais à Smax=13 j'ai eu Smax=1.

Donc, comment as-tu fait pour que "S parte en vrille et que la table ST explose" comme tu disais l'autre fois ?

A+

**PapyJohn** · 21/11/2007, 19h41

je ne suis servi de mon fichier Sodoku que j'ai merger sur lui même
et c'est là que j'ai souffert
Je regarde ton tri mais a première vu il est récursif !
J'ai ecrit un petit cours dessus tu vas etre mon premier lecteur.
PapyJohn

**Gilbert Geyer** · 22/11/2007, 11h21

Bonjour,

A PapyJohn :

je ne suis servi de mon fichier Sodoku que j'ai merger sur lui même et c'est là que j'ai souffert

... ok je vais faire pareil et faire afficher la valeur de Smax ... en espérant que j'ai suffisamment de mem-vive-dispo pour les 2 x 362880 lignes.

Je regarde ton tri mais a première vu il est récursif !

... sûr qu'il est récursif, par contre je n'arrive pas à piger pourquoi il est deux fois lent que le tien ???.

J'ai ecrit un petit cours dessus tu vas etre mon premier lecteur.

... ok, mais pour être ce lecteur faudrait que j'aie ce cours.

A+

**PapyJohn** · 22/11/2007, 11h50

... ok, mais pour être ce lecteur faudrait que j'aie ce cours

Je ke fais ire pour supprimer les fautes et les sottises(j'ai des fils sous la main)
et je t'envoies le PDF qui justement se sert du QuickSort pour expliquer la diffeence de perf
C'est a mon avbis tres simple à comprendre.
PapyJohn

**Gilbert Geyer** · 22/11/2007, 14h00

Re-bonjour,

A PapyJohn : A propos des différences de perf sur tris: En voulant tester Sudoku2.txt suite au merge de Sudoku je me suis rendu compte que j'avais oublié de placer en commentaire la ligne de commande de ta routine de tri ce qui fait que le temps mesuré était en fait la somme du temps mis par les deux routines : J'ai donc refait les tests et voiçi les résultats:

1) Tri seul avec le fichier "mi-doublons" de 10 000 lignes:
- L.Sort : mis : 125 ms
- Tri_3 : mis : 50 ms
- Avec QuickSortB(L,True) : mis : 56 ms : à peu près kif-kif

2) Tri seul avec le fichier "mi-doublons" de 200 000 lignes:
- L.Sort : Durée Tri : mis : 3480 ms
- Tri_3 : Durée Tri : mis : 1110 ms
- Avec QuickSortB(L,True) : Durée Tri : mis : 2136 ms : deux fois plus lent ???
Conclusion : pour améliorer le score actuel pour la suppression des doublons faudrait trouver une routine de tri encore plus rapide que la tienne.

B) Tests avec Sudoku2.txt = merge de Sudoku avec ta routine de Tri : tu disais "je me suis servi de mon fichier Sodoku que j'ai merger sur lui même et c'est là que j'ai souffert"
... j'ai commencé à comprendre ta souffrance quand j'ai vu tourner la pendule et au bout de 9 minutes j'ai eu le msg-d'erreur "Violation d'accès à ..." sans avoir eu la valeur de Smax.
... j'ai recommencé la manip en plaçant ClipBoard.AsText := intToStr(sMax) dans la boucle et au bout de 10 minutes même msg-d'erreur mais avec Ctrl+V j'ai eu Smax=715753 !!!!!!!!!! d'où l'intérêt de ton "grow".

C)

je t'envoies le PDF qui justement se sert du QuickSort pour expliquer la diffeence de perf

... ok et merci.

A+

**PapyJohn** · 22/11/2007, 16h44

Tu as tout a fait raison quand tu constate que plus le fichier devient gros plus il est judicieux de mettre le sort a salse. J'explique

En réalité quand t arrives devant ton fichier tu as deux traitements qui doivent avoir lieu: le chargement et le tri
Le but est de trouve le meilleur chargement et le meilleur tri afin de les combiner. Le problème est que les deux meilleurs solutions sont incompatibles: tu peux avoir le meilleur chargement mais pas le meilleur tri et viis versa.
Pourquoi?
Il suffit de regarder comment cela se passe: lors d'un load l'ordinateur fait un seul read puis découpe le string en lignes
Il regarde si dans sa liste en sortie la ligne est déjà présente:
il utilise pour cela une recherche dycho de bonne facture

La constitution de cette liste ne pose pas beaucoup de problème au niveau des trainements mais devient vite pénalisante quand les insertions des nouveaux éléments sont en tête de liste

si on a déjà 100000 strings et qu'il faille intercaler le nouveau en tete il faudra préalablement déplacer les 100000 premiers pour recopier le nouveau
Et donc plus le fichier en entrée est mélangé plus les insertions sont nombreuses: si le fichier est déjà trié alors la l'insertion se fait toujours à la fin sans avoir besoin de décaler de lignes

Maintenant si on a pas le sort automatique
La c'est le cas optimum vu plus haut un seul read, découpage en ligne et ajout à la fin.
Dans le premier cas le fichier est prêt à être travailler dans le second il fat le tier.
Quelque soit le tri utilisé le temps sera variable et parfois énorme. On peut améliorer le tri mais il y aura toujours des cas ou le temps augmentera

Donc si nous lisons rapidement le fichier il faut le trier et cela peut prendre beaucoup de temps
Si nous le lisons en le triant l'opération peut aussi prendre beaucoup de temps

La conclusion est qu'il n'y a pas de solution universelle, que quelque soit la rapidité, la facilité ou que sais-je du code la décision reste au programmeur qui en fonction du cas auquel il est confronté choisira telle ou telle solution.
car lui seul sait si son fichier arrive déjà trier ou non.
On peut sans trop de difficultés améliorer le tri nous l'avons vu il est aussi possible d'améliorer le chargement je l'ai fais. Le gain sur le tri semblant polus important.

Pour finir je le crois avec ce problème il reste à voir le problème des doublons
Si on effectue un chargement avec le tri actif c'est indiscutable il faut mettre le duplicatas a dupignore. Le traitement est gratuit au niveau informatique le test étant fait automatiquement
Si par contre le chargement se fait non trier il est impeatif de trier avant ( comme,; pour le chargement automatique)
Puis il faut supprimer les doublons.

Mais la il n'y a pas de méthode dans l'objet . Il faut repasser par une procédure save et load et on recharge la liste triée.
D'ou l'idée d'écrire une méthode universelle: je prose mon implementation comme base de départ. Elle n'est pas universelle mais je crois que mon approche est la bonne (jusqu'à se que l'on en trouve une meilleure)
Je crois qu'un test par ligne et un déplacement me semble le mieux que l'on puisse obtenir. Mais le génie humain est sans limlite...
on compte sur vous...

Si l'amélioration (en vitesse) du loadfromfile(même pour les petits fichiers) interessent du monde je propose d'ouvrir un nouveau sujet celui ci me parraissant déjà volumineux

PapyJohn

**Gilbert Geyer** · 22/11/2007, 17h20

Re-bonjour,

A PapyJohn :

il utilise pour cela une recherche dycho de bonne facture

... elle est peut être de bonne facture mais elle est en plus ralentie du fait qu'au lieu de faire une comparaison directe des chaines du type if string1>string2 elle utilise une fonction qui tient compte des différences dues a la présence éventuelle de caractères accentués.

Pour ce qui est de la suite de ton dernier message : R.a.s globalement d'accord.

Juste un petit chipotage : Tu dis "Puis il faut supprimer les doublons" : en fait dans la procedure DoublonsPapyJohn3(const nomFiSource, NomFiDest : string) on ne supprime absolument pas les doublons de la liste puisque pour aller plus vite on les ignore snobément en renvoyant directos et illico sur le disque les lignes qui ne forment pas de doublon.

A+

**PapyJohn** · 22/11/2007, 17h42

Mais le resultat est bon tu as le bon nombre dans nbLignes
Comme tu me chipotes des octets tu remplaces L par une table dynamique comme st et tu ajuste sa taille dans doublons! Na!
PapyJohn

**Gilbert Geyer** · 23/11/2007, 11h30

Bonjour,

A PapyJohn :

Mais le resultat est bon tu as le bon nombre dans nbLignes

... Ben oui on sait que le résultat est bon. J'ai pas dit que le résultat est mauvais puisque pour qu'il soit simultanément bon et rapide on ignore les doublons au lieu de les "Deleter".

Comme tu me chipotes des octets tu remplaces L par une table dynamique comme st et tu ajuste sa taille dans doublons!

... ça n'y changerait pas énormément l'économie d'octets vu que l'occupation de la mémoire passe par son maxima avant de faire le SetLength qui tronquerait la fin de la liste.

Par contre je vais essayer d'adapter à la suppression des doublons une routine de tri que j'ai retouvée dans mes oubliettes et dont je me souviens qu'elle était très speed dans certaines circonstances ... mais avant de faire mon cocorico faut que je m'y mette pour l'adapter et la tester.

A+

**PapyJohn** · 23/11/2007, 12h39

Ce qu'il faut voir dans le cas des doublons c'est qu'il n'y a aucune allocation memoire on se sert de la table en entrée et on la raccourcie quand il y a doublons En réalité on ne reajuste a table qu'une fois
i/e Comment fonctionne le setlength

Allocation d'une nouvelle zone de memoiire de la taille voule
Recopie de la première table dans la seconde en se servant de la tille de la nouvelle comme maxi et l'on recopie

C'est exactement ce que fait un add ou un delete dans un TStringList
la tabedes strings est elle aussi declarée en dynamique (d'où la présence de grow)

Comme toi j'ai cherche a modifier les doublons dans le trei mais je n'ai reussi dans aucun

La bonne approche pour les doublons dans le tri semble etre celle qui consiste a remplacer les doublons par HigthValue et de laisser le tri le mettre à la fin
Mais je n'ai pas trouve de tri connu qui le supporte
Tu seras peut etre plus chanceux que moi
PapyJohn

**Gilbert Geyer** · 23/11/2007, 14h56

Re-bonjour,

Globalement d'accord avec ton message.

Entre-temps j'ai adapté ma routine de Tri que j'avais retrouvée dans mes oubliettes pour voir ce qu'elle donne dans le contexte de la suppression de doublons.

Voiçi les résultats comparatifs :

1) Avec le fichier "mi-doublons" de 10000 lignes :
- avec DoublonsPapyJohn3 et tri avec Tri-3 : 50 ms pour le tri dans Durée totale : 362 ms
- avec IgnoreDoublonsASort : Durée Tri : 56 ms Durée totale : 103 ms soit 3,51 fois plus rapide mais on s'en fout puisqu'il s'agit d'un "petit fichier"

2) Avec le fichier "mi-doublons" de 200000 lignes :
- avec DoublonsPapyJohn3 et tri avec Tri_3 : mis : 1555 ms pour le tri dans Durée totale : 2652 ms
- avec IgnoreDoublonsASort : Durée Tri : 1521 ms Durée totale : 2493 ms soit 1,06 fois plus rapide donc le gain n'est pas énorme dans le cas de fichiers plus gros.
Par contre il reste peut-être un truc à améliorer dans IgnoreDoublonsASort pour le gain de speed ... à voir.

... du coup je n'ai pas posté le code de IgnoreDoublonsASort et de la méthode de tri mais s'ils t'intéressent dis moi le et je le mettrai ici (la méthode de tri en question renvoie, à la demande, soit la liste triée, soit simplement un array qui contient l'ordre suivant lequel il faut parcourir la liste pour la voir dans l'ordre triée).

Par ailleurs j'espère que t'auras des réponses intéresantes dans la discussion que tu as lancée pour l'utilisation de l'Asm dans le contexte de la surpession de doublons.

A+

**Gilbert Geyer** · 27/11/2007, 12h08

Bonjour,

A PapyJohn : Voiçi la version rectifiée de la procédure de suppression des doublons tenant compte de la nécessité de faire croître la taille de la table ST pour le cas de fichiers dupliqués entièrement sur eux-même où la valeur de S peut dépasser allègrement la valeur des 5000 :

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
 
procedure DoublonsPapyJohn3bis(const nomFiSource, NomFiDest : string);
var      i, NbLignes : longint;
         L : TStringList; FS : TFileStream; //ChronoB : oChrono; < chronomètre
 
         procedure Tri_3bis;
         const     PasDuGrow = 100; //
         var       s, sj, sl, sr, j,k : Longint;
                   Code: string;
                   Resa: string;
                   TailleSt : longint;
                   St0  : array of integer; 
                   St1  : array of integer;
 
         begin TailleSt :=PasDuGrow;
               SetLength(St0, TailleSt);
               SetLength(St1, TailleSt);
               S:=0;               
               St0[S]:=0;          
               St1[S]:=nbLignes-1; 
               repeat
                  sl:=St0[S]; 
                  sr:=St1[S]; 
                  Dec(S);
                  repeat
                     j := sl;
                     sj:= sr;
                     Code := L[(sl + sr) shr 1];
                     repeat
                        while (L[J] < Code)  do Inc(j);
                        while (Code < L[Sj]) do Dec(sj);
                        if j <= sj then
                        begin
                          Resa := L[j];
                          L[j] := L[Sj];
                          L[Sj] := Resa;
                          Inc(j);
                          Dec(sj);
                        end;
                     until j > sj;
                     if j < sr then
                     begin
                       inc(S);
                        if S = TailleSt then
                       begin TailleSt :=TailleSt + PasDuGrow;
                             SetLength(St0, TailleSt);
                             SetLength(St1, TailleSt);
                       end;
                       St0[S] := j;  
                       St1[S] := sr; 
                     end;
                       sr := sj;
                  until sl >= sr;
               until S < 0; 
         end; // Tri_3bis
 
begin    L:=TStringList.create;
         L.Sorted := FALSE;
         L.LoadFromFile(nomFiSource);
 
         NbLignes:=L.Count;
         //ChronoB.Top(frmGen.Edit1);
 
         Tri_3bis; 
         //frmGen.redRapport.lines.add('Durée Tri : mis : '+intToStr(chronoB.mis)+ ' ms');
         //L.SaveToFile(NomFiDest); EXIT;
 
         if L.Count>0 then
         begin FS := TFileStream.Create(NomFiDest, fmCreate);
               i := 0;
               FS.Write(PChar(L[i]+#13#10)^, length(L[i]+#13#10));
               for i:=0 to L.Count-2
               do if L[i]<>L[i+1] // alors pas doublon donc directos vers disque
                  then FS.Write(PChar(L[i+1]+#13#10)^, length(L[i+1]+#13#10));
               FS.Free;
         end;
         L.Free;
end; // DoublonsPapyJohn3bis

... j'ai pris comme valeur de PasDuGrow = 100; ce qui semble suffire dans le cas général vu qu'e j'ai constaté que S ne dépassait pas la valeur de 30 dans le cas d'un fichier "mi-doublons" de 500000 lignes.

Comme jusqu'à présent on a chaque fois comparé les performances de la dernière version à celles de la version "N-1" cette fois çi j'ai fait un test comparatif avec celles du code qui en début juin-2007 a lancé l'autre discussion sur la suppression des doublons ce qui permet de se faire une idée sur le gain de vitesse obtenu par le cumul des meilleures idées apportées par les divers participants et le résultat est éloquent :

Résultats : Avec fichier de tests de 200000 lignes dont une ligne sur deux est du texte aléatoire de 62 caractères suivis du numéro de ligne et une ligne sur deux est égale à la chaîne '<<< MI-DOUBLON >>>' (8540 Ko) :
- Durée totale : 351893 ms (5,86 min !!!) avec procédure AlgoArt7juin2007 (basé sur test de présence de doublons avec IndexOf)
- avec procédure DoublonsPapyJohn3bis et tri avec Tri_3bis : mis : 1555 ms pour le tri dans Durée totale : 2652 ms (< 3 sec) soit 133 fois plus rapide que celle de juin.

A+

EDIT Temps d'éxec valables pour Pentium III à 1,13 GHz

Dédoubler un fichier texte rapidement

Langage Delphi

Discussions similaires

Partager

Partager