Dédoubler un fichier texte rapidement

**tourlourou** · 15/11/2007, 14h18

@ PapyJohn : alors, toujours à fond ?

**PapyJohn** · 15/11/2007, 19h34

Bon pour le fichier de test je propose celui ci:
La rouine crre un fichier de 362880 strings de 9 chiffres chacn. Le ,nombre d'arrangement possible soit 9!). Je crois que l'on peut déjà s'amuser à chronométrer: a solution n'est pas arrivée du premier coup )

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 Calcul_Combi;
 var
 i1, i2, i3, i4, i5, i6, i7, i8, i9: integer;
 Stemp: string[9];
 
begin
 Totals := 0;
M:=Strinlist.create;
 Stemp := '111111111';
 for I1 := 49 to 57 do
  begin
   Stemp[1] := Chr(I1);
   for I2 := 49 to 57 do
    begin
     Stemp[2] := Chr(I2);
     if i1 <> i2 then
      for I3 := 49 to 57 do
       begin
        Stemp[3] := Chr(I3);
        if (i3 <> i1) and (i3 <> i2) then
         for I4 := 49 to 57 do
          begin
           Stemp[4] := Chr(I4);
           if (i4 <> i1) and (i4 <> i2) and (i4 <> i3) then
            for I5 := 49 to 57 do
             begin
              Stemp[5] := Chr(I5);
              if (i5 <> i1) and (i5 <> i2) and (i5 <> i3) and (i5 <> i4) then
               for I6 := 49 to 57 do
                begin
                 Stemp[6] := Chr(I6);
                 if (i6 <> i1) and (i6 <> i2) and (i6 <> i3) and
                  (i6 <> i4) and (i6 <> i5) then
                  for I7 := 49 to 57 do
                   begin
                    Stemp[7] := Chr(I7);
                    if (i7 <> i1) and (i7 <> i2) and (i7 <> i3) and
                     (i7 <> i4) and (i7 <> i5) and (i7 <> i6) then
                     for I8 := 49 to 57 do
                      begin
                       Stemp[8] := Chr(I8);
                       if (i8 <> i1) and (i8 <> i2) and (i8 <> i3) and (i8 <> i4) and
                        (i8 <> i5) and (i8 <> i6) and (i8 <> i6) and (i8 <> i7) then
                        for I9 := 49 to 57 do
                         begin
                          Stemp[9] := Chr(I9);
 
                          if (i9 <> i1) and (i9 <> i2) and (i9 <> i3) and (i9 <> i4) and
                           (i9 <> i5) and (i9 <> i6) and (i9 <> i7) and (i9 <> i8) then
                           begin
                            Totals := totals + 1;
                           M.aad(stemp);
                           end;
                         end;
                      end;
                   end;
                end;
             end;
          end;
       end;
    end;
  end;
 M.SaveTofile('Sudoku.txt');
end;

J'ai regarde les exemples: en réalité le fait de faire le blockread est plus rapide rapide que le loadfromfile MAIS on perde du temps dans le filesize:

il faut donc de très gros fichiers ou avoir la taille avant.

J'ai fini avec le tri des listes: interressant j'attaque les doublons et cela sera fini.
PapyJohn

**PapyJohn** · 16/11/2007, 11h30

Voici la routine que j'utilise pour supprimer les doublons dans une liste TRIEE
son gros avantage est quelle travaille sur elle mime sans allocation mémoire supplémentaire et manipule donc des listes de n'importe quelle taille.
ll faut juste lui indiquer le nom de la table : string, interroge, longent peu importe...Elle peut aussi travailler sur des portions de liste.
Elle supprime les doublons mais aussi les triples,quadruples....
Elle renvoie le nouveau nombre d'éléments
Il faudra attendre un peu poour les tris: il'effondre à 32700 entrées!
Et je ne sais pas pourquoi.

Pour le café la prochaine version est en négociation avec Nescafé....

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
 
function Doublons(Deb,Fin:longint): longint;
var i: Longint;
 Index: Longint;
 Taille:longint;
begin
 i := Deb;
 Index := Deb;
 Taille:=Sizeof(L[1]);
 repeat
   if L[i]<>L[i+1] then
     begin
      Inc(Index);
      Move(L[i+1],L[index],10);
     end;
   inc(i);
 until i >= Fin;
 Doublons := Index;
end;

