@ PapyJohn : alors, toujours à fond ?![]()
@ PapyJohn : alors, toujours à fond ?![]()
Bon pour le fichier de test je propose celui ci:
La rouine crre un fichier de 362880 strings de 9 chiffres chacn. Le ,nombre d'arrangement possible soit 9!). Je crois que l'on peut déjà s'amuser à chronométrer: a solution n'est pas arrivée du premier coup )
J'ai regarde les exemples: en réalité le fait de faire le blockread est plus rapide rapide que le loadfromfile MAIS on perde du temps dans le filesize:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65 procedure Calcul_Combi; var i1, i2, i3, i4, i5, i6, i7, i8, i9: integer; Stemp: string[9]; begin Totals := 0; M:=Strinlist.create; Stemp := '111111111'; for I1 := 49 to 57 do begin Stemp[1] := Chr(I1); for I2 := 49 to 57 do begin Stemp[2] := Chr(I2); if i1 <> i2 then for I3 := 49 to 57 do begin Stemp[3] := Chr(I3); if (i3 <> i1) and (i3 <> i2) then for I4 := 49 to 57 do begin Stemp[4] := Chr(I4); if (i4 <> i1) and (i4 <> i2) and (i4 <> i3) then for I5 := 49 to 57 do begin Stemp[5] := Chr(I5); if (i5 <> i1) and (i5 <> i2) and (i5 <> i3) and (i5 <> i4) then for I6 := 49 to 57 do begin Stemp[6] := Chr(I6); if (i6 <> i1) and (i6 <> i2) and (i6 <> i3) and (i6 <> i4) and (i6 <> i5) then for I7 := 49 to 57 do begin Stemp[7] := Chr(I7); if (i7 <> i1) and (i7 <> i2) and (i7 <> i3) and (i7 <> i4) and (i7 <> i5) and (i7 <> i6) then for I8 := 49 to 57 do begin Stemp[8] := Chr(I8); if (i8 <> i1) and (i8 <> i2) and (i8 <> i3) and (i8 <> i4) and (i8 <> i5) and (i8 <> i6) and (i8 <> i6) and (i8 <> i7) then for I9 := 49 to 57 do begin Stemp[9] := Chr(I9); if (i9 <> i1) and (i9 <> i2) and (i9 <> i3) and (i9 <> i4) and (i9 <> i5) and (i9 <> i6) and (i9 <> i7) and (i9 <> i8) then begin Totals := totals + 1; M.aad(stemp); end; end; end; end; end; end; end; end; end; end; M.SaveTofile('Sudoku.txt'); end;
il faut donc de très gros fichiers ou avoir la taille avant.
J'ai fini avec le tri des listes: interressant j'attaque les doublons et cela sera fini.
PapyJohn
Voici la routine que j'utilise pour supprimer les doublons dans une liste TRIEE
son gros avantage est quelle travaille sur elle mime sans allocation mémoire supplémentaire et manipule donc des listes de n'importe quelle taille.
ll faut juste lui indiquer le nom de la table : string, interroge, longent peu importe...Elle peut aussi travailler sur des portions de liste.
Elle supprime les doublons mais aussi les triples,quadruples....
Elle renvoie le nouveau nombre d'éléments
Il faudra attendre un peu poour les tris: il'effondre à 32700 entrées!
Et je ne sais pas pourquoi.
Pour le café la prochaine version est en négociation avec Nescafé....
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 function Doublons(Deb,Fin:longint): longint; var i: Longint; Index: Longint; Taille:longint; begin i := Deb; Index := Deb; Taille:=Sizeof(L[1]); repeat if L[i]<>L[i+1] then begin Inc(Index); Move(L[i+1],L[index],10); end; inc(i); until i >= Fin; Doublons := Index; end;
Bonjour,
A PapyJohn
1)... en fait avec un TFileStream on a à la fois la rapidité et la taille dans sa propriété FS.size et la lecture d'une propriété c'est quasi instantané (c'est pas pour rien qu'on utilise les FileStream lorsqu'on a de très gros fichiers qui ne tiennent pas entièrement en mem-vive) :il faut donc ... ou avoir la taille avant.... et dommage que le compilo n'accepte pas la ligne SetLength(lignes.Text,FS.Size); car cela aurait permis d'éviter le recours à la variable intermédiaire TXT et de gagner le temps pris par le transfert d'affectation de l'instruction "lignes.Text:=TXT".
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 procedure SupprDoublonsDansFI3(const nomFiSource, NomFiDest : string); //**** // avec tFileStream et TXT vers lignes.text var lignes : TStringList; FS : tFileStream; TXT : string; begin lignes := TStringList.Create; lignes.Sorted := TRUE; lignes.Duplicates:=DupIgnore; FS := TFileStream.Create(nomFiSource, fmOpenRead); FS.Position:=0; try SetLength(TXT,FS.Size); //SetLength(lignes.Text,FS.Size); <refusé par le compilo [Erreur] uLectureMegaFichier.pas(1401): Un objet constante ne peut être passé comme paramètre Var FS.Read(Pchar(TXT)^,FS.Size); //FS.Read(Pchar(lignes.Text)^,FS.Size); < syntaxe acceptée par le compilo lignes.Text:=TXT; lignes.SaveToFile( NomFiDest ); finally lignes.free; FS.Free; end; end;
2) Avec SupprDoublonsDansFI3 et votre 'Sudoku.txt' de 362880 strings de 9 chiffres le temps d'exec descend chez moi à Durée totale : mis : 4353 ms (Pentium III à 1,13 GHz) mais ce résultat est trompeur :
- d'abord car Sudoku.txt ne contient aucun doublon à supprimer or ce sont les suppressions qui demandent à Delphi de réorganiser la StringList ce qui prend du temps,
- et car des strings de seulement 9 chiffres c'est peu représentatif.
Dans son premier message que je viens de relire (et que j'avais complètement oublié) Bilbo194 a écrit... donc il faudrait que nos fichiers de tests soient représentifs de l'utilisation envisagée donc ni 9 chiffres ni 62 caractères mais en moyenne (10 + 200)/2 = 105."Suivant le type de fichier, chaque ligne peut avoir de 10 à 200 caracteres".
Faudrait donc qu'on mette d'abord au point le code de génération du fichier de tests (nombre de caractères par lignes, proprotion de doublons, etc) et surtout une idée nouvelle pour améliorer le score de la supression de doublons.
A+
EDIT : J'avais pas remarqué que PapyJohn a intercalé un nouveau message pendant que je rédigais le mien
Re-Bonjour,
A PapyJohn : J'ai voulu tester votre function Doublons(Deb,Fin:longint): longint; mais avec la variable "var L : TStringList;" le compilo me tousse un message d'erreur à la ligne suivante:... ??????????
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 Move(L[i+1],L[index],10); <[Erreur] uLectureMegaFichier.pas(1614): Variable requise
... de plus le principe même d'utiliser move m'intrigue car même si le compilo acceptait je me demande comment cela supprimerait les doublons en les déplacant ?
A+![]()
L'erreurque tu rencontre est du au fait que L (la liste) est un objet
C'est unde des raisons pour lesquels je rechine à les uilisé pour autre chose que l'affichage. Quand tu travaille à la main tu as plein de routines interdites
Ma Liste est definie par
L: array[1..40000] of string[9];
Bien sur on peut mettre une array dynamique!!!
Si tu gardes a TStringList tu remplaces simplement la lignes par
L[index]:= L[i+1]; et c'est tout
Le move va un peu plus vite: il y en a mime des versons de course:
le move est généraliste tu peux toujours le simplifier au cas par cas.
J'avais revenu on va chatouiller les cycles....
J'explique la routine de doublons:
soi une liste 1,2,2,3,12,12 et y on veut 1.2.3.12
donc on se sert de la table en entree et de DEUX index I et index
Maintenant tu regardes si la valeur suivante est la mime
donc le 1 et le 2 différent donc rien ne bouge incrément de l'index de balayage
on compare 2 et 2 c'est égal je n'incrémente que le balayage puisse que j'ai déjà
je compare donc le 2 et le 3 différents donc je remplace évincement mon index de sauvegarde je recopie dedans le 3
ma table est donc devient 1,2,3 et je pointe sur le 3 comparaison avec 12 différent donc recopie 1,2,3,12
je compare 12 et 12 rien
et j'ai fini mon index de recopie me dit combine il me reste d'éléments
Un seul balayage , les données déplacées une seule fois et tous les doubles supprimés techniquement je crois que c'est le mieux que l'on puisse imaginer
Un test ,un morve, 1 ou 2 incréments même en ASM je ne vois pas une autre logique qui supprime des instructions
L'avantage du MOVE est qu'il travaille sur la mémoire sans se soucier du type de variable contenues.
Peut être en regroupant les move en cas d'éléments différents; pour en réduire le nombre?
Papy qui rencontre un gros problème de performance; jusqu'à 350 000 éléments pas de souci au delà la cata!
Papy
Re-bonjour,
A PapyJohn : vu ça marche... j'ai gardé la TStringList en remplaçant la ligne par L[index]:= L[i+1]; :Résultats :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 var L : TStringList; function DoublonsPapyJohn(Deb,Fin:longint): longint; var i, Index : longint; //Taille : longint; begin i := Deb; Index := Deb; //Taille:=Sizeof(L[1]); L.Sorted:=FALSE; // sinon L[index]:= L[i+1]; non accepté repeat if L[i]<>L[i+1] then begin Inc(Index); //Move(L[i+1],L[index],10); <[Erreur] uLectureMegaFichier.pas(1614): Variable requise L[index]:= L[i+1]; end; inc(i); until i >= Fin; DoublonsPapyJohn := Index; end; procedure TfrmGen.bAlgo2PapyJohnClick(Sender: TObject); var NomCourtFichier, NomLongFichierOrig, RepAppli : string; chronoA : oChrono; NomSauverSous : string; pop : Integer; begin L:=TStringList.create; RepAppli:=ExtractFilePath(Application.ExeName); OpenDialog1.InitialDir := RepAppli; OpenDialog1.Filter:= 'Fichiers Texte (*.txt)|*.TXT'; if OpenDialog1.Execute then begin Application.ProcessMessages; ChronoA.Top(frmGen.Edit1); NomLongFichierOrig:=OpenDialog1.FileName; NomCourtFichier:=ExtractFileName(NomLongFichierOrig); pop := pos('.',NomCourtFichier); if pop>0 then Insert('_noDup',NomCourtFichier,pop) else NomCourtFichier:=NomCourtFichier+'_noDup'; NomSauverSous:=RepAppli+NomCourtFichier; L.Text:=''; L.Sorted := TRUE; L.LoadFromFile(NomLongFichierOrig); DoublonsPapyJohn(0,L.count-1); L.SaveToFile( NomSauverSous ); redRapport.lines.add('Durée totale : mis : '+intToStr(chronoA.mis)+ ' ms'); end; end;
1) avec un fichier de 10000 lignes dont une ligne sur deux est du texte aléatoire de 62 caractères et une ligne sur deux est égale à la chaîne '<<< MI-DOUBLON >>>' :
- Durée totale : mis : 110 ms avec DoublonsPapyJohn
- Durée totale : mis : 113 ms avec SupprDoublonsDansFI3 à peu près kif-kif.
2) avec fichier de 200000 lignes dont une ligne sur deux est du texte aléatoire de 62 car et une ligne sur deux est égale à la chaîne '<<< MI-DOUBLON >>>' (8540 Ko) :
- Durée totale : mis : 62753 ms avec DoublonsPapyJohn
- Durée totale : mis : 55879 ms avec SupprDoublonsDansFI3 un peu plus rapide.
3) avec fichier sudoku.txt, de 362880 lignes de 9 caractères, sans doublon :
- Durée totale : mis : 4419 ms avec DoublonsPapyJohn
- Durée totale : mis : 4348 ms avec SupprDoublonsDansFI3 à peu près kif-kif.
J'ai pas encore testé avec un array dynamique
... c'est peut-être que la mem-vive-disponible arrive à saturation ?Papy qui rencontre un gros problème de performance; jusqu'à 350 000 éléments pas de souci au delà la cata!
A+![]()
Desole erreur
Bonjour,
A PapyJohn
Hier j'ai dit un peu trop rapidement "vu ça marche... j'ai gardé la TStringList en remplaçant la ligne par L[index]:= L[i+1];"
Aujourd'hui en ajoutant des showMessage(intToStr(L.count)); je me suis rendu compte que le nombre de lignes était le même en entrée et en sortie de votre fonction ce qui signifie que les doublons avaient été supprimés par le LoadFromFile:... ce qui signifie également que L.Duplicates est par défaut égal à DupIgnore puisque les doublons avaient disparu.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 L.Sorted := TRUE; L.LoadFromFile(NomLongFichierOrig); showMessage(intToStr(L.count)); DoublonsPapyJohn(0,L.count-1); showMessage(intToStr(L.count)); L.SaveToFile( NomSauverSous );
... j'ai donc modifié ce passage comme suit :... et en examinant le fichier du résultat il apparaît que l'instruction L[index]:= L[i+1];" remplace les doublons originaux par des doublons formés par des lignes originales qui n'en étaient pas.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8 L.Sorted := TRUE; L.Duplicates:=DupAccept; L.LoadFromFile(NomLongFichierOrig); showMessage(intToStr(L.count)); DoublonsPapyJohn(0,L.count-1); showMessage(intToStr(L.count)); L.SaveToFile( NomSauverSous );
... comme dans le fichier-de-tests une ligne sur deux constituait un mi-doublon, le fichier-résultat comporte maintenant dans sa première moitié les lignes de texte aléatoire et dans sa deuxième moitié leur copie qui remplace les mi-doublons originaux mais qui forment des doublons avec la première moitié du fichier-résulat. Dommage...
A+
Je crois que l'erreur est dans le test de contrôle
En réalité JE NE MODIFIE pas le court: je le retourne seulement
car je ne me sers pas de TlistStrung mais d'unbe
warrant [1..40000] lof string de 10
Je supprime les éléments en double et je dis combien sont unique
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 function Doublons(Deb,Fin:longint): longint; var i: Longint; Index: Longint; begin i := Deb; Index := Deb; repeat if L[i]<>L[i+1] then begin Inc(Index); L[index]:=L[i+1]; end; inc(i); until i >= Fin; Doublons := Index; end;
L pourrai être une array s'interroge , de réal ou tout autre chose
la routine effacerait les doublons mais laisse toujours la table dans son intégralité
En fouillant bien la classe j'ai découvert du'i n'y a pas de méthode pour supprimer le doublons pour nettoyer un table par exemple
Exempe:
j'ai donc 10000 entrées mais comme mon plafond était à 5000 j'ai forcement de doubles. Et bien je n'ai aucun aucun moyen de les supprimer:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 for i:=1 to 10000 do M.add(IntTosStr(Random de 5000));
je peux modifier les méthodes , retrier la liste rien n'y fera mes doublons restent
Il existe une seule de solution le savetostream ou savetofile avec le load derriere
De fait la gestion des doublons et de 'duplicate' ne sont que dans la méthode add pas dans le sort
Et quand on fait un loadfromfile il lit le fichier ligne par ligne et qu'il ADD chaque ligne c'est à ce moment la et uniquement celui la qu'il vérifie(par une recherche dico) si la ligne est en double et s'il doit l'integrer
En réalité il n'y a pas de tri au chargement il construit une liste triée par insertion si sort est à true autrement il fait un ajout à la fin.
Ce n'est pas tout a fait vrai sur le lecture ligne par ligne: il lit l'intégralité dans les TEXT puis recoupe en lignes. Autant pour moi on ne gagne rien en lisant dans d'un bloc s'est déjà se qu'il fait
J'ai commis aussi une erreur sur les indexof en l'accusant de mille maux. En lisant la doc il est bien précisé que c'est pour les listes non triées pour les triées il faut utiliser FIND. Désole de cette fausse info.
Mais il est vrai que l'on peut toujours trier la liste en local pour accélérer les recherches.
Mais j'ai l'impression que les méthodes ne sont pas celles que j'avais vu il y a quelques années il se pourrait bien que lors d'une mise à jour les classes.pas
aient été modifiées (peut etr(e lors du poassage de D5 à D6 cela fait tellement longtemps.
PapyJohn
Bonjour,
A PapyJohn :
I) Suppression de doublons : En fait pour utiliser votre fonction avec une StringList de sorte qu'elle supprime non seulement les doublons d'origine mais également ceux qu'elle génère on est obligé de ne retenir que la partie située entre le début et la ligne correspondant à la valeur prise par "Index" :... avantage résultant : le fichier-résultat est effectivement débarassé 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 function DoublonsPapyJohn(Deb,Fin:longint): longint; var i, Index : longint; begin i := Deb; Index := Deb; L.Sorted:=FALSE; // sinon L[index]:= L[i+1]; non accepté par compilo repeat if L[i]<>L[i+1] then begin Inc(Index); L[index]:= L[i+1]; end; inc(i); until i >= Fin; DoublonsPapyJohn := Index; for i:=L.count-1 downto Index+1 do L.Delete(i); //< pourrait être remplacé par SetLength(L,index); dans le cas où L serait un Array of string end; // et pour l'appel de la fonction : L:=TStringList.create; L.Sorted := TRUE; L.Duplicates:=DupAccept; L.LoadFromFile(NomLongFichierOrig); DoublonsPapyJohn(0,L.count-1); L.SaveToFile( NomSauverSous );
... inconvénient : cela ralentit considérablement la manip :
1) avec le fichier de 10000 lignes dont une ligne sur deux est du texte aléatoire de 62 caractères et une ligne sur deux est égale à la chaîne '<<< MI-DOUBLON >>>' :
- Durée totale : mis : 259 ms avec DoublonsPapyJohn
- Durée totale : mis : 113 ms avec SupprDoublonsDansFI3 : 2,29 fois plus rapide.
2) avec le fichier de 200000 lignes dont une ligne sur deux est du texte aléatoire de 62 car et une ligne sur deux est égale à la chaîne '<<< MI-DOUBLON >>>' (8540 Ko) :
- Durée totale : mis : 410874 ms avec DoublonsPapyJohn
- Durée totale : mis : 55879 ms avec SupprDoublonsDansFI3 : 7,35 fois plus rapide.
... et on constate en plus que le gain de vitesse avec SupprDoublonsDansFI3 augmente lorsque le nombre de doublons à supprimer augmente.
II) IndexOf : En fait voiçi le code de TStringList.IndexOf standard qui utilise Find lorsque Sorted est à True :... mais les performances de rapidité de l'IndexOf standard sont sanctionnées par l'utilisation de l'instruction CompareStrings(FList^[i].FString, S) qui dans une fonction personnalisée peut être remplacée par une simple comparaison directe de chaines FList^[i].FString > S dans le cas de chaines non accentuées. Voiçi une fonction de remplacement plus rapide qui exploite ce principe :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 function TStringList.Find(const S: string; var Index: Integer): Boolean; var L, H, I, C: Integer; begin Result := False; L := 0; H := FCount - 1; while L <= H do begin I := (L + H) shr 1; C := CompareStrings(FList^[i].FString, S); if C < 0 then L := I + 1 else begin H := I - 1; if C = 0 then begin Result := True; if Duplicates <> dupAccept then L := I; end; end; end; Index := L; end; function TStringList.IndexOf(const S: string): Integer; begin if not Sorted then Result := inherited IndexOf(S) else if not Find(S, Result) then Result := -1; end;III)
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 function IndexOfSL3(SL : TStringList; const S: string): Integer; // Si SL.Sorted=False la présence de caractères accentués ne fausse pas le résultat. // Dans le cas inverse n'utiliser cette fonction que pour des chaînes non accentuées. // sinon remplacer le calcul de C par C := CompareStr() qui est plus lent var L, H, I, C: Integer; ok : boolean; begin with SL do begin Result := -1; // Cas SL non triée : Parcours depuis début de liste vers fin : if Not Sorted then begin I:=-1; repeat inc(I); until (SL[I] = S) or (I = Count-1); // < l''égalité SL[I] = S marche même en présence de caractères accentués if SL[I] = S then Result:= I; EXIT; end; // Cas SL triée : Parcours depuis la médiane de la liste // vers le début ou la fin en fonction du signe de C : L := 0; H := Count - 1; ok:=false; while L <= H do begin I := (L + H) shr 1; if SL[i] < S then C:=-1 else if SL[i] > S then C:=+1 else C:=0; if C < 0 then L := I + 1 else begin H := I - 1; if (C = 0) then begin ok:=true; if Duplicates <> dupAccept then L := I; end; end; end; if ok then Result:= L; end; end;... oui-mais sous réserve que le temps mis pour trier la liste ne dépasse pas le gain résultant de l'accélération des recherches.Mais il est vrai que l'on peut toujours trier la liste en local pour accélérer les recherches.
A+![]()
Votre mesure n'est pas 'honnête"
En rajoutant le delete il est clair que la fonction rame c'est bien pourquoi j'ai bien insisté sur la définition de a table
L : array[0..40000] of string[62];
// Par facilite
M=TStronglist.create.
M.LoadFromFile(NomLongFichierOrig);
For i:=0 to M.count-1 do
L[i]:=M[i],
La table L contient la même chose que M
et en sortie la liste L contient bien les éléments sans les doublons, le nombre d'éléments valide est le résultat de la fonction et il reste du garbage dans la table. Si c'est lui qui vous dérange vous dites que L est une table dynamique et vous faites un setlength à la nouvelle taille
Puisse que vous fouillez visiblement le classes.pas (comme moi)
vous pouvez allez voir le fonctionnement du loadfromFile ou steam
Il lit le fichier d'un seul coup Size octets dans S
puis il découpe le buffer en string car le fichier texte rajoute des $10 et à13 en fin de chaque ligne il fabrique alors le string et fait un ADD
er c'est dans le ADD qu'il n'ajoute pas le string dans la liste en sortie (qu'il fabrique directement triée si besoin.
Chaque fois due vous ferez un add en fonction du duplicate il ajoute ou pas.
Mais si vous arrivez vec une liste avec des doublons il n'existe pas de méthode pour la nettoyer. il faut faire un save et un load ou appeler une fonction qui le fait comme la mienne
Le seul moment où j'ai réellement eu des résultats est dans le tri.
L'hiver est un temps propice à la programmation: pas envie d'aller courir dehors!
PapyJohn
Re-Bonjour,
A PapyJohn :... en fait l'ajout du delete était la première idée qui m'est venue à la tête pour rendre le fichier-resultat entièrement "clean" et je pensais qu'en faisant les delete dans une boucle Downto ce serait plus favorable pour le chrono.Votre mesure n'est pas 'honnête"
En rajoutant le delete il est clair que la fonction rame
(tiens en rédigeant ceci, il me vient une idée que je vais tester demain : remplacer la boucle des delete en modifiant simplement la valeur de Capacity)
... Ok, je vais demain faire comme ceci, un test comparatif, en éliminant le garbage avec un SetLength à la nouvelle taille.L : array[0..40000] of string[62];
M=TStronglist.create.
M.LoadFromFile(NomLongFichierOrig);
For i:=0 to M.count-1 do
L[i]:=M[i],
... Ben-oui, car c'est très instructif (à part les fois où je n'y pige rien...).Puisse que vous fouillez visiblement le classes.pas (comme moi)
... exact! En plus de cela on a eu un été pourri et maintenant on caille.L'hiver est un temps propice à la programmation: pas envie d'aller courir dehors!
A+![]()
je fouille le classes pour voir somment fait delphi dans le delete pour resituer le memoire
Il y a peut etre un moyen de n'en faire qu'un!
Bonne Nuit
PapyJohn
Bonjour,
A PapyJohn
1) A propos de mon idée d'utiliser Capacity pour tronquer la liste : Elle est nulle car tout d'abord l'aide Delphi dit :... et en plus cela provoque le message d'erreur "Violation d'accès à ..."De plus, si la valeur affectée à Capacity est inférieure à celle de Count, la mémoire utilisée pour stocker les chaînes qui sortent de la liste n'est pas libérée.
2) Ton idée est nettement meilleure : elle m'a mis sur la piste d'une solution encore plus directe : au lieu de passer par une variable intermédiare du type array of string[62] pour faire For i:=0 to M.count-1 do L[i]:=M[i] afin de pouvoir faire le SetLength avant de sauver le résultat sur disque je sauve le résultat directement sur le disque au fur et à mesure de sa création avec un FileStream.Write() comme suit :... tout d'abord cette procédure évite le passage par la variable intérmédiare d'où économie de mem-vive, intéressant pour cas de gros fichiers.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 procedure SupprDoublonsPapyJohn2(const nomFiSource, NomFiDest : string); var i : longint; L : TStringList; FS : TFileStream; begin L:=TStringList.create; L.Sorted := FALSE; // < pour accélérer le LoadFromFile L.LoadFromFile(nomFiSource); if L.Count>0 then begin L.Sort; // < 1 seul tri FS := TFileStream.Create(NomFiDest, fmCreate); i := 0; FS.Write(PChar(L[i]+#13#10)^, length(L[i]+#13#10)); for i:=0 to L.Count-2 do if L[i]<>L[i+1] // alors directos vers disque then FS.Write(PChar(L[i+1]+#13#10)^, length(L[i+1]+#13#10)); FS.Free; end; L.Free; end;
... et pour les vitesses c'est encore mieux :
1) Avec le fichier de 10000 lignes dont une ligne sur deux est du texte aléatoire de 62 caractères et une ligne sur deux est égale à la chaîne '<<< MI-DOUBLON >>>' :
- Durée totale : mis : 259 ms avec DoublonsPapyJohn (version d'hier avec Delete)
- Durée totale : mis : 175 ms avec SupprDoublonsPapyJohn2
- Durée totale : mis : 113 ms avec SupprDoublonsDansFI3 : 1,54 fois plus rapide.
2) Avec le fichier de 200000 lignes dont une ligne sur deux est du texte aléatoire de 62 cara et une ligne sur deux est égale à la chaîne '<<< MI-DOUBLON >>>' (8540 Ko) :
- Durée totale : mis : 410874 ms avec DoublonsPapyJohn
- Durée totale : mis : 55879 ms avec SupprDoublonsDansFI3
- Durée totale : mis : 4596 ms avec SupprDoublonsPapyJohn2 : 12,15 fois plus rapide que SupprDoublonsDansFI3. (j'ai refait ce test plusieurs fois car au vu du résultat du premier essai j'ai cru avoir cliqué sur un autre bouton !!)
3) Avec le fichier Sudoku.txt de 362880 lignes de 9 caractères sans aucun doublon :
- Durée totale : mis : 6202 ms avec SupprDoublonsPapyJohn2
- Durée totale : mis : 4332 ms avec SupprDoublonsDansFI3 : 1,43 fois plus rapide
Conclusion l'ancien score est battu par SupprDoublonsPapyJohn2 (SupprDoublonsDansFI3 est plus rapide seulement dans les cas où la liste contient peu de doublons ou aucun doublon à supprimer, ce qui est agaçant car on ne sait pas à l'avance dans quel cas on se retrouve et un comptage préalable du nombre de doublons prendrait presque autant de temps que leur suppression).
A+![]()
J'ai fouille le delete en realite il appelè un finalize avec un count pour un freemem
Donc plus besoin de write (qui était une bonne idée)
On reste avec la TstringListe de base
On fazit un loadFromfie (a qui je viens de p)asser un peit cop d'accelerateur)
on elimine les doubons et on fait un finalize
Perso je ne travaille qu'avec du pre alloue et le NbLignes me donne largement satisfaction. Mon axiome de base étant moins tu demandes de chose au gestionnaire de mémoire moins il risque d'exploser.
Alors tanpis je préférè occuper de la memoire (surtout que sous windows ca l'occupe deja beaucoup)
Il ne te manque que le tri. Je te le joins
pour tester
Tu charge ton fichier avec le sort et le duplicates
et tu mesure le temps
Pour moi tu charges la liste avec un load sans tri ni doublons
tu déclenche le chrono
tu recopies ta liste dans L
Tu tires
Tu enleve les doublons
tu arretes le chrono
Et donc pour comparer tu fais
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 procedure Tri_; var s, sj, sl, sr, j,k: Longint; Code: string[9]; Resa: string[9]; St : array[0..5000, 0..1] of Longint; begin S := 1; st[S, 0] := 1; st[S, 1] := nbLignes; repeat sl := st[S, 0]; sr := st[S, 1]; Dec(S); repeat j := sl; sj := sr; Code := L[(sl + sr) shr 1]; repeat while (L[J] < Code) do Inc(j); while (Code < L[Sj]) do Dec(sj); if j <= sj then begin Resa := L[j]; L[j] := L[Sj]; L[Sj] := Resa; Inc(j); Dec(sj); end; until j > sj; if j < sr then begin inc(S); St[S, 0] := j; St[S, 1] := sr; end; sr := sj; until sl >= sr; until S < 1; end; function Doublons(Deb,Fin:longint): longint; var i: Longint; Index: Longint; begin i := Deb; Index := Deb; repeat if L[i]<>L[i+1] then begin Inc(Index); L[index]:=L[i+1]; end; inc(i); until i >= Fin; Doublons := Index; end;
La le temps est intéressant!!!
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 M.Clear; M.sorted:=true; M.Duplicates:=dupIgnore; QueryPerformanceCounter(FStart); M.LoadFromFile('Sudoku.TXT'); QueryPerformanceCounter(FStop); FElapsed := (FStop - FStart) div 1000; NbLignes:=M.Count-1; QueryPerformanceCounter(FStart); for j:=0 to NbLignes do L[j]:= M[j]; Tri_; Doublons; QueryPerformanceCounter(FStop); FElapsed := (FStop - FStart) div 1000;
A+
PapyJohn (j'ai oublié le fauteuit roulant)
Mais le moral est bon!!!
Re-Bonjour,
A PapyJohn : Ouille encore une nouvelle idée !
Comme j'ai sauté le repas de midi (skotché devant micro depuis ce matin) je ferai les tests comparatifs demain matin.
Par contre en lisant rapidement ton code il y a un truc qui m'intrigue :... si Sorted:=true alors le Duplicates:=dupIgnore a de l'effet sur le LoadFromFile() qui élimine les doublons d'entrée de jeu en ralentissant le chargement qui s'effectue par une succession d'insertions et de décalages de lignes.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 M.sorted:=true; M.Duplicates:=dupIgnore; QueryPerformanceCounter(FStart); M.LoadFromFile('Sudoku.TXT');
... de plus avec Sorted:=true la liste est triée d'entrée de jeu donc quel est l'intérêt de la trier une deuxième fois avec la procedure Tri_; ???????
Par contre cela ne m'empêchera pas de faire des tests comparatifs j'en profiterai pour comparer également les performances de ta procedure Tri_; à celles de la méthode "Sort" standard.
A propos de QueryPerformanceCounter : Je me contente d'une précision d'une milliseconde (avec GetTickCount) depuis que je me suis rendu compte que Windows piquait la main quand ça lui chante et autant de fois que ça lui chante même si on fixe la priorité à HightPriority (orthographe approximative) et même en lui passant la main avec Application.ProcessMessages juste avant le Start-Chrono.
Sur ce, je vais rattraper le repas de midi.
A+![]()
Exact
il faut le mettre a false pour partir d'un
fichier non trié: trop facile!
(n'oublies pas de mettre une echarpe: le coup de vent pourrait t'enrhumer)!
PapyJohn
Re-bonjour,
A PapyJohn :
J'allais quitter le forum quand...... là on est d'accord.Exact il faut le mettre a false pour partir d'un fichier non trié
... pour aujourd'hui pas de risque je ne quitterai ma turne avant demain matin.n'oublies pas de mettre une echarpe: le coup de vent pourrait t'enrhumer!
... et pour commencer je vais rattraper le repas de midi.
A+![]()
Bonjour,
A PapyJohn : Je viens de tester ta procédure de tri destinée à remplacer la méthode "Sort" dans la suppression de doublons mais elle me pose des problèmes je n'y ai pourtant remplacé que la taille des variables Code et Resa :Problème n°1 : en effectuant un tri sur la liste suivante :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 procedure Tri_3; var s, sj, sl, sr, j,k: Longint; Code: string; //string[9]; Resa: string; //[9]; St : array[0..5000, 0..1] of Longint; begin S := 1; st[S, 0] := 1; st[S, 1] := nbLignes; repeat sl := st[S, 0]; sr := st[S, 1]; Dec(S); repeat j := sl; sj:= sr; Code := L[(sl + sr) shr 1]; repeat while (L[J] < Code) do Inc(j); while (Code < L[Sj]) do Dec(sj); if j <= sj then begin Resa := L[j]; L[j] := L[Sj]; L[Sj] := Resa; Inc(j); Dec(sj); end; until j > sj; if j < sr then begin inc(S); St[S, 0] := j; St[S, 1] := sr; end; sr := sj; until sl >= sr; until S < 1; end; // Tri_3... elle me sort comme résultat :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12 2 2 2 1 1 1 4 5 6 7 12 12... les doublons ou triplons sont bien regroupés à l'exception de ceux formés par les chaines '2'. ?????? Cela vaudrait le coup d'en trouver la cause car ta procedure est effectivement plus rapide que la méthode standard "Sort" mais tant que le fonctionnement n'est pas entièrement correct je ne vais pas annoncer le résultat du chronomètre.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12 2 1 1 1 12 12 2 2 4 5 6 7
Problème n°2 : En fait il s'agit plutôt d'une question au sujet de la variable St : array[0..5000, 0..1] of Longint; j'y ai laissé la valeur de 5000 en pensant que cela provoquerait un plantage dans le cas d'un tri avec le fichier de 200000 lignes. Et comme il n'y a eu aucun plantage (à part peut être que le résultat du tri en était faussé) le question est "par quoi remplacer cette valeur de 5000 afin que la procédure de tri puisse être utilisable quelle que soit la taille de la liste à trier" ?? Par nbLignes ?
Au fait pendant que j'y suis : As tu eu au moins l'une des deux réponses que je t'ai envoyées en réponse à ton Message-perso ?
A+![]()
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager