Discussion :

[troycanneda]

Bonjour,

J’utilise souvent le site depuis sa création pour y trouver des réponses, mais c’est la première fois que je coince sur un problème, d’où cette petite demande d’aide.

Je désire effectuer le traitement statistique d’un tableau dynamique assez volumineux (>100.000 élements) dans une fonction : ce calcul nécessite un tri du tableau dans la fonction, mais je dois récupérer le tableau dans sa forme d’avant l’appel de la fonction (non trié donc).
J’ai lu les quelques conseils sur les déclarations et l’utilisation de gros tableaux sur le site ou ailleurs, j’ai néanmoins un débordement de pile au delà de 103.000 éléments.

En appliquant les conseils trouvés (notamment le passage de paramètre en var ), je n’ai pas d’erreur, mais ça ne réponds pas à mon problème car le tableau se trouve trié en sortant de la fonction.

Ci-dessous un code minimaliste illustrant le souci.

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
 
unit Unit1;
 
interface
 
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls ;
 
type
  TForm1 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Déclarations privées }
    A : array of extended;
    B : array of extended;
  public
    { Déclarations publiques }
  end;
 
var
  Form1: TForm1;
 
implementation
 
{$R *.dfm}
 
procedure MaProc1( var  A : array of extended);
begin
  //-- code contenant un tri du tableau A -> mais du coup, le tableau A est trié en sortie
end;
 
procedure MaProc2(  A : array of extended);
begin //<-- erreur d'exécution ici : débordement de pile ici
  //-- code contenant un tri du tableau A -> le tableau A n'est pas trié en sortie
end;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  i : integer;
 
begin
  SetLength(A, 110000);
 
  for i:=low(A) to high (A) do
    A[i]:=random ;
 
  MaProc1(A); //-- fonctionne
 
  MaProc2(A); //-- erreur : débordement de pile
 
  Finalize(A);
 
end;
 
end.

Je peux contourner le problème en utilisant un tableau intermédiaire B comme ceci :

Code :

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

1
2
3
4
 
  SetLength(B, 110000);
  Move(Pointer(A)^, Pointer(B)^, SizeOf(A[0])* Length(A));
  MaProc1(B);

Du coup, le tableau A n'est pas touché, mais comme ma fonction est exécutée des millions de fois, si je pouvais éviter cette étape de copie… (toute milliseconde de traitement gagnée est bonne à prendre ;-)

J'espère avoir été clair. Merci d’avoir pris le temps de me lire.

Yann

[Papy214]

ordre de tri dans un second tableau d'entiers
utilisation de ce tableau pour récupérer les éléments dans l'ordre voulu sans toucher à l'ordre initial.

Une question quand même: Pourquoi passer le tableau en paramètre ? En le déclarant dans l'implémentation, il serait accessible dans la procédure.

[troycanneda]

ordre de tri dans un second tableau d'entiers
utilisation de ce tableau pour récupérer les éléments dans l'ordre voulu sans toucher à l'ordre initial.

Un peu tiré par les cheveux : quitte à rajouter des instructions de parcours de tableaux, je préfère ma solution de passer par un tableau temporaire évoquée en fin de tableau.

Une question quand même: Pourquoi passer le tableau en paramètre ? En le déclarant dans l'implémentation, il serait accessible dans la procédure.

Pas envisageable de mon point de vue.
1. ça ne résout pas le pb du tableau qui sera trié en fin de traitement, ce que je ne veux pas. Il faudrait donc que je fasse une copie en amont pour récupérer l'ordre initial.

2.En fait, j'ai réduit le code donné en exemple au minimum pour illustrer le phénomène. Mon code final est largement plus complexe car il traite des tableaux multidimentionnelles, traitements lourds de millions de fichiers, etc : donc, l'algo nécessite le passage en paramètre je pense


En fait, je cherche plus une solution ou astuce ciblée sur passage de paramètre qui m'aurait échappé...

Le problème se réduit a savoir si je peux passer en paramètre un tableau de valeurs conséquent, le modifier dans la fonction, et le retrouver tel qu'avant modification après l'appel de la fonction : soit c'est possible, soit c'est techniquement impossible (limite du langage, etc...), et dans ce cas là, j'envisagerai alors un changement d'organisation de mon code.


merci pour ton intérêt.

Yann

[Papy214]

Sans faire de copie, ou utiliser la solution dont je parlais, je ne vois pas comment ça peut être possible. Si le tableau est trié, il ne va pas revenir à son ancien état comme par magie

[GoustiFruit]

Le débordement de pile a probablement à voir avec *ton* code: un tableau de 100000 valeurs de type extended, c'est peanuts !

