Dédoubler un fichier texte rapidement

**bilbo194** · 11/11/2007, 13h56

Bonjour,

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

Pour le moment, je charge le fichier dans une TStringList avec Duplicated = False. Ca fonctionne bien mais ca devient trop long avec des gros fichiers.

Si vous avez une experience de ce type de traitement merci d'avance de votre aide.

Jean-Michel

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

Salut,

Pour le moment, je charge le fichier dans une TStringList avec Duplicated = False. Ca fonctionne bien mais ca devient trop long avec des gros fichiers.

... avec une StringList la rapidité d'ajout ou d'accueil de chaînes est maximale lorsque Sorted := False (dans ce cas peu importe la valeur de Duplicates) car si jamais Sorted était à True les ajouts de chaînes dans la StringList s'exécuteraient par insertion ce qui nécessite à chaque nouvelle à ajouter que Delphi décale toutes les lignes qui suivent dans l'ordre de tri ce qui ralentit la cadence (alors qu'avec Sorted := False Delphi place chaque nouvelle chaine directos à la fin de la StringList ce qui est nettement plus rapide).

Par contre si t'as déjà mis Sorted := False la rapiditié des ajouts ne peut pas être améliorée (à part peut-être de gagner du temps d'éxec en spécifiant avant l'ajout des chaînes le nombre de chaînes pour lesquelles la liste de chaînes doit allouer de la mémoire avec la propriété Capacity :=plusieurs millions de lignes + 1 sinon il risque d'y avoir un ralentissement à partir du moment ou en cours d'éxec la valeur prise par Count dépasse la valeur par défaut de Capacity (qu'on oublie souvant d'initialiser) ce qui oblige Delphi à faire de la réallocation de mémoire en cours de route ce qui ralentit également la cadence).

Et si tu as déjà initialisé la propriété Capacity avec une valeur légèrement supérieure au nombre maxi de lignes de ton plus long fichier t'as la vitesse maximale qu'on peut attendre avec la StringList. Et dans ce cas pour gagner en rapidité il faut dédoubler tes fichiers en les chargeant dans une autre structure (un Stream par exemple) mais à déterminer en fonction de ce que tu veux faire par la suite avec les textes en question car les StringList ont des avantages que les Stream n'ont pas et les Stream d'autres avantages que les StringList n'ont pas.

A+

**sjrd** · 11/11/2007, 15h29

Si c'est pour copier purement et simplement le fichier :

Comment copier un fichier ?

**Gilbert Geyer** · 11/11/2007, 15h49

Re-bonjour,

Merci Sjrd : Effectivement "dédoubler des fichiers textes" c'est peut être tout simplement d'en faire une copie et rien de plus, autant pour moi

A+

**bilbo194** · 11/11/2007, 16h23

Merci de vos réponses.

Le but est d'enlever les lignes en double (en triple, etc) et de generer un nouveau fichier texte ne comportant aucun doublon.

Il n'y a aucune autre manipulation sur le fichier ou la StringList.

Sort est à True je vais donc le mettre à False et initialiser Capacity à une valeur superieure au nombre de lignes du fichier.

Apres test, je donnerai les résultats ici.

Bon dimanche
Jean-Mcihel

**sjrd** · 11/11/2007, 16h35

Envoyé par bilbo194

Le but est d'enlever les lignes en double (en triple, etc) et de generer un nouveau fichier texte ne comportant aucun doublon.

Ah ah ! Fallait le dire plus tôt.
Un sujet similaire (non en fait, c'était exactement la même chose) a été traité il y a quelque temps :
http://www.developpez.net/forums/sho...hlight=doublon

Bon courage

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

Re-bonjour,

Comme dit Srjd la suppression des doublons a déjà été traitée il te suffit de récupérer le code situé à la fin de la discussion dont il a donné le lien.

Bigre! En réexaminant ce code je me rends compte qu'il y manque juste après l'instruction lignes := TStringList.Create; l'instruction lignes.capacity:=NombreMaxDeLignes que je signalais tout à l'heure mais pour le reste c'est bon. (l'oubli provient du fait que j'avais fait les tests comparatifs de vitesse sur des fichiers plus petits que ceux d'Art19, car toujours impatient d'avoir les résultats chronométrés)

A+

**PapyJohn** · 11/11/2007, 18h31

Heureux que tu ai ta solutoin Mais une info complémentaire quand vos faites un loadfromfile e que vous avez des fichiers dizaine de meg Méga le liste Manager(e on le comprend à pédaler Je le soupçonne de faire des add avec tri a chaque ligne on peut (doit) utiliser la propriété Text . Il s'agit du String comprenant tous les rangées de la stringglist.

Si on met sort à true et duplicatas à true :on lit le fichier avec un blovread= et instantanément la liste de trouve triée, épurée
In simple savetoFile et c'est joué
Je n'ai pas trouver une methofe plus rapide mas celle la mache à fong.

PapyJohn

**Gilbert Geyer** · 12/11/2007, 12h04

Salut,

PapyJohn a écrit : quand vos faites un loadfromfile e que vous avez des fichiers dizaine de meg Méga le liste Manager(e on le comprend à pédaler Je le soupçonne de faire des add avec tri a chaque ligne on peut (doit) utiliser la propriété Text . Il s'agit du String comprenant tous les rangées de la stringglist.

... Dans le code qui figure en fin de la discussion dont Sjrd à cité le lien nous utilisons LoadFromFile après Sorted := FALSE il n'y a donc aucun "Add avec tri à chaque ligne" mais des Add qui sont placés directement et illico à la fin de la liste.

... Par contre l'idée d'utiliser la propriété Text m'intéresse mais comme tu écris :

Code :

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

1
2
Si on met  sort à true et duplicatas à true : on lit le fichier avec un blovread= et instantanément la liste de trouve triée, épurée
In simple savetoFile et c'est joué

ceci m'intrigue : je peux mettre Duplicates:=DupAccept (à la place de true) ou DupIgnore (si t'as voulu dire false à la place de true) par contre je ne vois pas comment on doit utiliser la propriété Text dans ce contexte et je n'ai pas trouvé "blovread" ni dans l'aide de Delphi ni dans celle de SDKWindows ?
Mais commre tu ajoutes :

Je n'ai pas trouver une methofe plus rapide mas celle la mache à fong.

... ce serait sympa de nous donner des éclaircissements ou le bout de code concerné car on est tous intéressés surtout s'il s'agit de la méthode la plus rapide.

A+

**DragonHeart** · 12/11/2007, 13h23

Salut,

Je pense qu'il a voulu dire "BlockRead"

Si j'ai bien compris sa solution tu lis le fichier par un BlockRead que tu envoie dans le .Text de ta stringlist en mettant les options Sorted à True et Duplicates a DupIgnore

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

Re-bonjour,

Merci DragonHeart : "BlockRead" : je l'avais complètement oublié.
Je vais faire un test comparatif.

A+

**PapyJohn** · 12/11/2007, 14h27

Les remarques sont justes voici une petite synthèse
Quand on manipule des listes il est préférable de mettre le sort a faux et true une fois le traitement fini (quand c’est possible bien sur)
Mais avec un delete par exemple on ne trie qu’une fois

Pour aller vite au moment du chargement pour de gros fichiers, il est plus rapide de passer par la propriété TEXT : on charge (avec un BlockRead par exemple) directemrt

Code :

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

1
2
3
4
5
6
Maliste := Tstringlist.Create;
Maliste.Sorted := True;
 
Open (F)
Blockhead (F, Maliste.TXT, falsie(f)) ;
Close (F)

Et hop le tour est joué!
Il existe un faux ami dans la gestion des listes(au moins avec D6) c’est le camarade indexof qui ne fonctionne que sur des listes triées
On pourrait croire à des recherches rapides (dichotomie) mais c’est un faux amis : liste triée ou pas il ne sait balayer sequentiellement sortie s’il trouve

Exemple

Code :

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

1
2
3
4
5
6
7
8
9
10
11
Maliste := Tstringlist.Create;
Maliste.Sorted := True;
 
For i :=1 to 1000000 do
  MaLiuste.Add’IntTostr(i)) ;
 
for i:=1 to 1000 do
  Cpt:=MaListe.Indexof(Maliste.Items[random (100001)]);
 
for i:=1 to 1000 do
  Cpt:=Recherche (Maliste.Items[random (100001)]);

A l :a place d’indexof uilisez cette peite recherche dico bien banale e standard !

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
 
function Recherche (Cherche: ShortString): integer;
var sup, mi, inf: integer;
begin
 Sup := MaListe.count - 1;
 Inf := 0;
 Dichotom := -1;
 while inf <= Sup do
  begin
   mi := (inf + sup) shr 1;
   if MaListe[mi] = Cherche then
    begin
     Dichotom := mi;
     exit;
    end
   else
    if MaListe [mi] < Cherche  then
    Inf := Mi + 1
   else
    Sup := Mi - 1;
  end;
end;

Je ne suis pas un artiste de la surcharge de méthode mais il doit etre possibe e de remplacer la méthode actuelle par celle-ci (avec un complément)

Pour Info aussi pour recopier une liste dans une autre on se sert aussi de la propriété text ; StrCopy

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

Re-bonjour,

1) Suppression de doublons :
A PapyJohn : Entre-temps j'ai codé votre idée 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
 
procedure TfrmGen.bIdeePapyJohnClick(Sender: TObject);
var       pop,i,j : Integer;
          lignes : TstringList;
          NomCourtFichier, NomLongFichierOrig, RepAppli : string; chronoA : oChrono;
          NomSauverSous : string;
 
          FromF   : file; // < 2Go max
          NumRead : Integer;
          Buf     : array[1..40960] of Char;
          S : 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(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;
 
                lignes.Text:='';
                lignes.Sorted := TRUE;
                lignes.Duplicates:=DupIgnore;
 
                AssignFile(FromF, NomLongFichierOrig);
                Reset(FromF, 1);
                repeat BlockRead(FromF, Buf, SizeOf(Buf), NumRead);
                       S:='';
                       for i := 1 to NumRead do S:=S+Buf[i];
                       lignes.Text:=lignes.Text+S;
                until (NumRead = 0);
                CloseFile(FromF);
 
                lignes.SaveToFile( NomSauverSous );
 
                redRapport.lines.add('Durée totale : mis : '+intToStr(chronoA.mis)+ ' ms');
                //avec fichier de 10000 lignes de 62 car Durée totale : mis : 1551 ms           
        end;
end;
 
//BlockRead (FromF, lignes.TeXT, false(FromF)); > [Erreur] uLectureMegaFicier.pas(1458): Un objet constante ne peut être passé comme paramètre Var et false(FromF) génère une deuxième erreur

Test de rapidité avec un fichier de 10000 lignes de 62 caractères, soit 644 Ko, Durée totale : mis : 1551 ms

( je n'ai pas pu utiliser BlockRead (FromF, lignes.TeXT, false(FromF)); que vous citez car [Erreur] LectureMegaFicier.pas(1458): Un objet constante ne peut être passé comme paramètre Var et en plus "false(FromF)" génère une deuxième erreur).

Avec le code suivant qui est une remise en forme du code de juin qui figure à la fin de la discusssion citée par Sjrd :

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
 
// Code de juin 2007 scindé en fonctions :
 
procedure SupprDoublonsDansSL(var Liste : TstringList);
var       i,j : integer;
begin     Liste.Sorted := true;
          Liste.Sort;
          i := Liste.count - 1;
          repeat j:=i-1;
                 if Liste[i]=Liste[j] then Liste.delete(i);
                 dec(i);
          until i=0;
end;
 
procedure SupprDoublonsDansFI(const nomFiSource, NomFiDest : string);
//        avec LoadFromFile
var       lignes : TStringList;
begin     lignes := TStringList.Create;
          lignes.Sorted := FALSE;  // insertion plus rapide en l'absence de recherche simultanée
          try lignes.LoadFromFile( nomFiSource );
              SupprDoublonsDansSL(lignes);
              lignes.SaveToFile( NomFiDest );
          finally
              lignes.free;
          end;
end;
 
procedure SupprDoublonsDansFI2(const nomFiSource, NomFiDest : string);
// variante avec   FileStream; : un chouïa plus rapide qu'avec LoadFromFile
 
var       lignes : TStringList; FS : tFileStream;
begin     lignes := TStringList.Create;
          lignes.Sorted := FALSE;  // insertion plus rapide en l'absence de recherche simultanée
          FS := TFileStream.Create(nomFiSource, fmOpenRead);
          try FS.Position:=0;
              lignes.LoadFromStream(FS);
              FS.Free;
              SupprDoublonsDansSL(lignes);
              FS := TFileStream.Create(NomFiDest, fmOpenWrite);
              lignes.SaveToStream(FS);
          finally
              lignes.free;
              FS.Free;
          end;
end;
 
// Utilisation :
procedure TfrmGen.bASuppDoublonsClick(Sender: TObject);
var       NomCourtFichier, NomLongFichierOrig, RepAppli : string; chronoA : oChrono;
          NomSauverSous : string; pop : Integer;
begin
          RepAppli:=ExtractFilePath(Application.ExeName);
          OpenDialog1.InitialDir := RepAppli;
          OpenDialog1.Filter:= 'Fichiers Texte (*.txt)|*.TXT';
          if OpenDialog1.Execute then
          begin
                Application.ProcessMessages;
                ChronoA.Top(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;
 
                //SupprDoublonsDansFI(NomLongFichierOrig, NomSauverSous); //Avec LoadFromFile et fichier de 200000 lignes de 62 car Durée totale : mis : 4803 ms
                SupprDoublonsDansFI2(NomLongFichierOrig, NomSauverSous);  //Avec LoadFromStream  et fichier de 200000 lignes de 62 cara Durée totale : mis : 4733 ms
 
                redRapport.lines.add('Durée totale : mis : '+intToStr(chronoA.mis)+ ' ms');
                //avec fichier de 10000 lignes de 62 cara  Durée totale : mis : 177 ms
 
          end;
end;

et avec le même fichier de test de 644 Ko Durée totale : mis : 177 ms soit 1551/177 = 8.76 fois + rapide.
(Essais effectués avec Delphi5 + Win98 + Pentium III 1,13 GHz)

2) A propos du camarade IndexOf : exact, c'est "un faux ami" cela avait fait l'objet d'une discussion il ya quelques mois au cours de laquelle il a été mis au point une fonction similaire à celle que vous proposez.

A+

**Gilbert Geyer** · 13/11/2007, 15h52

Bonjour,

Suppression de doublons dans fichiers texte :

PapyJohn va être content : en remplaçant le code suivant :

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
procedure SupprDoublonsDansFI2(const nomFiSource, NomFiDest : string);
var       lignes : TStringList; FS : tFileStream;
begin     lignes := TStringList.Create;
          lignes.Sorted := FALSE;  // insertion plus rapide en l'absence de recherche simultanée
          FS := TFileStream.Create(nomFiSource, fmOpenRead);
          try FS.Position:=0;
              lignes.LoadFromStream(FS);
              FS.Free;
              SupprDoublonsDansSL(lignes);
              FS := TFileStream.Create(NomFiDest, fmOpenWrite);
              lignes.SaveToStream(FS);
          finally
              lignes.free;
              FS.Free;
          end;
end;

par celui-ci, ou j'utilise la propriété Text de la StringList :

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 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);
              FS.Read(Pchar(TXT)^,FS.Size);
              lignes.Text:=TXT;
              lignes.SaveToFile( NomFiDest );
          finally
              lignes.free;
              FS.Free;
          end;
end;

... j'obtiens les résultats de chronométrage suivants :

1) avec fichier-tests de 10000 lignes de 62 caractères et un seul doublon en fin de fichier :
- Durée totale : mis : 177 ms avec SupprDoublonsDansFI2
- Durée totale : mis : 230 ms avec SupprDoublonsDansFI3

2) avec un fichier de 10000 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 >>>' :
- Durée totale : mis : 269 ms avec SupprDoublonsDansFI2
- Durée totale : mis : 113 ms avec SupprDoublonsDansFI3 (2,38 x+rapide)

