Discussion :

[ShaiLeTroll]

7*600*000*000 octets pour un fichier texte contenant 200000000 lignes comme ceci "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'#13#10"
Temps de Génération : 430 949 ms (encore parce que j'écrivais par paquet de 100 lignes)

Je fais le comptage de ligne maintenant ...

EDIT en 706 841 ms, il m'a compté mes 200 000 000 lignes, si tu reste en TextFile, il n'y pas de limite car il ne gère pas sa position pour gérer savoir sa fin comme le File non typé qui le gère avec un FilePos / FileSize ... donc pas de soucis avec les 10Go, juste le temps, ...

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
procedure TFrmTestFichier.BtnCountLineInFileClick(Sender: TObject);
var
   FLNC: TextFile;
   TimeIteration: Integer;
   CountLn, StartTick, EndTick, TickPerSec: Int64;
begin
   QueryPerformanceCounter(StartTick);
   try
      CountLn := 0;
      AssignFile(FLNC, EdPathSearch.Text);
      Reset(FLNC);
      try
         while not Eof(FLNC) do
         begin
            Inc(CountLn);
            Readln(FLNC);
         end;
      finally
         CloseFile(FLNC);
      end;
   finally
      QueryPerformanceCounter(EndTick);
      QueryPerformanceFrequency(TickPerSec);
      TimeIteration := Round((EndTick - StartTick) / TickPerSec * 1000);
   end;
   MemoShort.Lines.Add('CountLine : ' + IntToStr(TimeIteration) + ' ms');
   ShowMessage(IntToStr(CountLn));
end;

Maintenant, faut voir si l'on peut avoir plusieurs fois le même fichier texte dans plusieurs TextFile, car sans Seek, l'algo sera chiant et lent, alors qu'en fichier par Handle Windows, avec le Seek, ce sera plus facile, pas forcément plus rapide car l'on perdra la gestion par buffer du TextFile

[Art19]

apparemment mes plus gros fichiers sont de l'ordre de 200 000 lignes et mes plus petits de l'ordre de 5000 lignes. en moyenne ~ 44 000 lignes
ce qui me fait du 7 fichiers/seconde.. tu es sur que tu avais bien 200 000 000 de lignes parce que mon programme me semble beaucoup plus lent que ce que tu enonces

[Art19]

en rajoutant la TStringList dans ton code, je passe de 284 ms a 14 000 ms sur le meme fichier ShaiLeTroll. ce qui prend du temps dans mon algo ce n'est donc pas le ReadLn mais le

Code :

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

lignes.add

et le

Code :

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

if lignes.IndexOf(s) > -1

donc:

vous n'auriez pas une meilleure idee pour regarder si il y a des doublons?

[sjrd]

Tiens une idée qui vient de me traverser l'esprit, en repensant aux derniers posts, et au fait que les fichiers soient triés ou non.

Pensez-vous qu'il soit rentable de trier le fichier avant la recherche de doublons ? ! Si on peut se permettre de modifier le fichier, il y a moyen de trier sur place le fichier avec un quick sort (streams presque indispensables).
Ensuite, on peut rechercher les doublons en comparant chaque ligne avec la suivante uniquement.

Dans la théorie, ça veut dire faire O(n log n + n) = O(n log n) au lieu de O(n²) que l'on fait jusqu'à présent. Mais dans la pratique, je ne sais pas si les chronos diront la même chose... Surtout qu'un déplacement de données, même sur place, prend beaucoup plus de temps qu'une simple lecture.

Je pense que ce serait une excellente idée si l'on devait trouver tous les doublons. Mais s'il n'en faut qu'un... A moins qu'il y ait une probabilité correcte que les fichiers ne contiennent pas de doublons, ce qui force de toutes façons l'algo à aller jusqu'au bout.

D'un autre côté, on peut évidemment directement optimiser en faisant la recherche de doublons pendant le tri, puisqu'on peut s'arrêter au premier doublon.

Qu'en pensez-vous ?

[okparanoid]

Est-il envisageable d'enregistrer les données en amont dans une base et non pas dans un simple fichier texte ?

[Art19]

non les donnees viennent de fichiers texte
par contre il serait possible de ne pas utiliser de TStringList en aval.. non?

[macumba]

Bonjour avant de me prendre la tête comme tout le monde sur ce sujet, j'aimerais comprendre à quoi servent ces fichiers?
Ne détecter que des doublons en signalant seulement au premier doublon que le fichier a des doublons, je ne vois pas trop l'intérêt.
Ces fichiers ne serviraient pas au final à charger une base de données ? Le format du fichier le laisse penser. Auquel cas, la réflexion pourrait peut-être porter sur la façon de gérer les doublons en base de données, plutot que de perdre du temps à balayer le fichier une première fois, non? L'enlèvement d'une contrainte d'unicité pourrait peut-être régler le pb. Une simple requête pourrait alors peut-être supprimer ces doublons.

Je ne sais pas si je suis hors sujet mais en tout cas ca m'aiderait à comprendre le but recherché.

[sovitec]

Tiens une idée qui vient de me traverser l'esprit, en repensant aux derniers posts, et au fait que les fichiers soient triés ou non.

Pensez-vous qu'il soit rentable de trier le fichier avant la recherche de doublons ? ! Si on peut se permettre de modifier le fichier, il y a moyen de trier sur place le fichier avec un quick sort (streams presque indispensables).
Ensuite, on peut rechercher les doublons en comparant chaque ligne avec la suivante uniquement.

Dans la théorie, ça veut dire faire O(n log n + n) = O(n log n) au lieu de O(n²) que l'on fait jusqu'à présent. Mais dans la pratique, je ne sais pas si les chronos diront la même chose... Surtout qu'un déplacement de données, même sur place, prend beaucoup plus de temps qu'une simple lecture.

Je pense que ce serait une excellente idée si l'on devait trouver tous les doublons. Mais s'il n'en faut qu'un... A moins qu'il y ait une probabilité correcte que les fichiers ne contiennent pas de doublons, ce qui force de toutes façons l'algo à aller jusqu'au bout.

D'un autre côté, on peut évidemment directement optimiser en faisant la recherche de doublons pendant le tri, puisqu'on peut s'arrêter au premier doublon.

Qu'en pensez-vous ?

Je proposais quelques pages plus haut de conserver les lignes lues dans une structure de hashtable (insertion et recherche en O(log(n))), ce qui revient au même en terme de complexité globale, mais permet de détecter directement les doublons.

[e-ric]

Je proposais quelques pages plus haut de conserver les lignes lues dans une structure de hashtable (insertion et recherche en O(log(n))), ce qui revient au même en terme de complexité globale, mais permet de détecter directement les doublons.

Si le fichier fait quelques Go, quelle sera la taille de la hashtable ?

cdlt

[sovitec]

Si le fichier fait quelques Go, quelle sera la taille de la hashtable

Pas beaucoup plus que le TStringList. De plus je proposais de conserver le hash (MD5 par exemple) plutôt que la chaîne. C'est un peu plus lent (il faut calculer le hash), mais permet de se limiter à 16 octets (dans le cas du MD5) quelque soit la taille des lignes.

[sjrd]

Je proposais quelques pages plus haut de conserver les lignes lues dans une structure de hashtable (insertion et recherche en O(log(n))), ce qui revient au même en terme de complexité globale, mais permet de détecter directement les doublons.

Pas beaucoup plus que le TStringList. De plus je proposais de conserver le hash (MD5 par exemple) plutôt que la chaîne. C'est un peu plus lent (il faut calculer le hash), mais permet de se limiter à 16 octets (dans le cas du MD5) quelque soit la taille des lignes.

On s'était déjà penché sur les hash tables, et il est ressorti que ces hash tables, même rien qu'avec les hashes, sont beaucoup trop grosses pour être manipulées en mémoire.

D'où l'idée de travailler directement dans le fichier.

[sovitec]

On s'était déjà penché sur les hash tables, et il est ressorti que ces hash tables, même rien qu'avec les hashes, sont beaucoup trop grosses pour être manipulées en mémoire.

D'où l'idée de travailler directement dans le fichier.

J'ai pas eu le temps de lire tous les posts en détail, mais j'ai cru comprendre que la méthode actuellement utilisée utilise un TStringList, je ne vois pas en quoi cela permet de mieux travailler en mémoire.

Pour le tri du fichier c'est pareil, il ne tiendra pas en mémoire et posera les mêmes problèmes.

[ShaiLeTroll]

apparemment mes plus gros fichiers sont de l'ordre de 200 000 lignes et mes plus petits de l'ordre de 5000 lignes. en moyenne ~ 44 000 lignes
ce qui me fait du 7 fichiers/seconde.. tu es sur que tu avais bien 200 000 000 de lignes parce que mon programme me semble beaucoup plus lent que ce que tu enonces

De quoi parles-tu ?
Ma fonction ne fait que compter les lignes rien de plus, c'est un test de monter en charge pour voir si un fichier de plus de 4Go est manipulable via ReadLn ... et un fichier de 200 000 lignes de plus ou moins 40 à 60 char, ça ne fait qu'une bonne dizaine de Mo, c'est à dire rien du tout, pourquoi parlait du Go ...

[Art19]

j'ai demande a mon maitre (oui je suis un esclave) et finalement j'utilise une THashedStringList personnalisee... c'est 1000 fois plus rapide.. mon probleme est resolu.. merci a tous de vous etre bouges

[Gilbert Geyer]

Remarque 1 / structure de chaque fichier :
Si, comme le dit Art19 :

date, heure, champ1, champ2, ..., champN

N est le meme pour tout le fichier
mais il peut varier d'un fichier a un autre.
Le Nmax doit etre < 10

alors, et en supposant que le fichier n'est interrompu par aucune ligne vide (=absence de CRLFCRLF à répétition), dans ce cas la lecture de la seule 1ère ligne du fichier donne en une seule formule le relevé-topographique de la totalité du fichier vu que le pas est constant ... cela entraîne dèjà quelques simplifications et évite d'avoir à charger en mémoire des caractéristiques topographique-qui-varieraient ... si Art19 confirme cette supposition.

Remarque 2 / HashTable :
Il se trouve qu'hier matin j'ai fait des tests complémentaires avec le code de Banban54 pour rechercher l'origine de la profusion de faux-doublons (24905/41418 lignes) détectés dans un fichier-de-tests spécialement créé et ne comportant qu'un seul et unique vrai-doublon situé en fin de fichier et précédé par un seul et unique faux-doublon formé par le mot anagramme et l'anagramme de ce mot.
- Dans un premier temps j'ai donc remplacé dans ce code la formule du simple CheckSum utilisé par la formule du HashOf(string) ce qui a réduit le nombre de faux-doublons à 484.
- Ensuite j'ai fait afficher pour les 100 premiers de ces faux-doublons les paires de numéros-de-lignes en cause et j'ai pu constater dans le fichier-de-tests que 4 pour cent de ces faux-doublons étaient formés par des lignes qui deux à deux ont un contenu différent la même longueur et la même valeur du H (les 96 % de faux-doublons-restants étaient uniquement de banales lignes vides), voiçi à titre d'exemple quelques-unes des lignes où le HashOf(string) a détecté des faux-doublons :

...
Dbl entre i = 2900 et j = 1507 <- X[XWV et [VZKF
<- HashOf(X[XWV) = 19018 = HashOf([VZKF) = 19018
...
Dbl entre i = 7114 et j = 7068 <- UZ7114 QJ7068
<- HashOf(UZ7114) = 65568 = HashOf(QJ7068) = 65568
...
Dbl entre i = 9415 et j = 9311 <- YZRT et X\ZT
<- HashOf(YZRT) = 4860 = HashOf(X\ZT) = 4860
...
Dbl entre i = 41322 et j = 34478 <- VKQEKR et SYJIJV
<- HashOf(VKQEKR) = 66158 = HashOf(SYJIJV) = 66158

... donc HashOf(string) fournit des résultats inquiétants dans 4 % des cas.
... dommage que ces essais n'ont pas porté sur des chaines du type 10/04/05,17:04,0.87,0.87,0.87,0.87,1 que j'ai découvertes à l'issue de ces essais.

Question à Sovitec à propos de la réponse à E-ric :
C'est quoi la formule du "... hash (MD5 par exemple)" pour faire des tests comparatifs ... car MD5 (ou un autre, puisqu'il est dit "par exemple") est peut-être mieux adapté à notre cas de figure.???

A ShaiLeTroll / aux plus "gros fichiers" qu'Art19 déclare maintenant être de l'ordre de 200 000 lignes et qui ne feraient donc qu'une douzaine de Mo <<< "plusieurs Go" : bien vu, ça remet la balle au centre!!! ... et ça va forcément déboucher sur d'autres manières d'optimiser ... et comme Sjrd a émis l'idée d'exploiter les possibilité d'un tri voiçi à titre d'exemple des résultats comparatifs de tests de vitesse d'exécution de tris effectués par diverses routines en mémoire d'un PC 255Mo (de mem-totale) et qui pédale à seulement 1.13GHz :

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
 2 ) pour 500 000 chaînes de Texte aléatoire de 250 caractères :

    AlphaSort1( var A : StrArray; Lo,Hi : integer);    //     645 ms

    AlphaSort2( var A : tStringList;
                var PisteClef : array of integer);     //  1s 600 ms

    AlphaSort3( var A : tStringList);                  //  2s 570 ms

    TriSLTxt5(var donneesTxt : tStringList);	       //  5s 569 ms

    QuickSort2( var SL: TStringList; sens2tri : boolean; // 17s 980 ms
                fCompare: TCompareLig);
                (avec CompareLigTxtMajMin )

    sl.Sort Delphi 	                               // 34s 600 ms

... et comme Art19 utilise probablement une machine qui tourne à plusieurs Ghz sous plusieurs Go de RAM et avec seulement 200 000 lignes de seulement 62 caractères ont se sent vachement à l'aise.

Tiens Art19 vient de me prendre de vitesse avec son bref message sur sa THashedStringList personnalisee... c'est 1000 fois plus rapide.
Bon tant pis j'envoie quand-même.

[Gilbert Geyer]

A Art19

Art a dit : finalement j'utilise une THashedStringList personnalisee... c'est 1000 fois plus rapide.. mon probleme est resolu.. merci a tous de vous etre bouges

... sois sympa publie ton code ici sur le forum.

[Art19]

avant de publier mon code j'ai une question pour le newbie que je suis: ca veut dire hasher? pourquoi avec une THashedStringList c'est plus rapide qu'avec une TStringList? mon boss m'a dit que c'est parce que avec la TStringList je fais une boucle for pour la recherche alors qu'avec la hashed, c'est hashe..

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
procedure TForm1.Button1Click(Sender: TObject);
var
  i, j, flag: Integer;
  fich: TextFile;
  s: String;
  lignes: THashedStringList;
begin
  fichiers := TStringList.Create();
  lignes := THashedStringList.Create();
  Scan('E:\Sorted\STX\1M');
 
 
  for i := 0 to fichiers.Count-1 do begin
 
    lignes.Clear();
 
    AssignFile( fich, fichiers[i] );
    Reset( fich );
 
    while not Eof(fich) do begin
       ReadLn( fich, s );
 
       if lignes.IndexOf( s ) > -1 then begin
          memo1.Lines.Add( fichiers[i] );
          break;
       end;
 
       lignes.Add(s);
 
    end;
 
    CloseFile( fich );
 
  end;
 
 
end;

Scan est une fonction qui rechercher recursivement les fichiers texte

[Gilbert Geyer]

question ... ca veut dire hasher?

... par exemple la fonction HashOf(string) renvoie un cardinal (fonction de l'unités IniFiles utilisée dans THashStringList de Delphi) autrement dit cette fonction convertit les strings en des entiers et ensuite les comparaisons ne s'effectuent plus qu'entre ces entiers d'où gain de vitesse lors des comparaisons.
Mais attention si tu lis mon message précédent il y a des cas où HashOf(string1) = HashOf(string2) bien que string1<>string2.

Merci pour le code.
Je vais le récupérer et faire (demain) des essais avec en remplaçant le mode de lecture des fichiers par un FileStream vu qu'avec l'algo de Banban54 ainsi modifié j'ai constaté que l'étape de lecture-fichier en était rendue 51 fois plus rapide ... faut pas de se priver des optimisations.
A+

[Art19]

il y a des cas où HashOf(string1) = HashOf(string2) bien que string1<>string2.

est ce que ca veut dire que quand je fais

Code :

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

if lignes.IndexOf(s) > -1

il va me renvoyer true dans certains cas alors que s n'appartient pas a lignes?? dans ce cas la c'est une veritable catastrophe parce qu'il va me reperer des doublons qui n'existent pas!

[Gilbert Geyer]

A Art19 : Ben-oui il ya ce risque vu les exemples que j'ai cités et que revoiçi mais à propos desquels j'ai bien dit "dommage que ces essais n'ont pas porté sur des chaines du type 10/04/05,17:04,0.87,0.87,0.87,0.87,1 que j'ai découvertes à l'issue de ces essais" :

...
Dbl entre i = 2900 et j = 1507 <- X[XWV et [VZKF
<- HashOf(X[XWV) = 19018 = HashOf([VZKF) = 19018
...
Dbl entre i = 7114 et j = 7068 <- UZ7114 QJ7068
<- HashOf(UZ7114) = 65568 = HashOf(QJ7068) = 65568
...
Dbl entre i = 9415 et j = 9311 <- YZRT et X\ZT
<- HashOf(YZRT) = 4860 = HashOf(X\ZT) = 4860
...
Dbl entre i = 41322 et j = 34478 <- VKQEKR et SYJIJV
<- HashOf(VKQEKR) = 66158 = HashOf(SYJIJV) = 66158

... par contre si cela se produisait également avec les chaines du type 10/04/05,17:04,0.87,0.87,0.87,0.87,1 q j'ai également demandé à Sovitec la formule du "... hash MD5 qui pourrait éventuellement être plus approprié à notre problématique.
... En tous cas, quel que soit la formule du Hash, je commencerais par me générer un fichier-de-tests ne comportant qu'un seul vrai-doublon en fin de fichier et j'ajouterais dans mon code de recherche de doublons une ligne qui me renvoie au moins les 100-premiers-vrais-ou-faux-doublons pour m'assurer de l'absence de faux-doublons.
A+

P.S : si tu veux tester la function TStringHash.HashOf(const Key: string): Cardinal; avec tes données tu peux trouver son code ici en page 3 de la présente discussion joint au message de ShaiLeTroll du 30/05/2007, 18h03.