Tri de chaînes de caractères : Optimiser vitesse ?

**Paul TOTH** · 10/10/2013, 13h35

euh...non, tu as du mettre le code APRES le tri et non AVANT

du coup "DonneesTxt.Count - 1" pointe sur une ligne qui VA être supprimée et les éléments 0..1 ne sont pas modifiés.

Si tu réduits la tailles de la liste AVANT le tri, "DonneesTxt.Count - 1" sera bien la dernière ligne à modifier et on remontera jusque 0

**Gilbert Geyer** · 10/10/2013, 14h20

Re-bonjour,

Paul TOTH : euh...non, tu as du mettre le code APRES le tri et non AVANT

Bin, j'avais remplacé ça :

Code :

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

1
2
3
4
5
6
7
8
if TriCroissant then begin
    Index := FillList(DonneesTxt, 0, FirstList, 2);
    while DonneesTxt.Count > Index do DonneesTxt.Delete(Index);
  end
  else begin
    Index := FillList(DonneesTxt, DonneesTxt.Count - 1, FirstList, 2);
    while Index >= 0 do begin DonneesTxt.Delete(0); dec(Index); end;
  end;

Par ceci placé au même endroit :

Code :

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

1
2
3
4
5
6
7
 while DonneesTxt.Count > Index do DonneesTxt.Delete(Index);
  if TriCroissant then begin
    Index := FillList(DonneesTxt, 0, FirstList, 2);
  end
  else begin
    Index := FillList(DonneesTxt, DonneesTxt.Count - 1, FirstList, 2);
  end;

Placé au même endroit c'est à dire à la suite de ceci qui réalise des intitialisations :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
for Index := 0 to DonneesTxt.Count - 1 do
  begin
    Str := DonneesTxt[Index];
    if Str <> '' then
    begin
      Item := @AllItems[Index];
      Item.Value := Str;
      FirstChar := Str[1];
      Item.Next := FirstList[FirstChar];
      FirstList[FirstChar] := Item;
    end;
  end;

Donc je ne comprends pas ce que tu veux dire par AVANT le tri ???

A+.

**Paul TOTH** · 10/10/2013, 20h13

euh...ben comme ça ça fonctionne.

mais vu que dans résultat les éléments 0 et 1 n'étaient pas touchés j'ai supposé que tu avais fait ça:

Code :

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

1
2
3
4
5
6
7
8
9
 
  if TriCroissant then begin
    Index := FillList(DonneesTxt, 0, FirstList, 2);
  end
  else begin
    Index := FillList(DonneesTxt, DonneesTxt.Count - 1, FirstList, 2);
  end;
 // laisse les deux premiers et supprime les deux derniers, ce qui est une erreur
 while DonneesTxt.Count > Index do DonneesTxt.Delete(Index);

**Gilbert Geyer** · 11/10/2013, 09h55

Bonjour,

Paul TOTH :... j'ai supposé que tu avais fait ça:

Code :

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

1
2
3
4
5
6
7
8
9
 
  if TriCroissant then begin
    Index := FillList(DonneesTxt, 0, FirstList, 2);
  end
  else begin
    Index := FillList(DonneesTxt, DonneesTxt.Count - 1, FirstList, 2);
  end;
 // laisse les deux premiers et supprime les deux derniers, ce qui est une erreur
 while DonneesTxt.Count > Index do DonneesTxt.Delete(Index);

Bin non car dans le cas d'un tri Décroissant Index = 0 ou 1 en fin de tri et le Delete aurait carrément tout effacé.

A+.

**Paul TOTH** · 11/10/2013, 12h06

Envoyé par Gilbert Geyer

Bonjour,

Bin non car dans le cas d'un tri Décroissant Index = 0 ou 1 en fin de tri et le Delete aurait carrément tout effacé.

A+.

c'est pas faux ça !

ah mais oui j'ai dit n'importe quoi, la valeur de Index est non définie, dans mon esprit elle était égale au nombre d'items non vides

pour partager le code il faudra ajouter un compteur d'item dans la boucle qui rempli FirstList

voici une version finale (?)

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
 
