Parcourir un fichier texte sans charger le fichier

**ShaiLeTroll** · 30/05/2007, 18h03

Il existe la méthode dans IniFiles pour la THashStringList qui reprend l'idée de la "somme de contrôle"

Code :

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

1
2
3
4
5
6
7
8
9
function TStringHash.HashOf(const Key: string): Cardinal;
var
  I: Integer;
begin
  Result := 0;
  for I := 1 to Length(Key) do
    Result := ((Result shl 2) or (Result shr (SizeOf(Result) * 8 - 2))) xor
      Ord(Key[I]);
end;

Ensuite, pour la Gestion par Buffer, je l'ai suggéré moi même, c'est un peu chiant à bosser ...

**CapJack** · 30/05/2007, 18h36

Envoyé par Gilbert Geyer

le curseur de comparaison des chaines commence sur le a , passe au z et s'arrête sur la différence o/z, c.à.dire dès le caractère, quelle que soit la longueur de string2. Non?

Ben, non. Je dis "somme", mais ça peut être n'importe quoi ; en tout état de cause, tous les caractères sont considérés. Je ne comprends pas ton raisonnement. L'idée de Shai est excellente.

Envoyé par Gilbert Geyer

A propos de gains en temps de calcul : [/B]Je profite de ce message pour signaler à CapJack que son code pour la recherche de doublons peut être amélioré en remplacant les var k:Char; et les S.Read(k,SizeOf(k)); (qui font de la lecture de flux caractère par caractère) par un var buffer : array [0..4096] of char; puis un lu:=S.Read(buffer,SizeOf(buffer)); qui aspirent les 4096 caractères d'un coup et qui sont nettement plus rapides.

J'ai bien dit que c'était perfectible...

**Gilbert Geyer** · 31/05/2007, 13h26

A ShaiLeTroll :

- "...pour la Gestion par Buffer, je l'ai suggéré moi même, ..." : Exact, excuses, mais je l'avais oublié au point de faire la même erreur que CapJack comme je l'ai d'ailleurs signalé ... je rends donc à César ce qui appartient à César.

- "c'est un peu chiant à bosser ..." : Aucun travail n'est ergonomique, les ergonomes en sont tellement convaincus qu'ils se contentent d'observer le travail des autres (lol).

- "function HashOf(string) " : Elle est séduisante par son apparente simplicité, ce serait intéressant de connaître la démarche intellectuelle suivie pour sa conception et qui se strouve ici résumée pour l'essentiel en deux lignes de code. Par contre je crains que son utilisation dans le cas présent ne soit pas tout à fait appropriée aux gains de vitesse : voir suite dans réponse à CapJack.

A CapJack :

