Discussion :

[banban54]

bonjour

merci pour l'info (HashOf)

à plus!

[Gilbert Geyer]

A ShaiLeTroll / message d'Aujourd'hui 11h22

Juste une rectification pour éviter un quiproquo. Je n'ai pas écrit "qu'il y avait une taille moyenne de ligne indiqué par Art19 ..." (à moins que son code permette d'en déduire une) ... j'ai surtout voulu rappeler que d'après son code le but serait de trouver le premier couple de doublon dans le fichier, d'identifier ce fichier et de passer immédiatement au fichier suivant.
Comme sa StringList de fichiers comporte un nombre inconnu de noms-de-fichiers (10, 100, 1000, ...?) et que certains font "plusieurs Giga" (avec FileSream.Size : Longint "plusieurs" = limité à 2.147) ... cela constitue un nombre astronomique de lignes à comparer et un nombre encore plus qu'astronomique de comparaisons à effectuer ... d'où l'intérêt de quitter les boucles au 1er doublon détecté pour passer au fichier suivant.
Cela entraîne la possibilité d'autres scénarios de codification et d'optimisation sans oublier que pour ce qui est des tests de vitesse le cas de figure le plus contaignant est celui de la recherche de doublons dans un fichier de plusieurs Giga qui ne comporte aucun doublon et dans lequel on boucle jusqu'à la dernière ligne.
En attandant qu'Art19 apporte davantage de précisions sur son cahier de charges rien n'interdit de se faire plaisir en codant ce que l'on veut ...

[Gilbert Geyer]

A Banban54 :

1) A propos de HashOf :

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
Exemple de résultats fournis avec HashOf :
H(A) = 65
H(B) = 66
H(a) = 97
H(b) = 98
 
H(ZZ) = 306
H(AA) = 325
H(AZ) = 350
 
H(ZZZZZZZZZZ) = 18874386
H(AAAAAAAAAA) = 22020117
 
H(arbre)      =    31245
H(arbuste)    =   500165
H(arbrisseau) = 32009313
 
H(abcdefghijklmnopqrstuvwxyz0123456789) = 1411527292
 
H(ABC) = 1371
H(CBA) = 1401

... avec un seul caractère on retrouve le code Ascii
... et avec davantage de caractères on peut s'en servir pour voir si H(s1)=H(s2) mais on ne pourrait pas l'utiliser pour faire du classement Alpha.
... par contre H(ABC) = 1371 et H(CBA) = 1401 montre que ce hashOf permet de différencier deux anagrammes alors que Cheksum := Cheksum + BlocLecture[i]; donnerait la même Cheksum pour ABC et pour CBA (à moins qu'il n'y ait une subtilité dans ton code qui m'a échappé).

2) Test "sur un fichier de 8.3Mo / 12000 lignes" : (cela ferait des lignes de ~725 caractères!). C'est 12 000 ou 120 000 comme l'indique le commentaire qui figure dans le code ? Cela changerait quand même un peu les comparaisons des résultats avec ceux obtenus par d'autres codes.

Ce serait d'ailleurs pas mal, pour pouvoir mieux comparer les résultats des tests de vitesse, d'utiliser le même fichier de tests de sorte que les résultats ne dépendent plus que du code et de la machine utilisée.

[banban54]

@Gilbert Geyer
merci pour l'explication sur Hash

en effet c"est bien de 120 000 lignes pour 8.3 Mo, ce qui est plus cohérent.

Pour la démo "ABC" vous avez raison, disons que je suis parti du principe qu'un énorme fichier texte ne doit pas contenir trop de lignes courtes, ( en tout cas si elles ne font que 3 caractères il y aura forcemment doublon avant les 2 Go).
La methode avec deux integer et un boolean (contrôle aussi de la longueur) doit permettre d'aller plus loin avant le game over de la mémoire.
En extrapolant un peu, si les lignes ne font pas plus de 32 000 caractères, ça devrait pouvoir tourner avec des 'entiers court' avec un Checksum mod 32000.
C'est sans prétention, c'est comme vous avez dit un peu plus haut histoire de se faire plaisir.

à plus!

[Gilbert Geyer]

A banban54 :