procedure Tri_Casiers2_Str(var DonneesTxt: tStringList; ProfMaxTri: integer; TriCroissant: boolean);
type
  PStringItem = ^TStringItem;
  TStringItem = record
    Value: string;
    Next: PStringItem;
  end;
  TCharList = array[#0..#255] of PStringItem;
 
  function FillList(List: TStringList; Index, Delta: Integer; const Items: TCharList; CharPos: Integer): Integer;
  var
    SubList: TCharList;
    FirstChar: Char;
    NthChar: Char;
    Item: PStringItem;
    Next: PStringItem;
    SensDeTri: shortInt;
  begin
    Result := 0;
    for FirstChar := #0 to #255 do
    begin
      Item := Items[FirstChar];
      if Item = nil then Continue;
      if Item.Next = nil then
      begin
        List[Index] := Item.Value;
        Inc(Index, Delta);
        Continue;
      end;
      FillChar(SubList, SizeOf(SubList), 0);
      repeat
        Next := Item.Next;
        if (CharPos > ProfMaxTri) or (CharPos > Length(Item.Value)) then
        begin
          List[Index] := Item.Value;
          Inc(Index, Delta);
        end else begin
          NthChar := Item.Value[CharPos];
          Item.Next := SubList[NthChar];
          SubList[NthChar] := Item;
        end;
        Item := Next;
      until Item = nil;
      Index := FillList(List, Index, Delta, SubList, CharPos + 1);
    end;
    Result := Index;
  end; // FillList
 
var
  AllItems: array of TStringItem;
  FirstList: TCharList;
  Index: Integer;
  Count: Integer;
  Str: string;
  FirstChar: Char;
  Item: PStringItem;
  Delta: Integer;
begin
  SetLength(AllItems, DonneesTxt.Count);
  FillChar(FirstList, SizeOf(FirstList), 0);
  Count :=  0;
  for Index := 0 to DonneesTxt.Count - 1 do
  begin
    Str := DonneesTxt[Index];
    if Str <> '' then
    begin
      Inc(Count);
      Item := @AllItems[Index];
      Item.Value := Str;
      FirstChar := Str[1];
      Item.Next := FirstList[FirstChar];
      FirstList[FirstChar] := Item;
    end;
  end;
 
  while DonneesTxt.Count > Count
    do DonneesTxt.Delete(Count);
 
  if TriCroissant then
    Index := FillList(DonneesTxt, 0, +1, FirstList, 2)
  else
    Index := FillList(DonneesTxt, Count - 1, -1, FirstList, 2);
end; // Tri_Casiers2_Str

**Gilbert Geyer** · 11/10/2013, 13h49

Re-bonjour,

Paul TOTH : voici une version finale (?)

... Ok, j'ai testé elle fonctionne correctement dans les deux cas (Croissant/Décraoissant) donc elle est finale.

J'en ai profité pour en faire une version qui trie DonneesTxt du type array of string au lieu de tStringList vu que c'est presque kif-kif mais elle refuse de trier

, la voici :

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
procedure Tri_Casiers2_StrArray(var DonneesTxt: array of string; ProfMaxTri: integer; TriCroissant: boolean);
type
  PStringItem = ^TStringItem;
  TStringItem = record
    Value: string;
    Next: PStringItem;
  end;
  TCharList = array[#0..#255] of PStringItem;
 
  function FillList(List: array of string; Index, Delta: Integer; const Items: TCharList; CharPos: Integer): Integer;
  //function FillList(List: TStringList; Index, Delta: Integer; const Items: TCharList; CharPos: Integer): Integer;
  var
    SubList: TCharList;
    FirstChar: Char;
    NthChar: Char;
    Item: PStringItem;
    Next: PStringItem;
    SensDeTri: shortInt;
  begin
    Result := 0;
    for FirstChar := #0 to #255 do
    begin
      Item := Items[FirstChar];
      if Item = nil then Continue;
      if Item.Next = nil then
      begin
        List[Index] := Item.Value;
        Inc(Index, Delta);
        Continue;
      end;
      FillChar(SubList, SizeOf(SubList), 0);
      repeat
        Next := Item.Next;
        if (CharPos > ProfMaxTri) or (CharPos > Length(Item.Value)) then
        begin
          List[Index] := Item.Value;
          Inc(Index, Delta);
        end else begin
          NthChar := Item.Value[CharPos];
          Item.Next := SubList[NthChar];
          SubList[NthChar] := Item;
        end;
        Item := Next;
      until Item = nil;
      Index := FillList(List, Index, Delta, SubList, CharPos + 1);
    end;
    Result := Index;
  end; // FillList
 
var
  AllItems: array of TStringItem;
  FirstList: TCharList;
  Index: Integer;
  Count: Integer;
  Str: string;
  FirstChar: Char;
  Item: PStringItem;
  Delta: Integer;
begin
  //SetLength(AllItems, DonneesTxt.Count);
  SetLength(AllItems, length(DonneesTxt));
  FillChar(FirstList, SizeOf(FirstList), 0);
  Count :=  0;
  //for Index := 0 to DonneesTxt.Count - 1 do
  for Index := 0 to High(DonneesTxt) do
  begin
    Str := DonneesTxt[Index];
    if Str <> '' then
    begin
      Inc(Count);
      Item := @AllItems[Index];
      Item.Value := Str;
      FirstChar := Str[1];
      Item.Next := FirstList[FirstChar];
      FirstList[FirstChar] := Item;
    end;
  end;
 
  //while DonneesTxt.Count > Count : cas des chaînes vides pas converti puisque la routine ne trie pas encore.
  //  do DonneesTxt.Delete(Count);
 
  if TriCroissant then
    Index := FillList(DonneesTxt, 0, +1, FirstList, 2)
  else
    Index := FillList(DonneesTxt, Count - 1, -1, FirstList, 2);
   
end;// Tri_Casiers2_StrArray

J'ai laissé dans le code les instructions d'origine neutralisées suivies de leur version array of string pour mieux repérer les modifs.
J'ai beau m'écarquiller les yeux je ne vois pas pourquoi la routine ne trie rien dans ce cas ???

A+.

**Gilbert Geyer** · 13/10/2013, 11h11

Bonjour,

Voici la version qui trie DonneesTxt du type array of string au lieu de tStringList (l'erreur provenait du fait que Delphi n'aime pas que l'on passe en paramètre d'appel var DonneesTxt: array of string).

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
type tAOS = array of string;
 
procedure Tri_Casiers2_StrArray(var DonneesTxt: tAOS; ProfMaxTri: integer; TriCroissant: boolean);
type
  PStringItem = ^TStringItem;
  TStringItem = record
    Value: string;
    Next: PStringItem;
  end;
  TCharList = array[#0..#255] of PStringItem;
 
  function FillList(List: tAOS; Index, Delta: Integer; const Items: TCharList; CharPos: Integer): Integer;
  var
    SubList: TCharList;
    FirstChar: Char;
    NthChar: Char;
    Item: PStringItem;
    Next: PStringItem;
    SensDeTri: shortInt;
  begin
    Result := 0;
    for FirstChar := #0 to #255 do
    begin
      Item := Items[FirstChar];
      if Item = nil then Continue;
      if Item.Next = nil then
      begin
        List[Index] := Item.Value;
        Inc(Index, Delta);
        Continue;
      end;
      FillChar(SubList, SizeOf(SubList), 0);
      repeat
        Next := Item.Next;
        if (CharPos > ProfMaxTri) or (CharPos > Length(Item.Value)) then
        begin
          List[Index] := Item.Value;
          Inc(Index, Delta);
        end else begin
          NthChar := Item.Value[CharPos];
          Item.Next := SubList[NthChar];
          SubList[NthChar] := Item;
        end;
        Item := Next;
      until Item = nil;
      Index := FillList(List, Index, Delta, SubList, CharPos + 1);
    end;
    Result := Index;
  end; // FillList
 
var
  AllItems: array of TStringItem;
  FirstList: TCharList;
  Index: Integer;
  Count: Integer;
  Str: string;
  FirstChar: Char;
  Item: PStringItem;
  Delta: Integer;
begin
  SetLength(AllItems, length(DonneesTxt));
  FillChar(FirstList, SizeOf(FirstList), 0);
  Count := 0;
  for Index := 0 to High(DonneesTxt) do
  begin
    Str := DonneesTxt[Index];
    if Str <> '' then
    begin
      Inc(Count);
      Item := @AllItems[Index];
      Item.Value := Str;
      FirstChar := Str[1];
      Item.Next := FirstList[FirstChar];
      FirstList[FirstChar] := Item;
    end;
  end;
 
  SetLength(DonneesTxt, Count);
 
  if TriCroissant then
    Index := FillList(DonneesTxt, 0, +1, FirstList, 2)
  else
    Index := FillList(DonneesTxt, Count - 1, -1, FirstList, 2);
end; // Tri_Casiers2_StrArray

A mon avis on devrait pouvoir encore multiplier la vitesse par N avec une routine du style :

Code :

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

1
2
3
4
5
type 
tAOS = array of string;
tAOI = array of integer;

procedure Tri_Casiers2_PourAffichages(const DonneesTxt: tAOS; ProfMaxTri: integer; TriCroissant: boolean; var IndexesOrdreTri : tAOI);

dont la var IndexesOrdreTri renverrait la liste des Indexes de l'ordre trié, cela éviterait d'avoir à remanier l'ordre dans DonneesTxt lors du tri.
Et comme lors d'un affichage on n'affiche généralement que moins de 100 lignes à la fois quelle que soit la longueur du texte, lorsque cette longueur fait par exemple 100000 lignes on gagne le temps mis pour remanier l'ordre dans DonneesTxt lors du tri, ..., et il ne suffit plus qu'à afficher les quelques lignes dans l'ordre des indexes renvoyé par IndexesOrdreTri.
Je cois que cela vaut le coup de cogiter là dessus. Oui,Non ???

A+.

P.S : Par contre les variantes Tri_Casiers2 et Tri_Casiers2_StrArray conservent tout leur intérêt lorsque l'on a besoin de récupérer DonneesTxt remaniée complètement dans l'ordre trié, comme par exemple si on veut supprimer les doublons dans une liste de chaînes.

**Gilbert Geyer** · 15/10/2013, 12h03

Bonjour,

Voici le code de la routine Tri_Str_Indexes qui renvoie via la var IndexesOrdreTri la liste des indexes suivant lesquels il faut afficher au retour les chaînes de la const DonneesTxt pour visualiser celles-ci dans l'ordre trié donc sans remanier la structure de DonneesTxt :

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
type 
  tAOS = array of string;
  tAOI = array of integer;
 
procedure Tri_Str_Indexes(const DonneesTxt: tAOS; ProfMaxTri: integer; TriCroissant: boolean; var IndexesOrdreTri: tAOI);
var Count: integer;
 
  procedure TriSurPremChar;
  var i: integer; PremChar, Cara, CaraMin, CaraMax: Char; Indice: integer;
  begin
    Count := 0; CaraMin := #255; CaraMax := #0;
    for i := 0 to High(DonneesTxt) do // Initialisations
    begin
      if DonneesTxt[i] = '' then Continue;
      inc(Count);
      if DonneesTxt[i][1] <= CaraMin then CaraMin := DonneesTxt[i][1];
      if DonneesTxt[i][1] >= CaraMax then CaraMax := DonneesTxt[i][1];
    end;
    Indice := -1;
    for Cara := CaraMin to CaraMax do begin
      for i := 0 to High(DonneesTxt) do
      begin
        if DonneesTxt[i] = '' then Continue;
        if (DonneesTxt[i][1] = Cara) then begin
            inc(Indice); IndexesOrdreTri[Indice] := i;
        end;
      end;
    end;
  end;
 
begin
  SetLength(IndexesOrdreTri, length(DonneesTxt));
  TriSurPremChar;
  if length(DonneesTxt) > Count then SetLength(IndexesOrdreTri, Count);
  if ProfMaxTri = 1 then EXIT;
end; // Tri_Str_Indexes

Résultats des tests de vitesse pour une Profondeur de tri = 1 :
- Tri de 2000000 Lignes de 250 caractères = 500000000 avec Tri_Casiers2_Str en 374 ms (Hors affichage du résultat)
- Tri de 2000000 Lignes de 250 caractères = 500000000 avec Tri_Str_Indexes en 561 ms (Hors affichage du résultat)
Bigre : Tri_Str_Indexes est 1,5 fois plus lente que Tri_Casiers2_Str alors qu'elle ne sait pour l'instant que restituer qu'un tri sur le premier caractère !!!
Quel est donc le mystère qui explique la rapidité de Tri_Casiers2_Str ???
Car en toute logique, comme je ne demande à Tri_Str_Indexes qu'un travail beaucoup plus léger elle devrait être plus rapide que Tri_Casiers2_Str !!!???

A+.

**Paul TOTH** · 15/10/2013, 12h20

1) au lieu de faire 5 fois DonneesTxt[i], tu places sa valeur une première fois dans un Str local puis tu testes cette valeur.

2) au lieu de faire 2 fois Str[1] (ou DonneesTxt[i][1]) tu fais de même en copiant Str[1] dans Ch

c'est un principe de base d'optimisation ça, éviter de chercher plusieurs fois une valeur dans un tableau en faisant une copie locale.

**Gilbert Geyer** · 15/10/2013, 13h33

Re-bonjour,

Paul TOTH : 1) au lieu de faire 5 fois DonneesTxt[i], tu places sa valeur une première fois dans un Str local puis tu testes cette valeur.

2) au lieu de faire 2 fois Str[1] (ou DonneesTxt[i][1]) tu fais de même en copiant Str[1] dans Ch

c'est un principe de base d'optimisation ça, éviter de chercher plusieurs fois une valeur dans un tableau en faisant une copie locale.

Ok, merci, voici le code modifié :

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
procedure Tri_Str_Indexes(const DonneesTxt: tAOS; ProfMaxTri: integer; TriCroissant: boolean; var IndexesOrdreTri: tAOI);
var Count: integer;

  procedure TriSurPremChar;
  var i: integer; PremChar, Cara, Cara2, CaraMin, CaraMax: Char; Indice: integer; Str: string;
  begin
    Count := 0; CaraMin := #255; CaraMax := #0;
    for i := 0 to High(DonneesTxt) do // Initialisations
    begin
      Str := DonneesTxt[i];
      if Str = '' then Continue;
      inc(Count); Cara := Str[1];
      if cara <= CaraMin then CaraMin := cara;
      if cara >= CaraMax then CaraMax := cara;
    end;
    Indice := -1;
    for Cara := CaraMin to CaraMax do begin
      for i := 0 to High(DonneesTxt) do
      begin
        Str := DonneesTxt[i];
        if Str = '' then Continue;
        Cara2 := Str[1];
        if (cara2 = Cara) then begin
          inc(Indice); IndexesOrdreTri[Indice] := i;
        end;
      end;
    end;
  end;

begin
  SetLength(IndexesOrdreTri, length(DonneesTxt));
  TriSurPremChar;
  if length(DonneesTxt) > Count then SetLength(IndexesOrdreTri, Count);
  if ProfMaxTri = 1 then EXIT;
 end; // Tri_Str_Indexes

Résultats pour une Profondeur de tri = 1 :
- Tri de 2000000 Lignes de 250 caractères = 500000000 avec Tri_Casiers2_Str en 374 ms (Hors affichage du résultat)
- Tri de 2000000 Lignes de 250 caractères = 500000000 avec Tri_Str_Indexes en 1825 ms (Hors affichage du résultat)
C'est pire qu'avant où Tri_Str_Indexes ne mettait que 561 ms.
Là je n'y pige plus rien !!! On optimise et ça se comporte dans l'autre sens.

Mais quel est donc le mystère qui fait que Tri_Casiers2_Str soit nettement plus rapide ???

A+.

**Paul TOTH** · 15/10/2013, 18h21

en même temps ton code fait deux boucles pour pas grand chose.

c'est parfois nécessaire de faire une première boucle pour accélérer la seconde, mais dans le cas présent tu ralentis tout.

tu fais une première boucle sur le tableau pour avoir min/max...mais qu'est-ce que t'apporte cette info ? au pire tu pourrais mettre des -1 dans IndexesOrdreTri au départ puis décaler tous les nombres >= 0 vers le haut en fin de procédure.