3) 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 : 314210 ms avec SupprDoublonsDansFI2
- Durée totale : mis : 55879 ms avec SupprDoublonsDansFI3 (5,6 x+ rapide)

(avec Pentium III 1.13 Ghz)

Merci PapyJohn

Je laisse à Bilbo194 le soin de faire des tests avec ses fichiers de "plusieurs millions de lignes".

A+

**PapyJohn** · 13/11/2007, 19h37

J'ai un peu honte de dire comment je fais car les purstes vont trouve ma méthode barbare

Mais je ferai cette petite modif dans votre code

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
                lignes.Text:='';
                lignes.Sorted := FALSE;
                lignes.Duplicates:=DupIgnore;     
                AssignFile(FromF, NomLongFichierOrig);
                Reset(FromF, 1);
                Lo:=FileSizof(FromF);
                BlockRead(FromF, lignes.Text, Lo, NumRead);
                CloseFile(FromF); 
                lignes.Sorted := TRUE;
                Lignes.sort;

Dans le même genre avez vous constater qu'a partir de 25 millions d'éléments le quicksort ralenti?

En réalité pour éliminer les doublons le plus speed c'est le move....
Et s'il est vrai que le challenge peut paraitre mesquin mais quand réellement vous manipulez des listes avec des millions d'occurrence les gains prennent beaucoup d'importance
PapyJohn

**Gilbert Geyer** · 14/11/2007, 11h45

Bonjour,

PapyJohn a écrit : "J'ai un peu honte de dire comment je fais car les purstes vont trouve ma méthode barbare"

... S'il s'avère que votre méthode est plus rapide (à vérifier) même les puristes la qualifieront de "plus rapide" et non de "barbare".

Ensuite :
Dans le même genre avez vous constater qu'a partir de 25 millions d'éléments le quicksort ralenti?

... j'ai jamais eu l'occasion de faire des tests de suppression de doublons ni de tri dans un fichier aussi gros et je ne m'en plains pas car quand je lance un test je suis impatient d'avoir le résultat et en général j'augmente progessivement la taille de mes fichiers-de-tests tant que le délai d'attente ne dépasse pas 5 minutes, .... sans oublier que s'il s'agit de tests en rapport avec un Forum il y a en général "N" méthodes différentes à tester.

Ensuite:
En réalité pour éliminer les doublons le plus speed c'est le move....

... Là vous m'intriguez car à propos de la méthode avec "BlockRead + utilisation de la propriété Text" vous disiez "Je n'ai pas trouver une methofe plus rapide mas celle la mache à fong". Par contre il s'agit peut-être d'une idée plus récente. Vous feriez comment pour éliminer les doublons avec move ?