1) A propos de "( en tout cas si elles [les lignes] ne font que 3 caractères il y aura forcemment doublon avant les 2 Go)" : En fait bien-bien-avant les 2 Go, car j'ai utilisé pour ma part un fichier de tests dont :
- les n-2 lignes du début étaient générées chacune par un Random(98) pour la longueur de ligne et un chr(67 +Random(26)) pour chaque caractère de texte,
- et les deux dernières lignes par '<<< MI-DOUBLON >>>',
- avec bien entendu un #13#10 en fin de chaque ligne.

Et avec ceci, dans un fichier de 10 Mo (207760 lignes), le premier doublon généré aléatoirement est apparu dès la 249ième ligne ... j'ai donc vite ajouté une instruction if (length(ligAl)>0) and (length(ligAl)<=3) then LigAl:=LigAl+intToStr(numLig); pour éviter ce type de doublon et pousser ma moulinette à fureter jusqu'à la fin du fichier ... (et tout à l'heure j'y ai même rajouté deux lignes dont l'une est l'anagramme de l'autre.). Donc pour un fichier aléatoire de 2 Go il faudrait certainement différencier les lignes de moins de 4 ?, 5 ?, 6 ? caractères.

2) A propos de "La methode avec deux integer et un boolean (contrôle aussi de la longueur) doit permettre d'aller plus loin avant le game over de la mémoire. En extrapolant un peu, si les lignes ne font pas plus de 32 000 caractères, ça devrait pouvoir tourner avec des 'entiers court' avec un Checksum mod 32000" : j'ai pas bien pigé ? Car rien qu'avec un HashOf(string) la longueur de la ligne est déjà prise en compte dans sa routine de calcul (donc inutile de stocker toutes les longueurs), et si on peut se contenter de quitter les boucles dès la détection du 1er doublon il serait même superflu de pré-calculer les HashOf de toutes les lignes sauf en prévision du cas singulier d'un fichier de 2 Go qui ne comporterait aucun doublon. ... Et comme le calcul d'un Hashof + sa comparaison à un autre est plus lent qu'un comparaison directe des deux chaines correspondantes il faut bien, si on utilises les hashes, les utiliser d'une manière qui compense largement cette lenteur.

3) A propos de "si les lignes ne font pas plus de 32 000 caractères" :
Tiens faudrait voir ce que vaut un HashOf(string-de-32000-caractères) comparé à un HashOf(string-de-31999-caractères) pour tester par rapport aux limites du HashOf : Cardinal 0..4294967295.
Par contre une ligne de 32000 caractères imprimée en zig-zaguant sur du format A4 à raison de 10 à 12000 petits caractères par page cela ressemble à du texte tapé au kilomètre sans aucun #13#10 sur plusieurs pages.
... là aussi ce serait intéressant d'avoir l'avis d'Art19 si ceci correspond aux caractéristiques problables de ses fichiers.

[banban54]

bonjour