**Gilbert Geyer** · 16/11/2007, 11h58

Bonjour,

A PapyJohn

1)

il faut donc ... ou avoir la taille avant.

... en fait avec un TFileStream on a à la fois la rapidité et la taille dans sa propriété FS.size et la lecture d'une propriété c'est quasi instantané (c'est pas pour rien qu'on utilise les FileStream lorsqu'on a de très gros fichiers qui ne tiennent pas entièrement en mem-vive) :

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
 
procedure SupprDoublonsDansFI3(const nomFiSource, NomFiDest : string); //****
//        avec tFileStream et TXT vers lignes.text
var       lignes : TStringList; FS : tFileStream; TXT : string;
begin     lignes := TStringList.Create;
          lignes.Sorted := TRUE;
          lignes.Duplicates:=DupIgnore;
          FS := TFileStream.Create(nomFiSource, fmOpenRead);
          FS.Position:=0;
          try SetLength(TXT,FS.Size);
              //SetLength(lignes.Text,FS.Size); <refusé par le compilo [Erreur] uLectureMegaFichier.pas(1401): Un objet constante ne peut être passé comme paramètre Var
              FS.Read(Pchar(TXT)^,FS.Size);
              //FS.Read(Pchar(lignes.Text)^,FS.Size); < syntaxe acceptée par le compilo
              lignes.Text:=TXT;
              lignes.SaveToFile( NomFiDest );
          finally
              lignes.free;
              FS.Free;
          end;
end;

... et dommage que le compilo n'accepte pas la ligne SetLength(lignes.Text,FS.Size); car cela aurait permis d'éviter le recours à la variable intermédiaire TXT et de gagner le temps pris par le transfert d'affectation de l'instruction "lignes.Text:=TXT".

2) Avec SupprDoublonsDansFI3 et votre 'Sudoku.txt' de 362880 strings de 9 chiffres le temps d'exec descend chez moi à Durée totale : mis : 4353 ms (Pentium III à 1,13 GHz) mais ce résultat est trompeur :
- d'abord car Sudoku.txt ne contient aucun doublon à supprimer or ce sont les suppressions qui demandent à Delphi de réorganiser la StringList ce qui prend du temps,
- et car des strings de seulement 9 chiffres c'est peu représentatif.
Dans son premier message que je viens de relire (et que j'avais complètement oublié) Bilbo194 a écrit

"Suivant le type de fichier, chaque ligne peut avoir de 10 à 200 caracteres".

... donc il faudrait que nos fichiers de tests soient représentifs de l'utilisation envisagée donc ni 9 chiffres ni 62 caractères mais en moyenne (10 + 200)/2 = 105.

Faudrait donc qu'on mette d'abord au point le code de génération du fichier de tests (nombre de caractères par lignes, proprotion de doublons, etc) et surtout une idée nouvelle pour améliorer le score de la supression de doublons.

A+

EDIT : J'avais pas remarqué que PapyJohn a intercalé un nouveau message pendant que je rédigais le mien

**Gilbert Geyer** · 16/11/2007, 12h46

Re-Bonjour,

A PapyJohn : J'ai voulu tester votre function Doublons(Deb,Fin:longint): longint; mais avec la variable "var L : TStringList;" le compilo me tousse un message d'erreur à la ligne suivante:

Code :

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

1
2
 
             Move(L[i+1],L[index],10); <[Erreur] uLectureMegaFichier.pas(1614): Variable requise

... ??????????
... de plus le principe même d'utiliser move m'intrigue car même si le compilo acceptait je me demande comment cela supprimerait les doublons en les déplacant ?

A+

**PapyJohn** · 16/11/2007, 14h32

L'erreurque tu rencontre est du au fait que L (la liste) est un objet
C'est unde des raisons pour lesquels je rechine à les uilisé pour autre chose que l'affichage. Quand tu travaille à la main tu as plein de routines interdites

Ma Liste est definie par

L: array[1..40000] of string[9];

Bien sur on peut mettre une array dynamique!!!
Si tu gardes a TStringList tu remplaces simplement la lignes par
L[index]:= L[i+1]; et c'est tout

Le move va un peu plus vite: il y en a mime des versons de course:
le move est généraliste tu peux toujours le simplifier au cas par cas.

J'avais revenu on va chatouiller les cycles....

J'explique la routine de doublons:

soi une liste 1,2,2,3,12,12 et y on veut 1.2.3.12
donc on se sert de la table en entree et de DEUX index I et index

Maintenant tu regardes si la valeur suivante est la mime
donc le 1 et le 2 différent donc rien ne bouge incrément de l'index de balayage
on compare 2 et 2 c'est égal je n'incrémente que le balayage puisse que j'ai déjà
je compare donc le 2 et le 3 différents donc je remplace évincement mon index de sauvegarde je recopie dedans le 3

ma table est donc devient 1,2,3 et je pointe sur le 3 comparaison avec 12 différent donc recopie 1,2,3,12

je compare 12 et 12 rien
et j'ai fini mon index de recopie me dit combine il me reste d'éléments
Un seul balayage , les données déplacées une seule fois et tous les doubles supprimés techniquement je crois que c'est le mieux que l'on puisse imaginer
Un test ,un morve, 1 ou 2 incréments même en ASM je ne vois pas une autre logique qui supprime des instructions
L'avantage du MOVE est qu'il travaille sur la mémoire sans se soucier du type de variable contenues.

Peut être en regroupant les move en cas d'éléments différents; pour en réduire le nombre?

Papy qui rencontre un gros problème de performance; jusqu'à 350 000 éléments pas de souci au delà la cata!

Papy

**Gilbert Geyer** · 16/11/2007, 16h28

Re-bonjour,

A PapyJohn : vu ça marche... j'ai gardé la TStringList en remplaçant la ligne par L[index]:= L[i+1]; :

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
 
var      L : TStringList;
 
function DoublonsPapyJohn(Deb,Fin:longint): longint;
var      i, Index : longint;
         //Taille : longint;
begin    i := Deb;
         Index := Deb;
         //Taille:=Sizeof(L[1]);
         L.Sorted:=FALSE; // sinon L[index]:= L[i+1]; non accepté
         repeat
            if L[i]<>L[i+1] then
            begin
               Inc(Index);
               //Move(L[i+1],L[index],10); <[Erreur] uLectureMegaFichier.pas(1614): Variable requise
               L[index]:= L[i+1];
            end;
            inc(i);
         until i >= Fin;
         DoublonsPapyJohn := Index;
end;
 
procedure TfrmGen.bAlgo2PapyJohnClick(Sender: TObject);
var       NomCourtFichier, NomLongFichierOrig, RepAppli : string; chronoA : oChrono;
          NomSauverSous : string; pop : Integer;
begin
          L:=TStringList.create;
 
          RepAppli:=ExtractFilePath(Application.ExeName);
          OpenDialog1.InitialDir := RepAppli;
          OpenDialog1.Filter:= 'Fichiers Texte (*.txt)|*.TXT';
          if OpenDialog1.Execute then
          begin
                Application.ProcessMessages;
                ChronoA.Top(frmGen.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;
 
                L.Text:='';
                L.Sorted := TRUE;
                L.LoadFromFile(NomLongFichierOrig);
                DoublonsPapyJohn(0,L.count-1);
                L.SaveToFile( NomSauverSous );
 
                redRapport.lines.add('Durée totale : mis : '+intToStr(chronoA.mis)+ ' ms');
                end;
end;

Résultats :
1) avec un 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 : 110 ms avec DoublonsPapyJohn
- Durée totale : mis : 113 ms avec SupprDoublonsDansFI3 à peu près kif-kif.

2) avec fichier de 200000 lignes dont une ligne sur deux est du texte aléatoire de 62 car et une ligne sur deux est égale à la chaîne '<<< MI-DOUBLON >>>' (8540 Ko) :
- Durée totale : mis : 62753 ms avec DoublonsPapyJohn
- Durée totale : mis : 55879 ms avec SupprDoublonsDansFI3 un peu plus rapide.