- "en tout état de cause, tous les caractères sont considérés. Je ne comprends pas ton raisonnement." : Si tu devais coder la fonction if string1=string2 en utilisant les fonctions les plus basiques de Delphi il est certain que tu comparerais, de gauche vers la droite, deux à deux, les caractères de ces deux chaines en quittant vite la boucle dès que string1[i]<>string2[i] donc en ignorant tous les caractères situés après cet indice i. Non ?
Et en utilisant n'importe quelle fonction qui tient compte de la totalité des caractères de string1 et de string2 on augmente forcément le nombre d'opérations à effectuer ... ce qui est donc moins rapide. D'ailleurs pour me fixer les idées à ce sujet j'ai utilisé la function HashOf apportée hier par
ShaiLeTroll pour faire un test comparatif de vitesse d'éxecution entre If string1=string2 et if HashOf(string1)=HashOf(string2) avec 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
18
19
20
21
22
23
24
procedure TForm1.bCompareVitesseIFClick(Sender: TObject);
var       s,s1,s2 : string; chrono : oChrono; i,iMax : integer;
// Pour une boucle de iMax = 10 000 000
//- avec if s1=s2 > mis : 286 ms 
//- avec if HashOf(s1)=HashOf(s2) > mis : 23313 ms soit 81 fois plus lent
begin     s := StringOfChar('Z',198);
          s1:='AA' + s;
          s2:='AB' + s;
          iMax:=10000000;
          chrono.Top(Edit1);
          for i:=1 to iMax do
          begin if s1=s2 then
                begin { v'la un doublon } end;
          end;
          redRapport.lines.Add('Pour une boucle de '+intToStr(iMax));
          redRapport.lines.Add('- avec if s1=s2 > mis : '+intToStr(chrono.Mis)+' ms');

          chrono.Top(Edit1);
          for i:=1 to iMax do
          begin if HashOf(s1)=HashOf(s2) then
                begin { v'la un doublon } end;
          end;
          redRapport.lines.Add('- avec if HashOf(s1)=HashOf(s2) > mis : '+intToStr(chrono.Mis)+' ms');
end;

- "J'ai bien dit que c'était perfectible..." : Exact, mais je me suis dit qu'en te signalant que "la vitesse d'exécution de cette étape s'est ainsi touvée multipliée par 43" dans mon projet, cela te mettrait l'eau à la bouche pour rectifier ton code vu qu'il est certainement plus performant que celui qu'Art19 a présenté pour illustrer sa demande.

Remarque complémentaire sur l'utilisation de fonctions similiaires à HashOf et qui tiennent compte de la totalité des caractères des chaines :
Comme on a vu en commentaire dans le code du test ci-dessus qu'un simple if string1=string2 est de l'ordre de X à 80 fois plus rapide qu'une fonction qui tient compte de la totalité des caractères, il faudrait, à mon avis, pour justifier l'utilisation d'une fonction du style de HashOf() en vue d'augmenter la vitesse globale d'exécution que la valeur renvoyée par cette fonction puisse être utilisée autrement d'abord pour compenser le ralentissement qu'elle introduit et ensuite pour aller plus vite ... mais pour ma part je ne vois pas comment.

**sjrd** · 31/05/2007, 13h57

Envoyé par Gilbert Geyer

- "en tout état de cause, tous les caractères sont considérés. Je ne comprends pas ton raisonnement." : Si tu devais coder la fonction if string1=string2 en utilisant les fonctions les plus basiques de Delphi il est certain que tu comparerais, de gauche vers la droite, deux à deux, les caractères de ces deux chaines en quittant vite la boucle dès que string1[i]<>string2[i] donc en ignorant tous les caractères situés après cet indice i. Non ?
Et en utilisant n'importe quelle fonction qui tient compte de la totalité des caractères de string1 et de string2 on augmente forcément le nombre d'opérations à effectuer ... ce qui est donc moins rapide. D'ailleurs pour me fixer les idées à ce sujet j'ai utilisé la function HashOf apportée hier par
ShaiLeTroll pour faire un test comparatif de vitesse d'éxecution entre If string1=string2 et if HashOf(string1)=HashOf(string2) avec le code suivant :

Oui, bien entendu, la comparaison par hash d'un couple de chaînes est beaucoup plus lente que la comparaison des chaînes directement.

Par contre, dans le cas présent, on doit tester un grand nombre de couples, qui mettent en jeu les mêmes chaînes.

On peut donc passer une fois sur le fichier, et stocker les positions de début de chaînes, + leur hash. Ensuite, on fait une recherche de doubles des hashes gardés en mémoire. Là on ne doit plus comparer que des integer, ce qui est de toutes façons plus rapide que de comparer deux chaînes, mêmes si celles-ci n'ont qu'un seul caractère !

Comme la recherche de doublons est en O(n²), et que la composition des hashes est O(n), c'est la recherche de doublons qui prend le pas sur de gros (et même de petits dans ce cas, je pense) fichiers.

**ShaiLeTroll** · 31/05/2007, 14h35

Personnellement, je suis en train d'écrire une fonction (en intermitance avec mon travail) et j'ai déjà prévu une fonction pour générer un fichier de 2 Go (ouais je le fait avec les fonctions delphi donc pas plus ... mais avant test sur plus petit biensur !)

D'ailleurs, pourrait-on avoir des temps et le motif de fichier pour le test qui correpond à ce temps

Pour un fichier de "880 000 octets" cela dure 2 249 ms, long non pour si peu ?

il contient ceci répété 10000 fois

Code :

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

'Ligne 0'#13#10'Ligne 1'#13#10'Ligne 1'#10'Ligne 1'#10'Ligne 0'#13#10'Ligne 1'#13#10'Ligne 6'#13#10'Ligne 7'#13#10'Ligne 8'#13#10'Ligne 9'#13#10

cela fait bcp de doublon

**Gilbert Geyer** · 31/05/2007, 16h15

Sjrd a écrit :
On peut donc passer une fois sur le fichier, et stocker les positions de début de chaînes, + leur hash. Ensuite, on fait une recherche de doubles des hashes gardés en mémoire. Là on ne doit plus comparer que des integer, ce qui est de toutes façons plus rapide que de comparer deux chaînes,...

Je suis surpris de ce raisonnement après l'exemple de tests comparatifs entre la série de
If string1 = string2 et de if HashOf(string1) = HashOf(string2) où :
- d'un coté le temps de calcul porte sur la comparaison directe des chaines,
- et de l'autre coté le temps mis englobe la comparaison des hashes ET le temps de calcul des hashes des chaines,
- et qui en plus présage qu'on pourra s'attendre à ce que l'utilisation du principe des hashes sera entre X à 80 fois plus lent que la compararaison directe des chaines.

**banban54** · 31/05/2007, 17h15

bonjour

je vais mettre mon grain de sel:
but: lire de trés gros fichiers texte, le plus rapidement possible pour chercher des lignes en double, sans charger le fichier en mémoire.

personnellement je travaillerai en binaire:
- lecture par blocs jusqu'à la fin du fichier
-- mémorisation de la position du début de ligne
-- comptage (longueur chaine) et sommation de tous les octets jusqu'au prochain crlf (en binaire).
--- mémorisation de la position du début de ligne suivante....

ensuite la recherche des doublons se fait en mémoire, si même longueur et même sommation, aux anagrammes près, on peut considérer qu'il y a doublon.
La vérification est aisée ayant les position et longueur des lignes en question.

à plus

**Gilbert Geyer** · 31/05/2007, 17h28

A ShaiLeTroll :
A propos de la conception d'un fichier pour des tests de rapidité de repérage du 1er doublon rencontré :
Tu dis que le tien, je cite :

il contient ceci répété 10000 fois

Code :
'Ligne 0'#13#10'Ligne 1'#13#10'Ligne 1'#10'Ligne 1'#10'Ligne 0'#13#10'Ligne 1'#13#10'Ligne 6'#13#10'Ligne 7'#13#10'Ligne 8'#13#10'Ligne 9'#13#10

... avec un tel fichier d'essais où l'on met un doublon dès le début du fichier on rentre dans la moulinette de comparaison des lignes pour en ressortir immédiatement et afficher le ShowMessage('ce fichier comporte un ou plusieurs doublons') quelle que soit la taille du fichier... c'est de la triche ça. Non ?

... à mon avis pour faire un fichier de tests de vitesse il vaut mieux truffer le fichier du début vers sa fin avec des lignes de faux doublons formés par des lignes de texte aléatoire et de loger un vrai-doublon dans l'avant-dernière et la dernière ligne du fichier comme par exemple ceci :

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
procedure TForm1.bCreerFichierAleatoireClick(Sender: TObject);
label     PasBon;
var       FS : TFileStream; NomFichier,sTailleMo,LigAl,invite : string;
          TailleOc,code : integer; ChronoC : oChrono;
 
          function LgAleat : integer; // Longueur Aléatoire
          begin    Result:=Random(98); end;
 
          function LigneAleat(Lg : integer) : string; // Texte Aléatoire
          var      i : integer;
          begin    Result:='';
                   for i:=1 to Lg
                   do Result:=Result + chr(67 +Random(26));
          end;
 
begin     NomFichier:=edNomFichier.text;
          if FileExists(NomFichier)
          then begin sms(NomFichier+' : Existe déjà. Autre nom'); EXIT; end;
          FS := TFileStream.Create(NomFichier, fmCreate);
          invite := 'Entrer sa taille en Mo : ';
        PasBon :
          sTailleMo:= InputBox('Créer Fichier Aleatoire + Doublons', invite, '');
          val(sTailleMo,TailleOc,code);
          if code<>0 then
          begin invite:='... taille en Mo = valeur entière :'; goto PasBon; end;
          Sablier;
          ChronoC.Top(Edit1);
          TailleOc := TailleOc*1024*1024;
          Randomize;
 
          repeat LigAl:=LigneAleat(LgAleat)+#13#10;
                 FS.Write(PChar(LigAl)^, length(LigAl));
          until FS.Size >= TailleOc;
          LigAl:='<<< MI-DOUBLON >>>'+#13#10;
          FS.Write(PChar(LigAl)^, length(LigAl));
          FS.Write(PChar(LigAl)^, length(LigAl));
          ChronoC.Mis;
          Sablier;
end;

... ayant généré un tel fichier de 10Mo (pour pouvoir le visualiser d'abord dans un traitement de texte pour vérifier que sa création s'est bien passée avant de l'utiliser ) pour un test, mon appli m'a signalé que le fichier contenait 205581 lignes non vides et autant de lignes de même longueur sachant que lignes-de-même-longueur est un raccourci de langage pour désigner les lignes-qui-prises-deux-à-deux ont la même longueur alors que le reste est aléatoire sauf le doublon de fin de fichier .
(des lignes de texte aléatoires en contenu et en longueur bridée par un Random(98); finissent forcément par avoir une homologue de même-longueur dans un fichier de plusieurs Mo)
:

Code :

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

1
2
3
4
5
6
7
8
9
10
c:\Doublons10Mo.txt
Taille : 10485803 Octets
Nombre de lignes : 207760                 ReleveTopo : mis : 180 ms
 
Reste : 205581 lignes non vides           Longueurs : mis : 7366 ms
 
Reste lignes même longueur = 205581       PoserFlags : mis : 873269 ms
                                          --------------------------
                                          Total :  880815 ms = 14.6 min
Les différentes étapes chronométrées ici ne tiennent pas encore compte du temps que prendra la comparaison des chaines de faux-doublons avant de trouver le vrai-doublon logé à la fin du fichier.

Tiens, banban54 vient d'intercaler un message pendant que j'achève le mien, mais stop pour aujourd'hui.

A+

**sjrd** · 31/05/2007, 17h30

Envoyé par Gilbert Geyer

Je suis surpris de ce raisonnement après l'exemple de tests comparatifs entre la série de
If string1 = string2 et de if HashOf(string1) = HashOf(string2) où :
- d'un coté le temps de calcul porte sur la comparaison directe des chaines,
- et de l'autre coté le temps mis englobe la comparaison des hashes ET le temps de calcul des hashes des chaines,
- et qui en plus présage qu'on pourra s'attendre à ce que l'utilisation du principe des hashes sera entre X à 80 fois plus lent que la compararaison directe des chaines.

Je crois que tu as mal compris moin raisonnement. Je n'émets aucun doute quant à ce que 10 000 000 de

Code :

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

if HashOf(s1) = HashOf(s2) then

soit bien plus lent que 10 000 000 de

Code :

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

if s1 = s2 then

Seulement, ici, tu ne te replaces pas dans le contexte du problème. Dans ce contexte, on doit à plusieurs reprises traiter la même chaîne.

Donc on ne fait pas autant de HashOf qu'on ne fait de comparaisons : on en fait seulement un nombre égal au nombre de lignes du fichier. Et après on teste les hashes déjà calculés et mémorisés, et on fait donc n*(n-1)/2 comparaisons de hashes, pour seulement n calculs de hashes.

En code ça doit donner qqch comme ça (pas testé) :

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
type
  TLineInfo = record
    Position : Int64;
    Hash : integer;
  end;
 
function ReadStrFromStream(Stream : TStream) : string;
var C : Char;
begin
  Result := '';
  C := #0;
  while (Stream.Read(C, 1) > 0) and (C <> #13) and (C <> #10) do
    Result := Result+C;
  if C = #13 then
    Stream.Read(C, 1);
end;
 
procedure TestDoublons(Stream : TStream);
const
  AllocBy = 1024;
var LinesInfo : array of TLineInfo;
    I, J, LineCount, LineNumber : integer;
begin
  LineCount := 0;
  LineNumber := 0;
  while Stream.Position < Stream.Size do
  begin
    if LineCount = Length(LinesInfo) then
      SetLength(LinesInfo, LineCount+AllocBy);
    with LinesInfo[LineNumber] do
    begin
      Position := Stream.Position;
      Hash := HashOf(ReadStrFromStream(Stream));
    end;
  end;
  SetLength(LinesInfo, LineCount);
 
  for I := 0 to LineCount-2 do for J := I+1 to LineCount-1 do
  begin
    if LinesInfo[i].Hash = LinesInfo[J].Hash then
      WriteLn('Doublon de hases trouvé entre ligne ',
        I, ' (pos ', LinesInfo[i].Position, ') et ligne ',
        J, ' (pos ', LinesInfo[J].Position, ')');
  end;
end;

**ShaiLeTroll** · 31/05/2007, 17h30

Bon voici, un code fonctionnel, qui exploite les différentes, idées, il est a noté que le calcul CheckSum prend du temps (cela double le temps en fait, la recherche des lignes étant 3% du temps total) et le fait d'exploiter ce CheckSum fait revenir le temps à celui d'une comparaison simple, ceci sur le fichier de test expliqué dans mon message précédent

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
type
  TSearchDuplicatesLineIndexes = class(TStringList)
  private
    function GetInteger(IndexLine, IndexInteger: Integer): Integer;
    procedure PutInteger(IndexLine, IndexInteger: Integer; const Value: Integer);
    function GetCountInteger(IndexLine: Integer): Integer;
  public
    procedure Clear; override;
    function AddInteger(const Line: string; Value: Integer): Integer; overload;
    procedure AddInteger(IndexLine, Value: Integer); overload;
    property CountInteger[IndexLine: Integer]: Integer read GetCountInteger;
    property Integers[IndexLine, IndexInteger: Integer]: Integer read GetInteger write PutInteger;
  end;
 
function SearchDuplicatesLines(const FileName: string; Duplicates: TSearchDuplicatesLineIndexes): Integer;
type
  PInt64Rec = ^Int64Rec;
  TOffsetLine = record
    BeginOffSet: Int64;
    LineLength: Integer;
    EndOffSet: Int64;
    Is13: Boolean;
    Is10: Boolean;
    Skip: Boolean;
    DuplicateIndex: Integer;
    CheckSum: Int64;
  end;
var
  OffSetLines: Array of TOffsetLine;
 
  procedure CreateLineOffSet();
  const
     BUF_SIZE: Integer = 32000;
  var
    FileHandle: Integer;
    FileLength: Int64;
    SearchBuf, RememberBuf: array of Byte;
    iSearchBufPos, iReaded: Int64;
    AmtTransferred, RememberLen: Integer;
    CurrentOSL: TOffsetLine;
 
    procedure NewOSL(AOffSet: Int64);
    var
      I, ICS, BO: Integer;
      pCS: PInt64Rec;
      WordByte: Word;
    begin
      SetLength(OffSetLines, Length(OffSetLines) + 1);
      CurrentOSL.EndOffSet := AOffSet;
      CurrentOSL.LineLength := CurrentOSL.EndOffSet - CurrentOSL.BeginOffSet + 1;
      if CurrentOSL.Is13 then Dec(CurrentOSL.LineLength);
      if CurrentOSL.Is10 then Dec(CurrentOSL.LineLength);
      ICS := 0;
      pCS := PInt64Rec(@CurrentOSL.CheckSum);
      for I := 0 to RememberLen - 1 do
      begin
        pCS.Bytes[ICS] := (pCS.Bytes[ICS] + RememberBuf[I]) and $000000FF;
        Inc(ICS);
        if ICS = 8 then
          ICS := 0;
      end;
      if RememberLen > 0 then
        BO := 0
      else
        BO := CurrentOSL.BeginOffSet - iReaded;
      for I := BO to BO + CurrentOSL.LineLength - RememberLen do
      begin
        pCS.Bytes[ICS] := (pCS.Bytes[ICS] + SearchBuf[I]) and $000000FF;
        Inc(ICS);
        if ICS = 8 then
          ICS := 0;
      end;
 
      OffSetLines[High(OffSetLines)] := CurrentOSL;
      ZeroMemory(@CurrentOSL, SizeOf(CurrentOSL));
      CurrentOSL.BeginOffSet := AOffSet + 1;
      CurrentOSL.DuplicateIndex := -1;
      RememberLen := 0;
    end;
 
  begin
     SetLength(SearchBuf, BUF_SIZE);
     SetLength(RememberBuf, BUF_SIZE);
     RememberLen := 0;
 
     Result := 0;
     iReaded := 0;
     FileLength := 0;
     ZeroMemory(@CurrentOSL, SizeOf(CurrentOSL));
     CurrentOSL.DuplicateIndex := -1;
 
     FileHandle := FileOpen(FileName, fmOpenRead);
     try
        FileLength := FileSeek(FileHandle, FileLength, FILE_END);
        FileSeek(FileHandle, 0, FILE_BEGIN);
 
        while iReaded < FileLength do
        begin
           AmtTransferred := FileRead(FileHandle, SearchBuf[0], BUF_SIZE); // [0] parce que c'est un tableau dynamique
           iSearchBufPos := 0;
 
           if iReaded > 0 then
           begin
             if CurrentOSL.Is13 then
             begin
               CurrentOSL.Is10 := SearchBuf[iSearchBufPos] = 10;
               if CurrentOSL.Is10 then
               begin
                 NewOSL(iReaded+iSearchBufPos);
                 Inc(iSearchBufPos);
               end;
             end;
           end;
 
           while iSearchBufPos < AmtTransferred do
           begin
              CurrentOSL.Is13 := SearchBuf[iSearchBufPos] = 13;
              if CurrentOSL.Is13 then
              begin
                Inc(iSearchBufPos);
                if iSearchBufPos < AmtTransferred then
                begin
                  CurrentOSL.Is10 := SearchBuf[iSearchBufPos] = 10;
                  if not CurrentOSL.Is10 then
                    Dec(iSearchBufPos);
                  NewOSL(iReaded+iSearchBufPos);
                end;
              end else
              begin
                CurrentOSL.Is10 := SearchBuf[iSearchBufPos] = 10;
                if CurrentOSL.Is10 then
                begin
                  NewOSL(iReaded+iSearchBufPos);
                end;
              end;
 
              Inc(iSearchBufPos);
           end;
 
           RememberLen := AmtTransferred - CurrentOSL.BeginOffSet + iReaded;
           if RememberLen > 0 then
             CopyMemory(@RememberBuf[0], @SearchBuf[CurrentOSL.BeginOffSet - iReaded], RememberLen);
 
           Inc(iReaded, AmtTransferred);
        end;
        if (FileLength > 0) and not (CurrentOSL.Is13 or CurrentOSL.Is10) then
          NewOSL(FileLength - 1);
     finally
        FileClose(FileHandle);
     end;
  end;
 
  procedure CompareLength();
  var
    iOSL, iOSLSub: Integer;
  begin
    for iOSL := Low(OffSetLines) to High(OffSetLines) - 1 do
    begin
      OffSetLines[iOSL].Skip := True;
      for iOSLSub := iOSL + 1 to High(OffSetLines) do
      begin
        if (OffSetLines[iOSL].LineLength = OffSetLines[iOSLSub].LineLength)
        and (OffSetLines[iOSL].CheckSum = OffSetLines[iOSLSub].CheckSum) then
        begin
          OffSetLines[iOSL].Skip := False;
          Break;
        end;
      end;
    end;
  end;
 
  procedure CompareStrings();
  var
     FileHandle: Integer;
     FileLength, FilePosition: Int64;
     Buf, BufSub: string;
     BufLen: Integer;
     iOSL, iOSLSub: Integer;
  begin
     FileHandle := FileOpen(FileName, fmOpenRead);
     try
 
        for iOSL := Low(OffSetLines) to High(OffSetLines) - 1 do
        begin
          if OffSetLines[iOSL].Skip then
            Continue;
 
          BufLen := OffSetLines[iOSL].LineLength;
          SetLength(Buf, BufLen);
          SetLength(BufSub, BufLen);
 
          FileSeek(FileHandle, OffSetLines[iOSL].BeginOffSet, FILE_BEGIN);
          FileRead(FileHandle, Buf[1], BufLen);
 
          for iOSLSub := iOSL + 1 to High(OffSetLines) do
          begin
            if OffSetLines[iOSLSub].Skip then
              Continue;
 
            if OffSetLines[iOSL].LineLength = OffSetLines[iOSLSub].LineLength then
            begin
              FileSeek(FileHandle, OffSetLines[iOSLSub].BeginOffSet, FILE_BEGIN);
              FileRead(FileHandle, BufSub[1], BufLen);
 
              // if CompareMem(@Buf[1], @BufSub[1], BufLen) then
              if Buf = BufSub then
              begin
                OffSetLines[iOSLSub].Skip := True;
                if OffSetLines[iOSL].DuplicateIndex < 0 then
                  OffSetLines[iOSL].DuplicateIndex := Duplicates.AddInteger(Buf, iOSL);
 
                // Duplicates.AddInteger(OffSetLines[iOSL].DuplicateIndex, iOSLSub);
              end;
            end;
          end;
 
          SetLength(Buf, 0);
          SetLength(BufSub, 0);
        end;
     finally
        FileClose(FileHandle);
     end;
  end;
 
begin
  Result := -1;
  if not Assigned(Duplicates) then
    Exit;
 
  CreateLineOffSet();
  //CompareLength();
  CompareStrings();
 
  Result := Duplicates.Count;
end;
 
{ TSearchDuplicatesLineIndexes }
 
procedure TSearchDuplicatesLineIndexes.Clear;
var
  I: Integer;
begin
  for I := 0 to Count - 1 do
    if Assigned(Objects[I]) then
      Objects[I].Free();
 
  inherited Clear();
end;
 
function TSearchDuplicatesLineIndexes.AddInteger(const Line: string; Value: Integer): Integer;
begin
  Result := IndexOf(Line);
  if Result < 0 then
    Result := AddObject(Line, TList.Create());
 
  TList(Objects[Result]).Add(Pointer(Value));
end;
 
procedure TSearchDuplicatesLineIndexes.AddInteger(IndexLine, Value: Integer);
begin
  TList(Objects[IndexLine]).Add(Pointer(Value));
end;
 
function TSearchDuplicatesLineIndexes.GetInteger(IndexLine, IndexInteger: Integer): Integer;
begin
  Result := Integer(TList(Objects[IndexLine]).Items[IndexInteger]);
end;
 
procedure TSearchDuplicatesLineIndexes.PutInteger(IndexLine, IndexInteger: Integer; const Value: Integer);
begin
  TList(Objects[IndexLine]).Items[IndexInteger] := Pointer(Value);
end;
 
function TSearchDuplicatesLineIndexes.GetCountInteger(IndexLine: Integer): Integer;
begin
  Result := TList(Objects[IndexLine]).Count;
end;
 
{ TSearchDuplicatesLineIndexes - END }

Ce qui ce est à adapter c'est les appels de tests

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
procedure TFrmTestFichier.BtnRechercheDoublonClick(Sender: TObject);
var
  Duplicates: TSearchDuplicatesLineIndexes;
  iDup, iIndex: Integer;
  TimeIteration: Integer;
  StartTick, EndTick, TickPerSec: Int64;
begin
  Duplicates := TSearchDuplicatesLineIndexes.Create();
  try
    QueryPerformanceCounter(StartTick);
    try
      SearchDuplicatesLines(EdPathFileCompare.Text, Duplicates);
    finally
      QueryPerformanceCounter(EndTick);
      QueryPerformanceFrequency(TickPerSec);
      TimeIteration := Round((EndTick - StartTick) / TickPerSec * 1000);
    end;
    MemoDoublons.Lines.BeginUpdate();
    try
      MemoDoublons.Clear();
      MemoDoublons.Lines.Add('SearchDuplicatesLines : ' + IntToStr(TimeIteration) + ' ms');
      for iDup := 0 to Duplicates.Count - 1 do
      begin
        MemoDoublons.Lines.Add(Duplicates.Strings[iDup]);
        for iIndex := 0 to Duplicates.CountInteger[iDup] - 1 do
          MemoDoublons.Lines.Add(IntToStr(Duplicates.Integers[iDup, iIndex]));
      end;
    finally
      MemoDoublons.Lines.EndUpdate();
    end;
  finally
    Duplicates.Free();
  end;
end;
 
procedure TFrmTestFichier.BtnCreationDoublonClick(Sender: TObject);
const
  BUF = 'Ligne 0'#13#10'Ligne 1'#13#10'Ligne 1'#10'Ligne 1'#10'Ligne 0'#13#10'Ligne 1'#13#10'Ligne 6'#13#10'Ligne 7'#13#10'Ligne 8'#13#10'Ligne 9'#13#10;
var
  FileToFill: File;
  IFTF: Integer;
begin
  AssignFile(FileToFill, EdPathFileCompare.Text);
  try
    Rewrite(FileToFill, Length(BUF));
    for IFTF := 0 to 99999 do
      BlockWrite(FileToFill, BUF, 1);
  finally
     CloseFile(FileToFill);
  end;
end;

**ShaiLeTroll** · 31/05/2007, 17h32

Envoyé par Gilbert Geyer

avec un tel fichier d'essais où l'on met un doublon dès le début du fichier on rentre dans la moulinette de comparaison des lignes pour en ressortir immédiatement et afficher le ShowMessage('ce fichier comporte un ou plusieurs doublons') quelle que soit la taille du fichier... c'est de la triche ça. Non ?

Ma Fonction fait une analyse TOTALE du fichier ^_^, je me limite pas au premier doublon, mais cela indique pour chaque chaine, la liste des lignes où l'on trouve cette chaine, et mon fichier contient des lignes de même taille pour forcer le teste de Check (le test via longueur étant favorisé par le random, hors celui-ci on sait qu'il est performant, et c'est le Hash que je cherchais à estimer en puissance ...)

**Gilbert Geyer** · 31/05/2007, 17h46

Comme les messages datés aujourd'hui entre 17h15 et 17h32 ont tous été rédigés presque en parallèle avec mon message précédent, vu l'heure stop pour aujourd'hui, et à demain.

**CapJack** · 31/05/2007, 17h59

Gilber Geyer, je crois que tu n'as pas compris une donnée importante du problème : on part de l'hypothèse que le fichier est beaucoup trop gros pour être chargé en mémoire, ce qui entraîne que les comparaisons de chaînes devraient se faire obligatoirement sur disque.

Par contre, on fait l'hypothèse qu'on pourra charger en mémoire une hash list, plus longue à calculer mais moins volumineuse et faisant gagner un temps précieux par la suite, une fois calculée.

D'ailleurs tu commets une erreur de taille : tu compares "if s1 = s2" avec "if hash(s1) = hash(s2)", ce qui prouve bien que tu n'as pas compris le principe : les hash sont calculées d'abord, en une seule fois, et stockées dans un tableau. Ensuite, on les compare.

D'autres t'ont répondu en détail : réfléchis à leurs réponses !

Content que mon idée de somme de contrôle ait rencontré la quasi-unanimité (même celle de Gilbert Geyer, quand il aura compris le pourquoi de la chose

).

**ShaiLeTroll** · 31/05/2007, 18h22

Le plus drôle, c'est que j'ai réussi à exploser finalement mémoire ... pour quelle raison !

mon fichier contient des lignes de 7 caractères, pour chaque ligne, j'ai une structure TOffsetLine (voir code ci dessus) mais qui occupe pour sauvegader l'offset de début en Int64 pour dépasser la limite de 2Go du Integer, et quelques autres éléments pour optimiser ... au final, je me retrouve donc avec 36 octets pour une ligne donc plus que la taille de la ligne, conséquence mon mapping de fichier est plus volumineux que mon fichier, ... il faudrait avoir moins de chose en mémoire, mais les éléments que je peux supprimer sont ceux qui occupent peu de place comme les booleens ... je pourrais avoir un CheckSum sur 4 au lieu de 8 mais cela ne changera pas grand chose, ... car il nous faut quoi obligatoirement

Code :

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

1
2
3
    BeginOffSet: Int64;
    LineLength: Integer;
    CheckSum: Integer;

Ce qui fait déjà 16o ... et en fait, je ne descend pas sous 21 pour les besoins de mon algo ...

CONCLUSION
il faut faire un algo sans mémorisation des offets, il faut simplement remplacer le ReadLn par un FileRead (API) pour dépasser les 2Go ... ce serait lent mais économe en mémoire

voici quand même un algo modifié pour économiser de la mémoire

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
type
  TSearchDuplicatesLineIndexes = class(TStringList)
  private
    function GetInteger(IndexLine, IndexInteger: Integer): Integer;
    procedure PutInteger(IndexLine, IndexInteger: Integer; const Value: Integer);
    function GetCountInteger(IndexLine: Integer): Integer;
  public
    procedure Clear; override;
    function AddInteger(const Line: string; Value: Integer): Integer; overload;
    procedure AddInteger(IndexLine, Value: Integer); overload;
    property CountInteger[IndexLine: Integer]: Integer read GetCountInteger;
    property Integers[IndexLine, IndexInteger: Integer]: Integer read GetInteger write PutInteger;
  end;
 
function SearchDuplicatesLines(const FileName: string; Duplicates: TSearchDuplicatesLineIndexes): Integer;
type
  PLongRec = ^LongRec;
  TOffsetLine = packed record
    BeginOffSet: Int64;
    LineLength: Integer;
    Skip: Boolean;
    DuplicateIndex: Integer;
    CheckSum: Integer;
  end;
  TOffsetLineEx = packed record
    BeginOffSet: Int64;
    LineLength: Integer;
    Skip: Boolean;
    DuplicateIndex: Integer;
    CheckSum: Integer;
    EndOffSet: Int64;
    Is13: Boolean;
    Is10: Boolean;
  end;
var
  OffSetLines: Array of TOffsetLine;
 
  procedure CreateLineOffSet();
  const
     BUF_SIZE: Integer = 32000;
  var
    FileHandle: Integer;
    FileLength: Int64;
    SearchBuf, RememberBuf: array of Byte;
    iSearchBufPos, iReaded: Int64;
    AmtTransferred, RememberLen: Integer;
    CurrentOSL: TOffsetLineEx;
 
    procedure NewOSL(AOffSet: Int64);
    var
      I, ICS, BO: Integer;
      pCS: PLongRec;
      WordByte: Word;
    begin
      SetLength(OffSetLines, Length(OffSetLines) + 1);
      CurrentOSL.EndOffSet := AOffSet;
      CurrentOSL.LineLength := CurrentOSL.EndOffSet - CurrentOSL.BeginOffSet + 1;
      if CurrentOSL.Is13 then Dec(CurrentOSL.LineLength);
      if CurrentOSL.Is10 then Dec(CurrentOSL.LineLength);
      ICS := 0;
      pCS := PLongRec(@CurrentOSL.CheckSum);
      for I := 0 to RememberLen - 1 do
      begin
        pCS.Bytes[ICS] := (pCS.Bytes[ICS] + RememberBuf[I]) and $000000FF;
        Inc(ICS);
        if ICS = 4 then
          ICS := 0;
      end;
      if RememberLen > 0 then
        BO := 0
      else
        BO := CurrentOSL.BeginOffSet - iReaded;
      for I := BO to BO + CurrentOSL.LineLength - RememberLen do
      begin
        pCS.Bytes[ICS] := (pCS.Bytes[ICS] + SearchBuf[I]) and $000000FF;
        Inc(ICS);
        if ICS = 4 then
          ICS := 0;
      end;
 
      CopyMemory(@OffSetLines[High(OffSetLines)], @CurrentOSL, SizeOf(TOffsetLine));
      ZeroMemory(@CurrentOSL, SizeOf(CurrentOSL));
      CurrentOSL.BeginOffSet := AOffSet + 1;
      CurrentOSL.DuplicateIndex := -1;
      RememberLen := 0;
    end;
 
  begin
     SetLength(SearchBuf, BUF_SIZE);
     SetLength(RememberBuf, BUF_SIZE);
     RememberLen := 0;
 
     Result := 0;
     iReaded := 0;
     FileLength := 0;
     ZeroMemory(@CurrentOSL, SizeOf(CurrentOSL));
     CurrentOSL.DuplicateIndex := -1;
 
     FileHandle := FileOpen(FileName, fmOpenRead);
     try
        FileLength := FileSeek(FileHandle, FileLength, FILE_END);
        FileSeek(FileHandle, 0, FILE_BEGIN);
 
        while iReaded < FileLength do
        begin
           AmtTransferred := FileRead(FileHandle, SearchBuf[0], BUF_SIZE); // [0] parce que c'est un tableau dynamique
           iSearchBufPos := 0;
 
           if iReaded > 0 then
           begin
             if CurrentOSL.Is13 then
             begin
               CurrentOSL.Is10 := SearchBuf[iSearchBufPos] = 10;
               if CurrentOSL.Is10 then
               begin
                 NewOSL(iReaded+iSearchBufPos);
                 Inc(iSearchBufPos);
               end;
             end;
           end;
 
           while iSearchBufPos < AmtTransferred do
           begin
              CurrentOSL.Is13 := SearchBuf[iSearchBufPos] = 13;
              if CurrentOSL.Is13 then
              begin
                Inc(iSearchBufPos);
                if iSearchBufPos < AmtTransferred then
                begin
                  CurrentOSL.Is10 := SearchBuf[iSearchBufPos] = 10;
                  if not CurrentOSL.Is10 then
                    Dec(iSearchBufPos);
                  NewOSL(iReaded+iSearchBufPos);
                end;
              end else
              begin
                CurrentOSL.Is10 := SearchBuf[iSearchBufPos] = 10;
                if CurrentOSL.Is10 then
                begin
                  NewOSL(iReaded+iSearchBufPos);
                end;
              end;
 
              Inc(iSearchBufPos);
           end;
 
           RememberLen := AmtTransferred - CurrentOSL.BeginOffSet + iReaded;
           if RememberLen > 0 then
             CopyMemory(@RememberBuf[0], @SearchBuf[CurrentOSL.BeginOffSet - iReaded], RememberLen);
 
           Inc(iReaded, AmtTransferred);
        end;
        if (FileLength > 0) and not (CurrentOSL.Is13 or CurrentOSL.Is10) then
          NewOSL(FileLength - 1);
     finally
        FileClose(FileHandle);
     end;
  end;
 
  procedure CompareLength();
  var
    iOSL, iOSLSub: Integer;
  begin
    for iOSL := Low(OffSetLines) to High(OffSetLines) - 1 do
    begin
      OffSetLines[iOSL].Skip := True;
      for iOSLSub := iOSL + 1 to High(OffSetLines) do
      begin
        if (OffSetLines[iOSL].LineLength = OffSetLines[iOSLSub].LineLength)
        and (OffSetLines[iOSL].CheckSum = OffSetLines[iOSLSub].CheckSum) then
        begin
          OffSetLines[iOSL].Skip := False;
          Break;
        end;
      end;
    end;
  end;
 
  procedure CompareStrings();
  var
     FileHandle: Integer;
     FileLength, FilePosition: Int64;
     Buf, BufSub: Array of Byte;
     BufStr: string;
     BufLen: Integer;
     iOSL, iOSLSub: Integer;
  begin
     FileHandle := FileOpen(FileName, fmOpenRead);
     try
        for iOSL := Low(OffSetLines) to High(OffSetLines) - 1 do
        begin
          if OffSetLines[iOSL].Skip then
            Continue;
 
          BufLen := OffSetLines[iOSL].LineLength;
          SetLength(Buf, BufLen);
          FileSeek(FileHandle, OffSetLines[iOSL].BeginOffSet, FILE_BEGIN);
          FileRead(FileHandle, Buf[1], BufLen);
 
          SetLength(BufStr, BufLen);
          CopyMemory(@BufStr[1], @Buf[1], BufLen);
 
          SetLength(BufSub, BufLen);
 
          for iOSLSub := iOSL + 1 to High(OffSetLines) do
          begin
            if OffSetLines[iOSLSub].Skip then
              Continue;
 
            if OffSetLines[iOSL].LineLength = OffSetLines[iOSLSub].LineLength then
            begin
              FileSeek(FileHandle, OffSetLines[iOSLSub].BeginOffSet, FILE_BEGIN);
              FileRead(FileHandle, BufSub[1], BufLen);
 
              if CompareMem(@Buf[1], @BufSub[1], BufLen) then
              //if Buf = BufSub then
              begin
                OffSetLines[iOSLSub].Skip := True;
                if OffSetLines[iOSL].DuplicateIndex < 0 then
                  OffSetLines[iOSL].DuplicateIndex := Duplicates.AddInteger(BufStr, iOSL);
 
                Duplicates.AddInteger(OffSetLines[iOSL].DuplicateIndex, iOSLSub);
              end;
            end;
          end;
 
          SetLength(Buf, 0);
          BufStr := '';
          SetLength(BufSub, 0);
        end;
     finally
        FileClose(FileHandle);
     end;
  end;
 
begin
  Result := -1;
  if not Assigned(Duplicates) then
    Exit;
 
  CreateLineOffSet();
  //CompareLength();
  CompareStrings();
 
  Result := Duplicates.Count;
end;
 
{ TSearchDuplicatesLineIndexes }
 
procedure TSearchDuplicatesLineIndexes.Clear;
var
  I: Integer;
begin
  for I := 0 to Count - 1 do
    if Assigned(Objects[I]) then
      Objects[I].Free();
 
  inherited Clear();
end;
 
function TSearchDuplicatesLineIndexes.AddInteger(const Line: string; Value: Integer): Integer;
begin
  Result := IndexOf(Line);
  if Result < 0 then
    Result := AddObject(Line, TList.Create());
 
  TList(Objects[Result]).Add(Pointer(Value));
end;
 
procedure TSearchDuplicatesLineIndexes.AddInteger(IndexLine, Value: Integer);
begin
  TList(Objects[IndexLine]).Add(Pointer(Value));
end;
 
function TSearchDuplicatesLineIndexes.GetInteger(IndexLine, IndexInteger: Integer): Integer;
begin
  Result := Integer(TList(Objects[IndexLine]).Items[IndexInteger]);
end;
 
procedure TSearchDuplicatesLineIndexes.PutInteger(IndexLine, IndexInteger: Integer; const Value: Integer);
begin
  TList(Objects[IndexLine]).Items[IndexInteger] := Pointer(Value);
end;
 
function TSearchDuplicatesLineIndexes.GetCountInteger(IndexLine: Integer): Integer;
begin
  Result := TList(Objects[IndexLine]).Count;
end;
 
{ TSearchDuplicatesLineIndexes - END }

J'en suis à 966 ms pour 880 000 octets ...

Je vais dupliqué ma fonction SearchStringInFile en SearchStringInBigFile et l'utliser pour la recherche ...

EDIT : Pour un Algo pas terrible, j'en suis à 8 227 ms, c'est nettement plus lent ... mais bon cela reste possible ...

**CapJack** · 01/06/2007, 09h03

2 autres idées :

1) Sauvegarder les structures d'info (offsets, etc.) dans un fichier typé, ne charger en mémoire que les hashes. L'accès à un élément quelconque d'un fichier typé est très rapide, et il y en a de toute façon peu pendant la comparaison, uniquement en cas de risque de "fausse égalité".

2) Utiliser un hash sur 16 bits au lieu de 32 bits. Certes, cela augmente la probabilité de "fausse égalité", mais dans des proportions sans doute acceptables ? Il faudrait faire des essais. Je m'en veux de ne pas avoir le temps d'implémenter.

Bonne journée à tous !

**sovitec** · 01/06/2007, 10h09

Envoyé par CapJack

2) Utiliser un hash sur 16 bits au lieu de 32 bits. Certes, cela augmente la probabilité de "fausse égalité", mais dans des proportions sans doute acceptables ? Il faudrait faire des essais.

Le "paradoxe des anniversaires" stipule que le risque de collision devient nom négligeable lorsque l'on a un nombre d'élément de l'ordre de la racine carrée de la taille du hash. Soit de l'ordre de quelques centaines pour un hash 16 bits, et quelques dizaines de milliers pour un hash 32 bits.

Si la taille des lignes est assez grande devant un hash 128 bits on peut utiliser l'algorithme suivant inspirer de la recherche de doublon de fichiers et qui ressemble pas mal à celui de CapJack.

(L'algorithme suivant suppose que l'on ne conserve que le premier élément lorsqu'il existe un doublon, sinon il faut gérer une structure supplémentaire):

Code :

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

1
2
3
4
5
 
Pour chaque ligne
  Calculer le md5 de la ligne (O(1) en général)
  Insérer hash dans une hashtable (O(log(n))
  Si la ligne existe déjà dans la hashtable alors supprimer la ligne.

C'est du O(n.log(n)) et peut être très rapide s'il y a beaucoup de doublons ou des lignes très longues.

**Gilbert Geyer** · 01/06/2007, 16h44

Bonjour,

1) Je suis d’accord avec Sjrd qui écrit (message d’Hier 17h30) qu’ «on fait donc n*(n-1)/2 comparaisons de hashes, pour seulement n calculs de hashes » mais uniquement dans le cas où l’on serait obligés d’identifier la totalité des doublons présents dans les fichiers dont les noms figurent dans la StringList nommée 'fichiers' dans le code qu’Art19 a joint à son message du 25/05 20h25, qui illustre son besoin sous l’angle de son utilisation. Or, voiçi l’extrait de son code où Art19 lui même quitte les boucles dès la détection du premier doublon et aucun de ses messages ne précise qu’il en veut davantage : il se contente de repérer le nom des fichiers[i] qui contiennent un ou plusieurs doublons.

Code :

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

1
2
3
4
5
6
Art19 25/05 20h25 :
          if s = lignes[j] then begin
            memo1.Lines.Add( 'le fichier '+fichiers[i]+' contient un ou plusieurs doublon(s)' );
            flag := 1;
            break;
          end;

Ce point de vue était présent dans mon esprit lorsque (mon message d’hier 17h28) je faisais mes remarques à ShaiLeTroll à propos du contenu de son fichier utilisé pour les tests de rapidité et où la présence de doublons en entrée de fichier aurait donc évidemment faussé les conclusions … remarques à l’origine d’un deuxième malentendu issu de nos différences d’interprétation des exigences d’Art19

Conclusion d’étape : En conséquence, et sauf avis contraire d’Art19 je pencherais plutôt en faveur d’un code optimisé pour l’identification la plus rapide possible du premier-doublon-logé-n’importe-où dans un gros fichier et en économisant au max la mem-vive … et pour passer le plus vite au fichier suivant …imaginez les gains de temps d’exécution pour toute la série de gros fichiers d’Art19.

A CapJack /msg d’Hier, 19h59 :

Rassure-toi tout le monde a très bien pigé dès le départ qu’il s’agissait de fichiers trop gros pour être chargés en mémoire … ce qui entraîne que l’on ne charge en mémoire que le strict minimum que j’avais d’ailleurs nommé dès le départ de façon imagée « le tableau du relevé topographique du fichier ».

Ma boucle de comparaisons des "if s1 = s2" avec "if hash(s1) = hash(s2)" prouve surtout que je ne voulais pas me casser la tête pour avoir une idée approximative sur la différence des vitesses élémentaires d’exécution avant de faire plus compliqué.

A propos d’une somme de contrôle : Ce qui est certain à l’unanimité c’est que Hash(string) est bigrement plus significatif du contenu d’une chaîne qu’un Length(string). Par contre pour ce qui est d’avoir la certitude d’un gain-global de vitesse d’exécution par rapport a des "if s1 = s2" directs cela reste à prouver par des essais significatifs.

A ShaiLeTroll :T’as fait un sacré boulot en peu de temps : chapeau.
Mais pourquoi t’es-tu fixé comme contrainte de brider à seulement 7 caractères la longueur de chaque ligne de ton fichier d’essai vu, qu’à taille égale de fichier, ceci a pour conséquence d’augmenter inutilement le nombre de lignes du fichier avec les problèmes que cela pose … car si dans les fichiers d’Art19 les lignes de 7 caractères seulement ne représentaient qu’une minorité dans une majorité de lignes nettement plus longues on se sanctionne pour rien. Sur ce 2ème point l’avis d’Art19 serait également bien utile … et, sauf précision de sa part on peut en conclure que le contenu de ses fichiers peut être tout et n’importe quoi c’est à dire caractérisé par l’aléatoire en conséquence de quoi les essais les plus réalistes (= se rapprochant le plus des besoins d’Art19) devraient être effectués avec un fichier à contenu aléatoire. Faut pas être plus royaliste que le roi. Non ?

D’ailleurs d’une façon plus générale ce serait pas mal qu’Art19 participe à la discussion cela permettrait de clarifier bon nombres d’aspects.

**ShaiLeTroll** · 04/06/2007, 11h22

Merci, quand un sujet m'intéresse, j'aime bien pondre des trucs sympa ...
Pour la longueur de chaine, peu importe le fichier, le but était de faire ce "relevé topographique", et le fait d'avoir bcp de ligne en répétition était parce j'ai utilisé une fonction que j'avais déjà faite ... ensuite, effectivement, je n'ai pas fait attention qu'il y avait une taille moyenne de ligne indiqué par Art19 ... en fait, j'ai pris ce type de données car elles sont extrèmes justement, et j'aurais du réfléchir bien avant que le relevé était plus gros que la donnée ... sinon effectivement Art19, reviens, ... car si le but est juste de trouver le premier couple de doublon, seulement, l'algo est très simple ...

**banban54** · 04/06/2007, 12h03

bonjour

comme je ne connais pas les "Hash" ou "HashOf" (mon aide D6 me donne rien là dessus), j'ai pondu ce code qui permet de compter les supposés doublons d'un fichier texte.

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
 
 
var
  Form1: TForm1;
  PosDebutLigne    : array of int64;  // en réserve = filepos
  LongEtCheksum    : array of array[1..2] of integer;
  DejaDoublon      : array of boolean;
  BlocLecture      : array[1..20] of byte;
 
implementation
 
{$R *.dfm}
 
procedure TForm1.Button1Click(Sender: TObject);
var
Fromfic    : file of byte;
NumRead, NbLignes, NbDoublons, TailleBloc  : Integer;
i, j, Long, Cheksum       : integer;
CR         : boolean ;
begin  // vérif des doublons
  NbLignes   := 0;
  NbDoublons := 0;
  Long := 0;
  Cheksum := 0;
  CR := false;
  TailleBloc := SizeOf(BlocLecture);
  if OpenDialog1.Execute then begin
    AssignFile(Fromfic, OpenDialog1.FileName);
    Reset(FromFic);
    while not eof(Fromfic) do begin
      BlockRead(FromFic, BlocLecture, TailleBloc, NumRead);
      for i := 1 to TailleBloc do begin
        inc(Long);                      
        Cheksum := Cheksum + BlocLecture[i];
        if BlocLecture[i] = 13 then CR := true;
        if (BlocLecture[i] = 10) and CR then begin  // CRLF
          inc(NbLignes);
          if NbLignes >= length(LongEtCheksum)-1 then begin
            setlength(LongEtCheksum, length(LongEtCheksum) + TailleBloc);
            setlength(DejaDoublon, length(LongEtCheksum));
          end;
          LongEtCheksum[NbLignes,1] := long;
          LongEtCheksum[NbLignes,2] := Cheksum;
          DejaDoublon[NbLignes] := false;
          Long := 0;   // réinit début ligne
          Cheksum := 0;
          CR := false;
        end;
      end;  // for i := 1 to TailleBloc
    end;  // while not eof(Fromfic)
    CloseFile(FromFic);                       // <1s - 120 000 lignes - 8.3Mo
    for i := 1 to NbLignes -1 do
      for j := 1 to i - 1 do 
        if not DejaDoublon[j] then
          if LongEtCheksum[j,1] = LongEtCheksum[i,1] then  
            if LongEtCheksum[j,2] = LongEtCheksum[i,2] then begin
              inc(NbDoublons);
              DejaDoublon[i] := true;
            end;
    edit1.text := inttostr(NbLignes);
    edit2.text := inttostr(NbDoublons);
  end;  // if OpenDialog1.Execute
end;

j'ai testé sur un fichier de 8.3Mo / 12000 lignes, ça met quand même 20 secondes au total (la lecture du fichier < 1sec)

si quelqu'un peut m'expliquer les Hash en quelques mots (ou lignes) merci

à plus

**ShaiLeTroll** · 04/06/2007, 15h21

Ton algo est sur le principe de la création du relevé topologique ... donc trop couteuse en mémoire que l'on a abandonné, de plus, tu ne peux pas dépasser les 2 Go avec un "File of" ...c'est proche de celui que j'ai fourni qui pour un fichier de 8.8 Mo (1 millions de ligne), met 10s (pour TOUT mapper, et n'ont pas detecté un seul doublon) ... 90% étant prise par les comparaisons, les allocations de tableau ...

sinon HashOf c'est dans IniFiles THashStringList ... et c'est du code privée, et non documenté ... et c'est dans notre cas l'équivalent de ton CheckSum, il s'apelle HashOf car c'est pour créer une table de hashage (sorte d'index) dans une TStringList

Parcourir un fichier texte sans charger le fichier

Delphi

Discussions similaires

Partager

Partager