Ensuite : Et s'il est vrai que le challenge peut paraitre mesquin mais quand réellement vous manipulez des listes avec des millions d'occurrence les gains prennent beaucoup d'importance.

... Absolument d'accord.

Je vais faire des tests comparatifs avec la modif que vous avez apportée au code d'hier.

A+

**Gilbert Geyer** · 14/11/2007, 13h12

Re-Bonjour,

A PapyJohn / Suppression de doublons : J'ai été obligé de modifier votre proposition comme suit (le compilo n'a pas aimé certains trucs : voir commentaires dans le 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
procedure SupprDoublonsDansFI4(const nomFiSource, NomFiDest : string);
//        variante proposée par PapyJohn le 13 nov 2007, 19h37
var       lignes : TStringList; TXT : string;
          FromF  : file;
          Lo, NumRead : integer;
begin     lignes := TStringList.Create;
          lignes.Text:=''; TXT:='';
          lignes.Sorted := FALSE;
          try
             AssignFile(FromF, nomFiSource);
             Reset(FromF, 1);
             Lo:=FileSize(FromF);
             SetLength(TXT,Lo); // sinon Erreur E/S 87
             //BlockRead(FromF, lignes.Text, Lo, NumRead); [Erreur] > uLectureMegaFicier.pas(1421): Un objet constante ne peut être passé comme paramètre Var
             BlockRead(FromF, PChar(TXT)^, Lo, NumRead);
             CloseFile(FromF);
             lignes.Sorted := TRUE;
             lignes.Duplicates:=DupIgnore;
             lignes.Text:=TXT;
             //Lignes.sort; < Ligne qui s'avère inutile
             lignes.SaveToFile( NomFiDest );
          finally
             lignes.free;
             SetLength(TXT,1);
          end;