dans la deuxième boucle tu reboucles sur le tableau autant de fois que max - min...c'est à dire que si tu as min = #0 et max = #255 tu fais 256 boucles de tout le tableau ! dans la méthode Str2 on ne fait que deux boucles, une pour lire Str[1], une pour relire la liste ordonnée.

mais de toute façon tu vas être embêter pour appliquer cet algorithme dans les passes suivantes.

si tu ne veux pas toucher au tableau d'origine, tu peux ajouter un Index dans TStringItem, au départ il contient l'index de la chaîne, puis au lieu de copier Value dans DonneeTxt tu recopies Index dans ta liste d'indexes.

**Gilbert Geyer** · 16/10/2013, 11h12

Bonjour,

Paul TOTH :en même temps ton code fait deux boucles pour pas grand chose.

c'est parfois nécessaire de faire une première boucle pour accélérer la seconde, mais dans le cas présent tu ralentis tout.

tu fais une première boucle sur le tableau pour avoir min/max...mais qu'est-ce que t'apporte cette info ? au pire tu pourrais mettre des -1 dans IndexesOrdreTri au départ puis décaler tous les nombres >= 0 vers le haut en fin de procédure.

Ceci je n'ai pas compris. ???

dans la deuxième boucle tu reboucles sur le tableau autant de fois que max - min...c'est à dire que si tu as min = #0 et max = #255 tu fais 256 boucles de tout le tableau ! dans la méthode Str2 on ne fait que deux boucles, une pour lire Str[1], une pour relire la liste ordonnée.

Bin oui c'est un inconvénient, sauf que dans du texte min = #32 et max variable < #255 donc je pensais gagner des tours de boucle.

mais de toute façon tu vas être embêté pour appliquer cet algorithme dans les passes suivantes.

C'est surtout ceci qui m'inquiète en plus du problème de vitesse.

si tu ne veux pas toucher au tableau d'origine, tu peux ajouter un Index dans TStringItem, au départ il contient l'index de la chaîne, puis au lieu de copier Value dans DonneeTxt tu recopies Index dans ta liste d'indexes.

Ok, merci pour l'info, voici ce que ça donne :

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
type 
tAOS = array of string;
tAOI = array of integer;