pour le 2) il est évident que j'ai laissé tomber les Hash (puisque j'usqu'à hier je ne savais pas ce que c'était (blague!)) mais pour ma vue un peu binaire, avoir la longueur directement est sans doute un gain de temps pour la recherche des doublons.
donc le but ( sauf si Art19 se manifestant nous dit qu'au premier doublon on sort de la boucle) pour moi est de rechercher tous les doublons possibles (aux anagrammes près). Donc je pensai pouvoir mapper un plus grand fichier en utilisant un tableau d'entiers court.

attendons qu'Art19 se manifeste

dans tous les cas, avoir plusieurs point- de-vues ne peut être que positif.
à plus

[Gilbert Geyer]

A banban54 :

Pour info : résultats de tests comparatifs entre algo du 4 juin 2007 12h03 et mon algo-lent mais avec les mêmes fichiers semi-aléatoires de tests.
(Il y a de quoi améliorer nos deux codes) :

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
Avec Pentium III à 1.13Ghz :
----------------------------------------------------------------
Algo Banban avec C:\Doublons2Mo.txt
NbLignes : 41418
Fin lecture : mis : 15788ms
NbDoublons : 24905 < ???
Durée totale : mis : 26443ms <soit 27 s
----------------------------------------------------------------
Algo Banban avec C:\Doublons10Mo.txt
NbLignes : 207104
Fin lecture : mis : 24870ms
NbDoublons : 182534 < ???
Durée totale : mis : 274986ms <soit 275 s < 4 min 35 s
==================================================
mon Algo avec c:\Doublons2Mo.txt
Taille : 2097232 Octets
Nombre de lignes : 41419
ReleveTopo : mis : 36 ms
Longueurs : mis : 6 ms
ChercherPremDoublon2 :
Dup n° 1 numLignes 41417 = 41418 <= 1 seul doublon en fin du fichier
mis : 113322 ms <soit 114 s < 1 min 54 s contre 27 s
-----------------------------------------------------------------
mon Algo avec C:\Doublons10Mo.txt
c:\Doublons10Mo.txt
Taille : 10485863 Octets
Nombre de lignes : 207105
ReleveTopo : mis : 185 ms (*)
Longueurs : mis : 19 ms (*)
ChercherPremDoublon2 : beaucoup trop lent, pas attendu la fin ... et on est loin des 2 Go !!! :oops: .

(*) = 204 ms de lecture à comparer aux 24870ms

A+

[Gilbert Geyer]

Bonjour,

à banban54 / msg d'Aujourd'hui 15h21

"avoir la longueur directement est sans doute un gain de temps pour la recherche des doublons".

Le problème est que pour lever les doutes on est, presque chaque fois qu'on parle de l'incidence d'un paramètre sur les gains/pertes de temps, obligés de sortir les chronomètres.

attendons qu'Art19 se manifeste

... oui effectivement cela clarifierait les limites de son besoin,
... et s'il ne se manifeste pas, on peut continuer à creuser le sujet à notre guise.

A+

[banban54]

@Gilbert Geyer

je suis en train de chercher pourquoi j'ai autant de proposition de doublons???
je vous tien au courant (si je trouve!)

à plus

[Gilbert Geyer]

A mon avis si CheckSum(string-i)=CheckSum(string-j) et que length(string-i)=length(string-j) dans ce cas je pense que le code signale qu'il s'agit d'un doublon même si en réalité (string-i)<>(string-j).

Voiçi pour gagner du temps le code avec lequel j'ai généré les fichiers d'essais et qui au moins jusqu'à 10 Mo fournit des fichiers avec un seul et unique vrai-doublon logé en fin de fichier :

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
procedure TForm1.bCreerFichierAleatoireClick(Sender: TObject);
label     PasBon;
var       FS : TFileStream; NomFichier,sTailleMo,LigAl,invite : string;
          TailleOc,code,numLig : integer; // ChronoC : oChrono; < chronomètre avec GetTickCount
 
          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; < simple bascule avec Screen.cursor
          //ChronoC.Top(Edit1);
          TailleOc := TailleOc*1024*1024;
          Randomize;
          numLig:=0;
          repeat inc(numLig);
                 LigAl:=LigneAleat(LgAleat);
                 // Eviter génération de profusion de doublons avec chaines très courtes
                 if (length(ligAl)>0) and (length(ligAl)<=3)
                 then LigAl:=LigAl+intToStr(numLig);
                 LigAl:=LigAl+#13#10;
                 FS.Write(PChar(LigAl)^, length(LigAl));
          until FS.Size >= TailleOc;
          LigAl:='ANAGRAMME'+#13#10;
          FS.Write(PChar(LigAl)^, length(LigAl));
          LigAl:='EMMARGANA'+#13#10; //< anagramme d'ANAGRAMME'
          FS.Write(PChar(LigAl)^, length(LigAl));
          LigAl:='<<< MI-DOUBLON >>>'+#13#10;
          FS.Write(PChar(LigAl)^, length(LigAl));
          FS.Write(PChar(LigAl)^, length(LigAl));
          //ChronoC.Mis;
          //Sablier;
end;

A+

[CapJack]

A mon avis si CheckSum(string-i)=CheckSum(string-j) et que length(string-i)=length(string-j) dans ce cas je pense que le code signale qu'il s'agit d'un doublon même si en réalité (string-i)<>(string-j).

D'où la nécessité de faire un relevé topologique dans un fichier déporté, pour comparer directement les chaînes dans les (rares) cas où cela risque d'arriver.

[Art19]

c'est sympa d'avoir ecrit 5 pages de reponses mais j'ai deja resolu ce probleme depuis plus d'une semaine je crois

[banban54]

bonjour

@Art19

C'est le defi du jour. Si vous trouvez une solution optimale je vous offre une bouteille de champagne (et un bisous)

1) quand on lance un defi on prend la peine de le suivre!