end;

et voiçi les résultats des tests comparatifs :

1) avec un fichier de 10000 lignes dont une ligne sur deux est du texte aléatoire de 62 cararctères et une ligne sur deux est égale à la chaîne '<<< MI-DOUBLON >>>' :
- Durée totale : mis : 113 ms avec SupprDoublonsDansFI3
- Durée totale : mis : 112 ms avec SupprDoublonsDansFI4

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 : 55879 ms avec SupprDoublonsDansFI3
- Durée totale : mis : 67215 ms avec SupprDoublonsDansFI4 soit 1,2 fois plus lent.

(valable pour Pentium III à 1,13 GHz)

A mon avis la différence de vitesse provient essentiellement du fait que le FileStream utilisé dans SupprDoublonsDansFI3 est légèrement plus rapide que le BlockRead utilisé dans SupprDoublonsDansFI4 car pour le reste les deux codes sont équivalents.

Par contre on pourra peut-être améliorer avec votre idée d'utiliser le move mais faudrait que j'en sache un plus à ce sujet.

A+

**Gilbert Geyer** · 14/11/2007, 14h51

Bonjour,

A PapyJohn / Suppression de doublons :

J'ai fait des essais comparatifs avec le code suivant qui inclut l'utilisation de move :

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
procedure SupprDoublonsDansFI5(const nomFiSource, NomFiDest : string);
var       lignes : TStringList; i,j : integer;
begin     lignes := TStringList.Create;
          lignes.Sorted := FALSE;  
          try lignes.LoadFromFile( nomFiSource );
              lignes.Sorted := TRUE;
              lignes.Sort;
              lignes.Sorted := FALSE;
              i := lignes.count - 1;
              repeat j:=i-1;
                 if lignes[i]=lignes[j] then lignes[i]:=''; //variante 1
                 //if lignes[i]=lignes[j] then lignes.delete(i); //variante 2 
                 //if lignes[i]=lignes[j] then lignes.Move(i, 0); //variante 3 
                 dec(i);
              until i=0;
              lignes.SaveToFile( NomFiDest );
          finally
              lignes.free;
          end;