3) avec fichier sudoku.txt, de 362880 lignes de 9 caractères, sans doublon :
- Durée totale : mis : 4419 ms avec DoublonsPapyJohn
- Durée totale : mis : 4348 ms avec SupprDoublonsDansFI3 à peu près kif-kif.

J'ai pas encore testé avec un array dynamique

Papy qui rencontre un gros problème de performance; jusqu'à 350 000 éléments pas de souci au delà la cata!

... c'est peut-être que la mem-vive-disponible arrive à saturation ?

A+

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

Desole erreur

**Gilbert Geyer** · 17/11/2007, 11h23

Bonjour,

A PapyJohn

Hier j'ai dit un peu trop rapidement "vu ça marche... j'ai gardé la TStringList en remplaçant la ligne par L[index]:= L[i+1];"
Aujourd'hui en ajoutant des showMessage(intToStr(L.count)); je me suis rendu compte que le nombre de lignes était le même en entrée et en sortie de votre fonction ce qui signifie que les doublons avaient été supprimés par le LoadFromFile:

Code :

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

1
2
3
4
5
6
7
 
                L.Sorted := TRUE;
                L.LoadFromFile(NomLongFichierOrig);
                showMessage(intToStr(L.count));
                DoublonsPapyJohn(0,L.count-1);
                showMessage(intToStr(L.count));
                L.SaveToFile( NomSauverSous );