2) prendre la peine de lire les cinq pages, pour répondre aux questions que les gens qui voulaient t'aider se sont posé.

3) nous sommes sur un forum d'entraide, dautres auront peut être besoin de ta solution que tu devrais publier ici.

à plus!

[ShaiLeTroll]

c'est sympa d'avoir ecrit 5 pages de reponses mais j'ai deja resolu ce probleme depuis plus d'une semaine je crois

Alors on marque le sujet résolu avec le bouton, et il serait sympa de nous faire partager ta solution finale ...

[Gilbert Geyer]

A Art19

Félicitations! ... Et pour clore la discussion de façon constructive, je soutiens le voeu de ceux qui se sont cassé la tête sur le sujet ainsi que sur les questions sans réponse à propros du cahier des charges ... en répétant qu'il "serait sympa de nous faire partager ta solution finale ..."

[Gilbert Geyer]

A ShaiLeTroll :

A propos de ta fonction HashOf(string) : En la testant (voir les quelques résultats cités dans mon message à Banban54 du 04/06/2007, 18h06) il apparaît que celle-ci est utilisable pour voir si H(s1)=H(s2) ou si H(s1)<>H(s2) y compris si s1 et s2 sont l'anagramme l'un de l'autre, mais que l'on ne pourrait pas l'utiliser pour faire du classement Alphabétique vu entr'autres que :
H(arbre) = 31245
H(arbuste) = 500165
H(arbrisseau) = 32009313
... n'y aurait-il pas une astuce qui permettrait de transformer cette fonction en une fonction HashOfAlpha(string) utilisable pour faire du classement alphabétique ???

[ShaiLeTroll]

A propos de ta fonction HashOf(string)

Rendons à César, ce qui est à César, c'est une fonction de l'unités IniFiles utilisé dans THashStringList de Delphi

Sinon pour la modifier pour conserver l'ordre cela risque de rendre faux les égalités ...

[Gilbert Geyer]

A ShailLeTroll :

c'est une fonction de l'unités IniFiles utilisé dans THashStringList de Delphi

: Exact et tu l'avais d'ailleurs déjà annoncé, mais comme c'est toi qui l'as apportée dans la discussion je me suis permis d'abréger en disant "ta fonction".

Sinon pour la modifier pour conserver l'ordre cela risque de rendre faux les égalités ...

: Dommage car cela aurait élargi le champ de ses possibilités d'utilisation.

[Art19]

desole! je pensais que le topic etait parti aux oubliettes.. et entre temps j'ai travaille sur d'autres programmes. mais la j'y reviens. voila ce que j'avais retenu:

'fichiers' est une TStringList qui contient les noms des fichiers

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
  for i := 0 to fichiers.Count-1 do begin
 
    flag := 0;
 
    lignes.Clear();
 
    AssignFile( fich, fichiers[i] );
    Reset( fich );
 
    while not Eof(fich) do begin
       ReadLn( fich, s );
 
       for j := 0 to lignes.Count-1 do begin
 
          if s = lignes[j] then begin
            memo1.Lines.Add( 'le fichier '+fichiers[i]+' contient un ou plusieurs doublon(s)' );
            flag := 1;
            break;
          end;
 
       end;
 
       if flag = 0 then lignes.Add(s);
       if flag = 1 then break;
 
 
    end;

avantages:

* je lis une ligne par une ligne
* des qu'il y a un doublon je sors de ma boucle

inconvenient:

* en pratique c'est quand meme tres lent!

[e-ric]

Cela ne résoud pas le problème de la taille des données.

A titre pratique, tu peux utiliser IndexOf poour déterminer si une chaîne de caractères se trouve déjà dans la TStringList. Remarque que cela n'accélérera pas ton traitement, mais le code est plus simple.

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
 
  for i := 0 to fichiers.Count-1 do 
  begin
    flag := 0;
    lignes.Clear;
    AssignFile( fich, fichiers[i]);
    try
      Reset( fich );
      while not Eof(fich) do 
      begin 
        ReadLn( fich, s ); 
        if lignes.IndexOf(s) > - 1 then
          flag := 1
        else
          lignes.Add(s);
      end;        
      if flag = 1 then
        memo1.Lines.Add( 'le fichier '+fichiers[i]+' contient un ou plusieurs doublon(s)' );
      //....
    finally
      CloseFile(fich);
    end;
  end;

Cdlt