procedure Tri_Casiers2_StrArrayIndexes(const DonneesTxt: tAOS; ProfMaxTri: integer; TriCroissant: boolean; var IndexesOrdreTri: tAOI);
type
  PStringItem = ^TStringItem;
  TStringItem = record
    Value: string;
    IndexTri : integer;
    Next: PStringItem;
  end;
  TCharList = array[#0..#255] of PStringItem;
var iot : integer;

  function FillList(List: tAOS; Index, Delta: Integer; const Items: TCharList; CharPos: Integer): Integer;
  var
    SubList: TCharList;
    FirstChar: Char;
    NthChar: Char;
    Item: PStringItem;
    Next: PStringItem;
    SensDeTri: shortInt;
  begin
    Result := 0;
    for FirstChar := #0 to #255 do
    begin
      Item := Items[FirstChar];
      if Item = nil then Continue;
      if Item.Next = nil then
      begin
        List[Index] := Item.Value;
        inc(iot); IndexesOrdreTri[iot]:=Index;
        Inc(Index, Delta);
        Continue;
      end;
      FillChar(SubList, SizeOf(SubList), 0);
      repeat
        Next := Item.Next;
        if (CharPos > ProfMaxTri) or (CharPos > Length(Item.Value)) then
        begin
          List[Index] := Item.Value;
          inc(iot); IndexesOrdreTri[iot]:=Index;
          Inc(Index, Delta);
        end else begin
          NthChar := Item.Value[CharPos];
          Item.Next := SubList[NthChar];
          SubList[NthChar] := Item;
        end;
        Item := Next;
      until Item = nil;
      Index := FillList(List, Index, Delta, SubList, CharPos + 1);
    end;
    Result := Index;
  end; // FillList

var
  AllItems: array of TStringItem;
  FirstList: TCharList;
  Index: Integer;
  Count: Integer;
  Str: string;
  FirstChar: Char;
  Item: PStringItem;
  Delta: Integer;
begin
  SetLength(AllItems, length(DonneesTxt));
  SetLength(IndexesOrdreTri,length(DonneesTxt));
  FillChar(FirstList, SizeOf(FirstList), 0);
  Count := 0;
  for Index := 0 to High(DonneesTxt) do
  begin
    Str := DonneesTxt[Index];
    if Str <> '' then
    begin
      Inc(Count);
      Item := @AllItems[Index];
      Item.Value := Str;
      Item.IndexTri := Index;
      FirstChar := Str[1];
      Item.Next := FirstList[FirstChar];
      FirstList[FirstChar] := Item;
    end;
  end;

  //SetLength(DonneesTxt, Count);
  SetLength(IndexesOrdreTri,Count); iot:=-1;

  if TriCroissant then Index := FillList(DonneesTxt, 0, +1, FirstList, 2)
  else Index := FillList(DonneesTxt, Count - 1, -1, FirstList, 2);
end; // Tri_Casiers2_StrArrayIndexes

Cela fonctionne mais IndexTri ajoutée dans TStringItem n'est pas utilisée.
et le résultat est du tri Croissant même si TriCroissant = False.
Puis pour la vitesse avec Profondeur de tri = 1 :
- Tri de 2000000 Lignes de 250 caractères = 500000000 avec Tri_Casiers2_StrArray en 374 ms (Hors affichage du résultat)
- Tri de 2000000 Lignes de 250 caractères = 500000000 avec Tri_Casiers2_StrArrayIndexes en 374 ms (Hors affichage du résultat)
Donc vitesses identiques sauf si j'ai mal interprété ton conseil.

A+.

**Gilbert Geyer** · 16/10/2013, 12h29

Re-bonjour,

En attandant de comprendre la remarque de Paul TOTH :

en même temps ton code fait deux boucles pour pas grand chose.

c'est parfois nécessaire de faire une première boucle pour accélérer la seconde, mais dans le cas présent tu ralentis tout.

tu fais une première boucle sur le tableau pour avoir min/max...mais qu'est-ce que t'apporte cette info ? au pire tu pourrais mettre des -1 dans IndexesOrdreTri au départ puis décaler tous les nombres >= 0 vers le haut en fin de procédure.

et vu les résultats de mon message précédent j'ai modifié le code du tri sur le premier caractère en y utilisant les PChar comme suit :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
type 
tAOS = array of string;
tAOI = array of integer;

procedure Tri_Str_Indexes(const DonneesTxt: tAOS; ProfMaxTri: integer; TriCroissant: boolean; var IndexesOrdreTri: tAOI);
var Count: integer;

  procedure TriSurPremChar;
  var i, imax: integer; sPremChars: string; p: pchar;
    Cara, CaraMin, CaraMax: Char; Indice: integer;
  begin
    Count := 0; CaraMin := #255; CaraMax := #0; imax := High(DonneesTxt);
    SetLength(sPremChars, length(DonneesTxt));
    p := @sPremChars[1];
    for i := 0 to imax do begin // Récup des Premiers caractères dans sPremChars
      if DonneesTxt[i] = '' then p^ := #1 else p^ := DonneesTxt[i, 1];
      inc(p);
    end;
    p := @sPremChars[1];
    for i := 0 to imax do // CaraMin et CaraMax
    begin
      if p^ = #1 then begin inc(p); Continue; end;
      inc(Count);
      if p^ <= CaraMin then CaraMin := p^;
      if p^ >= CaraMax then CaraMax := p^;
      inc(p);
    end;
    Indice := -1;
    for Cara := CaraMin to CaraMax do begin // Tri Croissant
    //for Cara := CaraMax downto CaraMin do begin // Tri Décroissant
      p := @sPremChars[1];
      for i := 0 to imax do
      begin
        if p^ = #1 then begin inc(p); Continue; end;
        if p^ = Cara then begin
          inc(Indice); IndexesOrdreTri[Indice] := i;
        end;
        inc(p);
      end;
    end;
   end; // TriSurPremChar

begin
  SetLength(IndexesOrdreTri, length(DonneesTxt));
  TriSurPremChar;
  if length(DonneesTxt) > Count then SetLength(IndexesOrdreTri, Count);
  if ProfMaxTri = 1 then EXIT;
end; // Tri_Str_Indexes

Resultats des tests de vitesse :
A) Pour Profondeur tri = 1 :
- Tri de 2000000 Lignes de 250 caractères = 500000000 avec Tri_Str_Indexes en 94 ms (Hors affichage du résultat)
- Tri de 2000000 Lignes de 250 caractères = 500000000 avec Tri_Casiers2_StrArray en 374 ms (Hors affichage du résultat) : 3,97 fois plus lent
B) Pour Profondeur tri = 250 :
- Tri de 2000000 Lignes de 250 caractères = 500000000 avec Tri_Casiers2_StrArray en 1123 ms (Hors affichage du résultat)
Conclusion : Enfin un gain de vitesse grâce aux PChar.
Mais c'est pas encore gagné car il faut pouvoir conserver ce gain en surchargeant le code pour obtenir le tri sur les caractères suivants.