... ce qui signifie également que L.Duplicates est par défaut égal à DupIgnore puisque les doublons avaient disparu.
... j'ai donc modifié ce passage comme suit :

Code :

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

1
2
3
4
5
6
7
8
 
                L.Sorted := TRUE;
                L.Duplicates:=DupAccept;
                L.LoadFromFile(NomLongFichierOrig);
                showMessage(intToStr(L.count));
                DoublonsPapyJohn(0,L.count-1);
                showMessage(intToStr(L.count));
                L.SaveToFile( NomSauverSous );

... et en examinant le fichier du résultat il apparaît que l'instruction L[index]:= L[i+1];" remplace les doublons originaux par des doublons formés par des lignes originales qui n'en étaient pas.

... comme dans le fichier-de-tests une ligne sur deux constituait un mi-doublon, le fichier-résultat comporte maintenant dans sa première moitié les lignes de texte aléatoire et dans sa deuxième moitié leur copie qui remplace les mi-doublons originaux mais qui forment des doublons avec la première moitié du fichier-résulat. Dommage...

A+

**PapyJohn** · 17/11/2007, 18h50

Je crois que l'erreur est dans le test de contrôle
En réalité JE NE MODIFIE pas le court: je le retourne seulement
car je ne me sers pas de TlistStrung mais d'unbe
warrant [1..40000] lof string de 10

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
 
function Doublons(Deb,Fin:longint): longint;
var i: Longint;
 Index: Longint;
begin
 i := Deb;
 Index := Deb;
 repeat
   if L[i]<>L[i+1] then
     begin
      Inc(Index);
      L[index]:=L[i+1];
     end;
   inc(i);
 until i >= Fin;
 Doublons := Index;
end;

Je supprime les éléments en double et je dis combien sont unique
L pourrai être une array s'interroge , de réal ou tout autre chose
la routine effacerait les doublons mais laisse toujours la table dans son intégralité

En fouillant bien la classe j'ai découvert du'i n'y a pas de méthode pour supprimer le doublons pour nettoyer un table par exemple
Exempe:

Code :

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

1
2
for i:=1 to 10000 do
  M.add(IntTosStr(Random de 5000));

j'ai donc 10000 entrées mais comme mon plafond était à 5000 j'ai forcement de doubles. Et bien je n'ai aucun aucun moyen de les supprimer:
je peux modifier les méthodes , retrier la liste rien n'y fera mes doublons restent

Il existe une seule de solution le savetostream ou savetofile avec le load derriere

De fait la gestion des doublons et de 'duplicate' ne sont que dans la méthode add pas dans le sort
Et quand on fait un loadfromfile il lit le fichier ligne par ligne et qu'il ADD chaque ligne c'est à ce moment la et uniquement celui la qu'il vérifie(par une recherche dico) si la ligne est en double et s'il doit l'integrer

En réalité il n'y a pas de tri au chargement il construit une liste triée par insertion si sort est à true autrement il fait un ajout à la fin.

Ce n'est pas tout a fait vrai sur le lecture ligne par ligne: il lit l'intégralité dans les TEXT puis recoupe en lignes. Autant pour moi on ne gagne rien en lisant dans d'un bloc s'est déjà se qu'il fait

J'ai commis aussi une erreur sur les indexof en l'accusant de mille maux. En lisant la doc il est bien précisé que c'est pour les listes non triées pour les triées il faut utiliser FIND. Désole de cette fausse info.

Mais il est vrai que l'on peut toujours trier la liste en local pour accélérer les recherches.