end;

... resultats pour SupprDoublonsDansFI5 avec le fichier-de-tests de 10000 lignes avec un mi-doublon dans une ligne sur deux :
- variante 1 : avec affectation lignes[i]:=ChaîneVide : Durée totale : mis : 156 ms + inconvénient : le fichier de Destination se retrouve truffé de chaines-vides mais les doublons-texte sont supprimés.
- variante 2 : avec supression par delete(i) : Durée totale : mis : 270 ms.
- variante 3 : lignes.Move(i, 0); : Durée totale : mis : 561 ms + gros inconvénient les doublons-texte ne sont pas supprimés mais simplement regroupés.

Conclusion : pour l'instant SupprDoublonsDansFI3 reste la plus rapide (113 ms avec le même fichier-tests).

A+

**PapyJohn** · 15/11/2007, 09h25

Bon alors je m'y colle je fais un teste bien complet pour la vitesse
il serait bien que l'on utilise tous le même fichier de test ou du moins constitue

En réalité pour obtenir des fichiers aussi volumineux je travaille sur le sudoku et les carres magiques: le moindre fait 30000 ligns!

Ai chrono (AMD 2 Ghtz,2 Go Mem)
PapyJohn

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

Bonjour,

PapyJohn a écrit :
Bon alors je m'y colle je fais un teste bien complet pour la vitesse
il serait bien que l'on utilise tous le même fichier de test ou du moins constitue