A+.

**Paul TOTH** · 16/10/2013, 13h05

pas le temps de finaliser mais voici ce que ça donne

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
 
procedure Tri_Casiers3_Str(var DonneesTxt: tStringList; ProfMaxTri: integer; TriCroissant: boolean);
type
  PStringItem = ^TStringItem;
  TStringItem = record
    Value: PChar;
    Index: Integer;
    Next : PStringItem;
  end;
  TCharList = array[#0..#255] of PStringItem;
 
  procedure FillList(var Index: PInteger; Delta: Integer; const Items: TCharList; CharPos: Integer);
  var
    SubList: TCharList;
    FirstChar: Char;
    NthChar: Char;
    Item: PStringItem;
    Next: PStringItem;
    SensDeTri: shortInt;
  begin
    for FirstChar := #0 to #255 do
    begin
      Item := Items[FirstChar];
      if Item = nil then Continue;
      if Item.Next = nil then
      begin
        Index^ := Item.Index;
        Inc(Index, Delta);
        Continue;
      end;
      FillChar(SubList, SizeOf(SubList), 0);
      repeat
        Next := Item.Next;
        Inc(Item.Value);
        if (CharPos > ProfMaxTri) or (Item.Value^ = #0) then
        begin
          Index^ := Item.Index;
          Inc(Index, Delta);
        end else begin
          NthChar := Item.Value^;
          Item.Next := SubList[NthChar];
          SubList[NthChar] := Item;
        end;
        Item := Next;
      until Item = nil;
      FillList(Index, Delta, SubList, CharPos + 1);
    end;
  end; // FillList
 
var
  AllItems: array of TStringItem;
  FirstList: TCharList;
  Index: Integer;
  Count: Integer;
  Str: string;
  FirstChar: Char;
  Item: PStringItem;
  Delta: Integer;
  Indexes: array of Integer;
  Idx: PInteger;
begin
  SetLength(AllItems, DonneesTxt.Count);
 
  FillChar(FirstList, SizeOf(FirstList), 0);
  Count :=  0;
  for Index := 0 to DonneesTxt.Count - 1 do
  begin
    Str := DonneesTxt[Index];
    if Str <> '' then
    begin
      Inc(Count);
      Item := @AllItems[Index];
      Item.Value := Pointer(Str);
      Item.Index := Index; // Index dans la tableau
      FirstChar := Item.Value^;
      Item.Next := FirstList[FirstChar];
      FirstList[FirstChar] := Item;
    end;
  end;
 
  SetLength(Indexes, Count);
 
  if TriCroissant then
  begin
    Idx := @Indexes[0];
    FillList(Idx, +1, FirstList, 2)
  end else begin
    Idx := @Indexes[Count - 1];
    FillList(Idx, -1, FirstList, 2);
  end;
 
  for Index := 0 to Count - 1 do
    Form1.ListBox1.Items.Add(DonneesTxt[Indexes[Index]]);
end; // Tri_Casiers3_Str

**Gilbert Geyer** · 16/10/2013, 13h15

Re-bonjour,

Paul TOTH :pas le temps de finaliser mais voici ce que ça donne
Ok, merci, je vais tester.

A+.

**Gilbert Geyer** · 16/10/2013, 13h36

Re-bonjour,

Voici les résultats des tests de vitesse pour profondeur de tri = 250 :
- Tri de 2000000 Lignes de 250 caractères = 500000000 avec Tri_Casiers2_Str (StringList) en 1155 ms (Hors affichage du résultat)
- Tri de 2000000 Lignes de 250 caractères = 500000000 avec Tri_Casiers3_Str (StringList) en 999 ms (Hors affichage du résultat) : 1,15 fois plus rapide.
Bon, le gain n'est pas énorme, mais un gain c'est un gain.
Je vais voir ce que je peux faire avec les PChar pour le tri sur les caractères suivants.

A+.

**Paul TOTH** · 16/10/2013, 19h38

tu as vu qu'e fin de méthode j'alimente ListBox1 ? c'était pour tester rapidement

mais sinon il faut retourner le tableau Indexes

**Gilbert Geyer** · 17/10/2013, 10h08

Bonjour,

Paul TOTH: tu as vu qu'en fin de méthode j'alimente ListBox1 ? c'était pour tester rapidement mais sinon il faut retourner le tableau Indexes

Oui, j'avais remarqué.
Pour l'instant j'essaye de poursuivre le tri sur les caractères suivants avec mon binz à base de PChar.
En rapport avec ceci, j'en profite pour te demander de m'expliquer un peu mieux ce que je n'avais pas compris dans ton message du 15/10/2013 18h21, où tu disais :

en même temps ton code fait deux boucles pour pas grand chose.

c'est parfois nécessaire de faire une première boucle pour accélérer la seconde, mais dans le cas présent tu ralentis tout.

tu fais une première boucle sur le tableau pour avoir min/max...mais qu'est-ce que t'apporte cette info ? au pire tu pourrais mettre des -1 dans IndexesOrdreTri au départ puis décaler tous les nombres >= 0 vers le haut en fin de procédure.

Cela me permettra peut être d'améliorer davantage mon code.

A+.

**Paul TOTH** · 17/10/2013, 14h31

Envoyé par Gilbert Geyer

Bonjour,

Oui, j'avais remarqué.
Pour l'instant j'essaye de poursuivre le tri sur les caractères suivants avec mon binz à base de PChar.
En rapport avec ceci, j'en profite pour te demander de m'expliquer un peu mieux ce que je n'avais pas compris dans ton message du 15/10/2013 18h21, où tu disais :
Cela me permettra peut être d'améliorer davantage mon code.

A+.

au lieu de chercher min/max tu remplies au départ le tableau avec des "-1" pour indiquer des indices invalides, et après l'algo de tri tu supprimes les "-1" qui restent

Code :

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

1
2
3
4
5
6
7
8
9
10
 
j := 0;
for i := 0 to max do
begin
  if Indexes[i] >= 0 then
  begin
    Indexes[j] := Indexes[i];
    Inc(j);
  end;
end;

mais en fait dans le code de Str3 je connais déjà le nombre d'éléments quand je dimensionne le tableau d'indexes, je n'ai donc pas de trou

PS: dans Str3 j'utilise aussi des PChar, c'est une bonne idée

**Gilbert Geyer** · 17/10/2013, 15h21

Re-bonjour,

Paul TOTH : au lieu de chercher min/max tu remplies au départ le tableau avec des "-1" pour indiquer des indices invalides, et après l'algo de tri tu supprimes les "-1" qui restent

Je suppose que par "min/max" tu parles de mes "CarMin/CarMax" ???
Je vais donc voir ce que ça donne ainsi...

dans Str3 j'utilise aussi des PChar, c'est une bonne idée

Ah oui les PChar ça glisse plus vite que de l'indexé.

A+.