Mais j'ai l'impression que les méthodes ne sont pas celles que j'avais vu il y a quelques années il se pourrait bien que lors d'une mise à jour les classes.pas
aient été modifiées (peut etr(e lors du poassage de D5 à D6 cela fait tellement longtemps.
PapyJohn

**Gilbert Geyer** · 18/11/2007, 13h03

Bonjour,

A PapyJohn :

I) Suppression de doublons : En fait pour utiliser votre fonction avec une StringList de sorte qu'elle supprime non seulement les doublons d'origine mais également ceux qu'elle génère on est obligé de ne retenir que la partie située entre le début et la ligne correspondant à la valeur prise par "Index" :

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
function DoublonsPapyJohn(Deb,Fin:longint): longint;
var      i, Index : longint;
begin    i := Deb;
         Index := Deb;
         L.Sorted:=FALSE; // sinon L[index]:= L[i+1]; non accepté par compilo
         repeat
            if L[i]<>L[i+1] then
            begin
               Inc(Index);
               L[index]:= L[i+1];
            end;
            inc(i);
         until i >= Fin;
         DoublonsPapyJohn := Index;
         for i:=L.count-1 downto Index+1 do L.Delete(i); //< pourrait être remplacé par SetLength(L,index); dans le cas où L serait un Array of string
end;

// et pour l'appel de la fonction :
         L:=TStringList.create;
         L.Sorted := TRUE;
         L.Duplicates:=DupAccept;
         L.LoadFromFile(NomLongFichierOrig);
         DoublonsPapyJohn(0,L.count-1);
         L.SaveToFile( NomSauverSous );

... avantage résultant : le fichier-résultat est effectivement débarassé des doublons.
... inconvénient : cela ralentit considérablement la manip :
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 : 113 ms avec SupprDoublonsDansFI3 : 2,29 fois plus rapide.

2) avec le fichier de 200000 lignes dont une ligne sur deux est du texte aléatoire de 62 car 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 : 7,35 fois plus rapide.

... et on constate en plus que le gain de vitesse avec SupprDoublonsDansFI3 augmente lorsque le nombre de doublons à supprimer augmente.

II) IndexOf : En fait voiçi le code de TStringList.IndexOf standard qui utilise Find lorsque Sorted est à True :

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
 
function TStringList.Find(const S: string; var Index: Integer): Boolean;
var
  L, H, I, C: Integer;
begin
  Result := False;
  L := 0;
  H := FCount - 1;
  while L <= H do
  begin
    I := (L + H) shr 1;
    C := CompareStrings(FList^[i].FString, S);
    if C < 0 then L := I + 1 else
    begin
      H := I - 1;
      if C = 0 then
      begin
        Result := True;
        if Duplicates <> dupAccept then L := I;
      end;
    end;
  end;
  Index := L;
end;
 
function TStringList.IndexOf(const S: string): Integer;
begin
  if not Sorted then Result := inherited IndexOf(S) else
    if not Find(S, Result) then Result := -1;
end;

... mais les performances de rapidité de l'IndexOf standard sont sanctionnées par l'utilisation de l'instruction CompareStrings(FList^[i].FString, S) qui dans une fonction personnalisée peut être remplacée par une simple comparaison directe de chaines FList^[i].FString > S dans le cas de chaines non accentuées. Voiçi une fonction de remplacement plus rapide qui exploite ce principe :

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
 
function IndexOfSL3(SL : TStringList; const S: string): Integer;
// Si SL.Sorted=False la présence de caractères accentués ne fausse pas le résultat.
// Dans le cas inverse n'utiliser cette fonction que pour des chaînes non accentuées.
// sinon remplacer le calcul de C par C := CompareStr() qui est plus lent
var      L, H, I, C: Integer; ok : boolean;
begin    with SL do
         begin Result := -1;
               // Cas SL non triée : Parcours depuis début de liste vers fin :
               if Not Sorted then
               begin I:=-1;
                     repeat inc(I);
                     until  (SL[I] = S) or (I = Count-1); // < l''égalité SL[I] = S marche même en présence de caractères accentués
                     if SL[I] = S then Result:= I;
                     EXIT;
               end;
               // Cas SL triée : Parcours depuis la médiane de la liste
               // vers le début ou la fin en fonction du signe de C :
               L := 0;
               H := Count - 1;
               ok:=false;
               while L <= H do
               begin I := (L + H) shr 1;
                     if SL[i] < S then C:=-1 else
                     if SL[i] > S then C:=+1 else C:=0;
                     if C < 0 then L := I + 1 else
                     begin H := I - 1;
                           if (C = 0) then
                           begin ok:=true;
                                 if Duplicates <> dupAccept then L := I;
                           end;
                     end;
               end;
               if ok then Result:= L;
         end; 