... En toute rigueur c'est ce qu'il faudrait faire cela règlera au moins une partie du problème des comparaisons mais comme on n'utilise pas tous le même équipement on sera toujors obligés de baser les compararaisons sur des rapports du type "temps-mis-par-méthode-A/temps-mis-par-méthode-B", pour apprécier les différences de performance de rapidité entre les méthodes.

A toutes fins utiles voiçi le code que j'utilise depuis la discussion de juin concernant la suppression des doublons :

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
 
procedure TfrmGen.bCreerFichierTxtAleatoireClick(Sender: TObject);
// crée un Fichier calibré de "texte" aléatoire alterné de mi-doublons comme suit:
// 02/12/95,07:56,0.62,0.19,0.72,0.92,0.38,0.53,0.36,0.95,0.46,1
// <<< MI-DOUBLON >>>
// 07/21/25,10:47,0.28,0.02,0.42,0.52,0.96,0.49,0.39,0.25,0.48,3
// <<< MI-DOUBLON >>>
// 11/04/90,02:07,0.55,0.52,0.84,0.93,0.80,0.49,0.12,0.58,0.43,5
// <<< MI-DOUBLON >>>
const     Nmax = 10;
var       FS : TFileStream; NomFichier, LigAl,LigMiDbl : 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;
                   // Champ N pris égal au numéro de ligne sinon doublons-aléatoires-perturbateurs
                   Result:=sr;
          end;
 
begin     NomFichier:=ExtractFilePath(Application.ExeName)+'ftAL44000x62.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;
          LigMiDbl:='<<< MI-DOUBLON >>>'+#13#10;
          repeat inc(numLig); // Ajout de lignes de texte aléatoire et de mi-doublons
                 if odd(numLig)
                 then LigAl:=DateHeureAl+champs1aN(Nmax)+intToStr(numLig)+#13#10
                 else LigAl:=LigMiDbl;
                 FS.Write(PChar(LigAl)^, length(LigAl));
          until numLig=200000; //10000; //  //250000; //44000; //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)); // Ajouté 2 fois = 1 doublon final
          redRapport.Lines.Add( NomFichier+' : '+intToStr(numLig)
                               +' lignes '+intToStr(FS.size)+' Octets'
                               +' mis : '+intToStr(ChronoC.Mis)+' ms');
          Sablier;
          FS.Free;
end;

... En juin ce code générait un fichier qui ne comportait qu'un seul doublon situé en fin de fichier, mais dans la présente discussion je l'ai modifié de sorte que le fichier-tests comporte un mi-doublon dans une ligne sur deux. Depuis le début, pour être certain que les lignes de "texte"-aléatoire ne créent pas des doublons les lignes en question se terminent chacune par intToStr(numLig).

Par contre je crains que le jeu va être serré pour améliorer encore davantage le rapidité de la suppression de doublons vu que SupprDoublonsDansFI2 est une synthèse des meilleures idées proposées en juin et que l'on se rend compte que depuis qu'on a amélioré le score avec SupprDoublonsDansFI3 qui intègre votre idée d'affecter les chaînes directement à la propriété Text les autres récentes tentatives d'amélioration ont échoué comme si on avait atteint le seuil d'incompressibilité.

A+

Dédoubler un fichier texte rapidement

Langage Delphi

Discussions similaires

Partager

Partager