Ensuite pour le tri, il faudrait savoir plus précisément ce que tu cherches à faire avec tes données, entre ton tableau initial et ton tableau trié. Selon ce que tu veux, il serait par ex. possible de créer un tableau auxiliaire qui conserverait les indices des valeurs après tri. Sinon une copie de 100000 valeurs reste très rapide (à condition que tu ne répètes pas l'opération des gazillions de fois).

[troycanneda]

Bonsoir,

Le débordement de pile a probablement à voir avec *ton* code: un tableau de 100000 valeurs de type extended, c'est peanuts !

C'est vrai, c'est peanuts, sauf que le problème survient : le code simpliste fourni sur le message initial reproduit l'erreur (même sans code dans les procédures) , tu peux faire le test toi-même dans Delphi pour te rendre compte.
Je ne pense pas avoir modifié le paramètre de pile au niveau des options du projet, je dois avoir les valeurs par défaut (Delphi 7). Tu devrais déclencher l'erreur comme moi.

Ensuite pour le tri, il faudrait savoir plus précisément ce que tu cherches à faire avec tes données, entre ton tableau initial et ton tableau trié

J'ai décrit le problème final aussi simplement que possible, j'ai pas voulu faire trop technique métier pour pas compliqué.
Pour essayer de résumer, j'ai ce tableau dynamique de valeurs sur lequel je dois calculer des statistiques pondérées par un tableau de poids (pondération). J'enchaîne donc sur le même tableau un calcul de moyenne, médiane, percentiles 15 et 85, etc, etc, le tout pondérés. Certains calculs nécessitent un tri du tableau, d'autre pas, et en final, j'ai besoin du tableau dans son ordre initial.

Sinon une copie de 100000 valeurs reste très rapide (à condition que tu ne répètes pas l'opération des gazillions de fois).

Tout a fait d'accord avec toi, dans l'absolu, la copie de 100000 valeurs avec le move reste très rapide, mais répétée des millions de fois, ça rajoute... Je suis en phase d'optimisation pour améliorer des traitements statistiques de volumes monstrueux qui prennent des heures, chaque instruction compte ;-) Surtout que pour le moment, j'ai 100000 valeurs, j'en aurai peut être 1 million à traiter dans un an...

Quitte à me répéter, j'ai juste besoin de savoir si il est techniquement possible de passer un gros tableau dynamique comme on le ferait naturellement sans utiliser le passage en VAR. D'un autre côté, si c'est possible, le compilateur fera peut être automatiquement une copie locale : ça prendra peut être autant de temps que ma solution de passer par mon move vers une variable temporaire de travail.

merci
Yann

[Papy214]

Je viens de tester ton code sur D7 et effectivement, je déclenche la même erreur.

Par contre, modifié comme suit, ça ne plante pas. Mais pourquoi, c'est un mystère.

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
 
 
type
  TArrayExtended = array of extended;
 
procedure MaProc2(  A : TArrayExtended);
begin //<-- erreur d'exécution ici : débordement de pile ici
  //-- code contenant un tri du tableau A -> le tableau A n'est pas trié en sortie
end;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  i : integer;
begin
  SetLength(A, 110000);
  for i:=low(A) to high (A) do
    A[i]:=random ;
  MaProc1(A); //-- fonctionne
  MaProc2(TArrayExtended(A)); // fonctionne
  Finalize(A);
end;

Je pense tout de même que la fonction avec var ne passe que l'adresse du tableau. Sans var, c'est une copie complète (peut-être mise dans un registre, faudrait demander aux spécialistes de la mémoire qui sévissent ici, j'ai jamais top compris comment fonctionnent ces choses là ).

[Papy214]

Le problème se règle également en modifiant les options du projet en définissant (dans l'exemple fourni) pour le linker
Max Stack Size = $01000000

au lieu de $00100000 par défaut

[troycanneda]

Merci Papy214 pour ces quelques pistes à suivre, je vais investiguer tout ça...
Je vais faire quelques recherches sur l'impact du changement du Max Stack Size au niveau du projet...
merci
Yann

[Paul TOTH]

la différence de déclaration est celle qui existe entre une tableau ouvert (paramètre array of) et un tableau dynamique (type array of). le tableau ouvert sera une copie sur la pile, tandis que le tableau dynamique sera un simple pointeur = les données sont modifiées comme avec un "var" !

démonstration:

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
  TTableau = array of integer;
 
procedure test1(t: TTableau);
begin
  t[0] := 4;
  t[1] := 5;
  t[2] := 6;
end;
 
procedure test2(t: array of integer);
begin
  t[0] := 4;
  t[1] := 5;
  t[2] := 6;
end;
 
procedure TForm1.FormCreate(Sender: TObject);
var
  t: TTableau;
begin
  SetLength(t, 3);
  t[0] := 1;
  t[1] := 2;
  t[2] := 3;
  memo1.lines.add(format('%d %d %d',[t[0],t[1],t[2]])); // 1 2 3
  test1(t);
  memo1.lines.add(format('%d %d %d',[t[0],t[1],t[2]])); // 4 5 6 
  t[0] := 1;
  t[1] := 2;
  t[2] := 3;
  memo1.lines.add(format('%d %d %d',[t[0],t[1],t[2]])); // 1 2 3
  test2(t);
  memo1.lines.add(format('%d %d %d',[t[0],t[1],t[2]])); // 1 2 3
end;

je pense que ta structure gagnerait à être un objet liste, tu pourrais avoir alors deux listes pointant sur les mêmes éléments, l'une triée l'autre dans l'ordre naturel.

[GoustiFruit]

Quitte à me répéter, j'ai juste besoin de savoir si il est techniquement possible de passer un gros tableau dynamique comme on le ferait naturellement sans utiliser le passage en VAR. D'un autre côté, si c'est possible, le compilateur fera peut être automatiquement une copie locale : ça prendra peut être autant de temps que ma solution de passer par mon move vers une variable temporaire de travail.

Tu pourrais utiliser un TDynArray: je cite:"you can sort the dynamic array content by two means: either in-place (i.e. the array elements content is exchanged) or via an external integer index look-up array (using the CreateOrderedIndex method - in this case, you can have several orders to the same data)"
-> http://synopse.info/forum/viewtopic.php?id=254

[Papy214]

ce qui revient à ma solution de départ