end;

III)

Mais il est vrai que l'on peut toujours trier la liste en local pour accélérer les recherches.

... oui-mais sous réserve que le temps mis pour trier la liste ne dépasse pas le gain résultant de l'accélération des recherches.

A+

**PapyJohn** · 18/11/2007, 16h13

Votre mesure n'est pas 'honnête"

En rajoutant le delete il est clair que la fonction rame c'est bien pourquoi j'ai bien insisté sur la définition de a table

L : array[0..40000] of string[62];
// Par facilite

M=TStronglist.create.
M.LoadFromFile(NomLongFichierOrig);
For i:=0 to M.count-1 do
L[i]:=M[i],
La table L contient la même chose que M

et en sortie la liste L contient bien les éléments sans les doublons, le nombre d'éléments valide est le résultat de la fonction et il reste du garbage dans la table. Si c'est lui qui vous dérange vous dites que L est une table dynamique et vous faites un setlength à la nouvelle taille

Puisse que vous fouillez visiblement le classes.pas (comme moi)
vous pouvez allez voir le fonctionnement du loadfromFile ou steam

Il lit le fichier d'un seul coup Size octets dans S
puis il découpe le buffer en string car le fichier texte rajoute des $10 et à13 en fin de chaque ligne il fabrique alors le string et fait un ADD
er c'est dans le ADD qu'il n'ajoute pas le string dans la liste en sortie (qu'il fabrique directement triée si besoin.
Chaque fois due vous ferez un add en fonction du duplicate il ajoute ou pas.

Mais si vous arrivez vec une liste avec des doublons il n'existe pas de méthode pour la nettoyer. il faut faire un save et un load ou appeler une fonction qui le fait comme la mienne
Le seul moment où j'ai réellement eu des résultats est dans le tri.

L'hiver est un temps propice à la programmation: pas envie d'aller courir dehors!

PapyJohn

**Gilbert Geyer** · 18/11/2007, 17h15

Re-Bonjour,

A PapyJohn :

Votre mesure n'est pas 'honnête"
En rajoutant le delete il est clair que la fonction rame

... en fait l'ajout du delete était la première idée qui m'est venue à la tête pour rendre le fichier-resultat entièrement "clean" et je pensais qu'en faisant les delete dans une boucle Downto ce serait plus favorable pour le chrono.
(tiens en rédigeant ceci, il me vient une idée que je vais tester demain : remplacer la boucle des delete en modifiant simplement la valeur de Capacity)

L : array[0..40000] of string[62];

M=TStronglist.create.
M.LoadFromFile(NomLongFichierOrig);
For i:=0 to M.count-1 do
L[i]:=M[i],

... Ok, je vais demain faire comme ceci, un test comparatif, en éliminant le garbage avec un SetLength à la nouvelle taille.

Puisse que vous fouillez visiblement le classes.pas (comme moi)

... Ben-oui, car c'est très instructif (à part les fois où je n'y pige rien...).

L'hiver est un temps propice à la programmation: pas envie d'aller courir dehors!

... exact! En plus de cela on a eu un été pourri et maintenant on caille.

A+

**PapyJohn** · 18/11/2007, 20h53

je fouille le classes pour voir somment fait delphi dans le delete pour resituer le memoire
Il y a peut etre un moyen de n'en faire qu'un!
Bonne Nuit
PapyJohn

**Gilbert Geyer** · 19/11/2007, 14h07

Bonjour,

A PapyJohn

1) A propos de mon idée d'utiliser Capacity pour tronquer la liste : Elle est nulle car tout d'abord l'aide Delphi dit :

De plus, si la valeur affectée à Capacity est inférieure à celle de Count, la mémoire utilisée pour stocker les chaînes qui sortent de la liste n'est pas libérée.

... et en plus cela provoque le message d'erreur "Violation d'accès à ..."

2) Ton idée est nettement meilleure : elle m'a mis sur la piste d'une solution encore plus directe : au lieu de passer par une variable intermédiare du type array of string[62] pour faire For i:=0 to M.count-1 do L[i]:=M[i] afin de pouvoir faire le SetLength avant de sauver le résultat sur disque je sauve le résultat directement sur le disque au fur et à mesure de sa création avec un FileStream.Write() 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
 
procedure SupprDoublonsPapyJohn2(const nomFiSource, NomFiDest : string);
var      i : longint; L : TStringList; FS : TFileStream;
begin    L:=TStringList.create;
         L.Sorted := FALSE; // < pour accélérer le LoadFromFile
         L.LoadFromFile(nomFiSource);
         if L.Count>0 then
         begin L.Sort; // < 1 seul tri
               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;

... tout d'abord cette procédure évite le passage par la variable intérmédiare d'où économie de mem-vive, intéressant pour cas de gros fichiers.
... et pour les vitesses c'est encore mieux :
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 (version d'hier avec Delete)
- Durée totale : mis : 175 ms avec SupprDoublonsPapyJohn2
- Durée totale : mis : 113 ms avec SupprDoublonsDansFI3 : 1,54 fois plus rapide.

2) Avec le fichier de 200000 lignes dont une ligne sur deux est du texte aléatoire de 62 cara 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 SupprDoublonsPapyJohn2 : 12,15 fois plus rapide que SupprDoublonsDansFI3. (j'ai refait ce test plusieurs fois car au vu du résultat du premier essai j'ai cru avoir cliqué sur un autre bouton !!)

3) Avec le fichier Sudoku.txt de 362880 lignes de 9 caractères sans aucun doublon :
- Durée totale : mis : 6202 ms avec SupprDoublonsPapyJohn2
- Durée totale : mis : 4332 ms avec SupprDoublonsDansFI3 : 1,43 fois plus rapide

Conclusion l'ancien score est battu par SupprDoublonsPapyJohn2 (SupprDoublonsDansFI3 est plus rapide seulement dans les cas où la liste contient peu de doublons ou aucun doublon à supprimer, ce qui est agaçant car on ne sait pas à l'avance dans quel cas on se retrouve et un comptage préalable du nombre de doublons prendrait presque autant de temps que leur suppression).

A+

**PapyJohn** · 19/11/2007, 14h39

J'ai fouille le delete en realite il appelè un finalize avec un count pour un freemem
Donc plus besoin de write (qui était une bonne idée)
On reste avec la TstringListe de base
On fazit un loadFromfie (a qui je viens de p)asser un peit cop d'accelerateur)
on elimine les doubons et on fait un finalize

Perso je ne travaille qu'avec du pre alloue et le NbLignes me donne largement satisfaction. Mon axiome de base étant moins tu demandes de chose au gestionnaire de mémoire moins il risque d'exploser.
Alors tanpis je préférè occuper de la memoire (surtout que sous windows ca l'occupe deja beaucoup)

Il ne te manque que le tri. Je te le joins
pour tester
Tu charge ton fichier avec le sort et le duplicates
et tu mesure le temps

Pour moi tu charges la liste avec un load sans tri ni doublons

tu déclenche le chrono

tu recopies ta liste dans L
Tu tires
Tu enleve les doublons
tu arretes le chrono

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
 
procedure Tri_;
var
 s, sj, sl, sr, j,k: Longint;
 Code: string[9];
 Resa: string[9];
 St  : array[0..5000, 0..1] of Longint;
 
begin
 S := 1;
 st[S, 0] := 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 < 1;
end;
function Doublons(Deb,Fin:longint): longint;
var i: Longint;
 Index: Longint;
begin
 i := Deb;
 Index := Deb;
 repeat
   if L[i]<>L[i+1] then
     begin
      Inc(Index);
      L[index]:=L[i+1];
     end;
   inc(i);
 until i >= Fin;
 Doublons := Index;
end;

Et donc pour comparer tu fais

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
 
 
 M.Clear;
 M.sorted:=true;
 M.Duplicates:=dupIgnore;
 QueryPerformanceCounter(FStart);
 M.LoadFromFile('Sudoku.TXT');
 QueryPerformanceCounter(FStop);
 FElapsed := (FStop - FStart) div 1000;
 
 
 NbLignes:=M.Count-1;
 QueryPerformanceCounter(FStart);
 for j:=0 to NbLignes do
   L[j]:= M[j];
  Tri_;
 Doublons;
 QueryPerformanceCounter(FStop);
 FElapsed := (FStop - FStart) div 1000;

La le temps est intéressant!!!

A+

PapyJohn (j'ai oublié le fauteuit roulant

)
Mais le moral est bon!!!

**Gilbert Geyer** · 19/11/2007, 16h12

Re-Bonjour,

A PapyJohn : Ouille encore une nouvelle idée !

Comme j'ai sauté le repas de midi (skotché devant micro depuis ce matin) je ferai les tests comparatifs demain matin.

Par contre en lisant rapidement ton code il y a un truc qui m'intrigue :

Code :

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

1
2
3
4
5
 
 M.sorted:=true;
 M.Duplicates:=dupIgnore;
 QueryPerformanceCounter(FStart);
 M.LoadFromFile('Sudoku.TXT');

... si Sorted:=true alors le Duplicates:=dupIgnore a de l'effet sur le LoadFromFile() qui élimine les doublons d'entrée de jeu en ralentissant le chargement qui s'effectue par une succession d'insertions et de décalages de lignes.
... de plus avec Sorted:=true la liste est triée d'entrée de jeu donc quel est l'intérêt de la trier une deuxième fois avec la procedure Tri_; ???????

Par contre cela ne m'empêchera pas de faire des tests comparatifs j'en profiterai pour comparer également les performances de ta procedure Tri_; à celles de la méthode "Sort" standard.

A propos de QueryPerformanceCounter : Je me contente d'une précision d'une milliseconde (avec GetTickCount) depuis que je me suis rendu compte que Windows piquait la main quand ça lui chante et autant de fois que ça lui chante même si on fixe la priorité à HightPriority (orthographe approximative) et même en lui passant la main avec Application.ProcessMessages juste avant le Start-Chrono.

Sur ce, je vais rattraper le repas de midi.

A+

**PapyJohn** · 19/11/2007, 16h31

Exact
il faut le mettre a false pour partir d'un
fichier non trié: trop facile!

(n'oublies pas de mettre une echarpe: le coup de vent pourrait t'enrhumer)!

PapyJohn

**Gilbert Geyer** · 19/11/2007, 16h43

Re-bonjour,

A PapyJohn :
J'allais quitter le forum quand...

Exact il faut le mettre a false pour partir d'un fichier non trié

... là on est d'accord.

n'oublies pas de mettre une echarpe: le coup de vent pourrait t'enrhumer!

... pour aujourd'hui pas de risque je ne quitterai ma turne avant demain matin.

... et pour commencer je vais rattraper le repas de midi.

A+

**Gilbert Geyer** · 20/11/2007, 13h11

Bonjour,

A PapyJohn : Je viens de tester ta procédure de tri destinée à remplacer la méthode "Sort" dans la suppression de doublons mais elle me pose des problèmes je n'y ai pourtant remplacé que la taille des variables Code et Resa :

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
 
procedure Tri_3;
         var       s, sj, sl, sr, j,k: Longint;
                   Code: string; //string[9];
                   Resa: string; //[9];
                   St  : array[0..5000, 0..1] of Longint;
 
         begin S := 1;
               st[S, 0] := 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 < 1;
         end; // Tri_3

Problème n°1 : en effectuant un tri sur la liste suivante :

Code :

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

... elle me sort comme résultat :

Code :

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

... les doublons ou triplons sont bien regroupés à l'exception de ceux formés par les chaines '2'. ?????? Cela vaudrait le coup d'en trouver la cause car ta procedure est effectivement plus rapide que la méthode standard "Sort" mais tant que le fonctionnement n'est pas entièrement correct je ne vais pas annoncer le résultat du chronomètre.

Problème n°2 : En fait il s'agit plutôt d'une question au sujet de la variable St : array[0..5000, 0..1] of Longint; j'y ai laissé la valeur de 5000 en pensant que cela provoquerait un plantage dans le cas d'un tri avec le fichier de 200000 lignes. Et comme il n'y a eu aucun plantage (à part peut être que le résultat du tri en était faussé) le question est "par quoi remplacer cette valeur de 5000 afin que la procédure de tri puisse être utilisable quelle que soit la taille de la liste à trier" ?? Par nbLignes ?

Au fait pendant que j'y suis : As tu eu au moins l'une des deux réponses que je t'ai envoyées en réponse à ton Message-perso ?

A+

Dédoubler un fichier texte rapidement

Langage Delphi

Discussions similaires

Partager

Partager