Discussion :

[MonsieurHelmut]

Bonjour à tous et à toutes.

Ces derniers temps, je test quelques approches sur un algorithme. Il s'agit d'un algo de parcours de tableau 2D façon "parcours depuis un point donné". Ma première approche est récursive et se présente comme suit :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
void Fonction(int x, int y)
{
<div style="margin-left:40px">if (...) // condition d'arret
<div style="margin-left:40px">return;</div>
tableau[x, y] ... // do stuff
 
Fonction(x + 1, y);
Fonction(x - 1, y);
Fonction(x, y + 1);
Fonction(x, y - 1);</div>}

A l'usage, je n'ai pas trouvé cette approche très performante et ai voulu me passer de la récursion, ayant lu par ci par la les tendances de .NET à ce sujet, et histoire d'éviter des StackOverflow sur des récursions trop profondes.

J'ai donc adpaté mon algo d'une façon assez classique, en empilant les paramtères :

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
 
struct Pos
{
<div style="margin-left:40px">int x, y;
public Pos(int _x, int _y)
{
<div style="margin-left:40px">x = _x;
y = _y;</div>}</div>}
 
void Fonction2(int x, int y)
{
<div style="margin-left:40px">Stack<Pos> stack = new Stack<Pos>(); // eventuellement spécifier la taille de la pile lorsque je connais la profondeur
Pos p = new Pos(x, y);
 
stack.Push(p);
 
while (stack.Count > 0)
{
<div style="margin-left:40px">p = stack.Pop();
if (...) // condition d'arret
<div style="margin-left:40px">continue;</div>
tableau[p.x, p.y] ... // do stuff
 
stack.Push(new Pos(p.x + 1, p.y));
stack.Push(new Pos(p.x - 1, p.y));
stack.Push(new Pos(p.x, p.y + 1));
stack.Push(new Pos(p.x, p.y - 1));</div>}</div>}

Mystère et boule de gomme, la version à pile est 10% moins performante que la version récursive.
Les deux fonctions sont vérifiées, même nombre d'itérations et même résultat.

La question : est-ce que je fais quelque chose de mal dans mon approche non récursive ou est-ce normal ?

Merci d'avance pour les clarifications, je suis curieux de savoir ce que .NET traffique derrière.

[emiscool]

Bonjour,

dans l'exemple que tu nous a donnée , j ai constaté que des appels ce fait plusieurs fois,


si en suit les trace de l'exécution de la fonction : Fonction(1,1) on aura les appel suivantes :

Fonction(2,1)
Fonction(0,1)
Fonction(1,2)
Fonction(1,0)

2 ème itération: Fonction(2,1) donne :
Fonction(3,1)
Fonction(1,1)
Fonction(2,2)
Fonction(2,0)

donc on a bien l'appel de la fonction avec comme paramètre x=1 et y=1 une deuxième fois.

[MonsieurHelmut]

Bonjour,

dans l'exemple que tu nous a donnée , j ai constaté que des appels ce fait plusieurs fois,


si en suit les trace de l'exécution de la fonction : Fonction(1,1) on aura les appel suivantes :

Fonction(2,1)
Fonction(0,1)
Fonction(1,2)
Fonction(1,0)

2 ème itération: Fonction(2,1) donne :
Fonction(3,1)
Fonction(1,1)
Fonction(2,2)
Fonction(2,0)

donc on a bien l'appel de la fonction avec comme paramètre x=1 et y=1 une deuxième fois.

Oui, j'en suis bien conscient et je suis obligé de le faire par rapport au traitement de mon tableau. La condition d'arret empeche la recursion d'aller plus loin si la case a deja une valeur convenable, mais je suis tout de meme forcé de revenir dessus au cas ou :/.

Merci d'avoir jeté un oeil la dessus .

[smyley]

Au fait, en programmation sous CAML ou autre, la récursion c'est la puissance. Mais en C#, par expérience, je me dit qu'on a tout à gagner à faire de l'itératif s'il y a beaucoup d'étapes.

En fait, si par malheur on fait un algorithme qui fonctionne bien sur une centaine d'étapes, arrivé à 4000 et des poussières, Stack Overflow et tout est planté ...

[Graffito]

Je serai curieux de voir la performance avec 2 Stack<int> : stackX et stackY.

Code :

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

1
2
3
4
5
6
7
8
9
10
Stack<int> stackX = new Stack<int>(); Stack<int> stackX = new Stack<int>(); 
stackX.Push(x); stackY.Push(y);
while (stackX.Count > 0)
{ int X = stackX.Pop(); int Y =stackY.Pop(); 
  if (...) // condition d'arretcontinue;tableau[X, Y] ... // do stuff
  stackX.Push(X + 1) ; stackY.Push(Y   );
  stackX.Push(X - 1) ; stackY.Push(Y   );
  stackX.Push(X    ) ; stackY.Push(Y+ 1);
  stackX.Push(X    ) ; stackY.Push(Y- 1);
}

[MonsieurHelmut]

Je serai curieux de voir la performance avec 2 Stack<int> : stackX et stackY.

Code :

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

1
2
3
4
5
6
7
8
9
10
Stack<int> stackX = new Stack<int>(); Stack<int> stackX = new Stack<int>(); 
stackX.Push(x); stackY.Push(y);
while (stackX.Count > 0)
{ int X = stackX.Pop(); int Y =stackY.Pop(); 
  if (...) // condition d'arretcontinue;tableau[X, Y] ... // do stuff
  stackX.Push(X + 1) ; stackY.Push(Y   );
  stackX.Push(X - 1) ; stackY.Push(Y   );
  stackX.Push(X    ) ; stackY.Push(Y+ 1);
  stackX.Push(X    ) ; stackY.Push(Y- 1);
}

C'est l'approche que j'avais eu avant de faire une struct, j'en avais même 3 étant donné que j'ai en réalité 3 paramètres, mais cela n'importe pas pour l'algo. Au niveau des perfs, avec le niveau de profondeur que j'ai (un peu plus de 9000 itérations), je n'ai noté aucune différence. J'ai préféré garder ce qui était le plus propre.

Ce qui serait intéressant à voir, c'est le code IL derrière deux Stack.Push(int) et derrière un Stack.Push(new struct..) pour en être certain.


EDIT : je ne sais pas si c'est représentatif des perf mais,
3 push de int = 15 IL instructions (en considérant les add/sub nécessaires à mes calculs),
1 push de new struct(int - 1, int, int + 1) = 14 IL instructions. Rien de signification à mon gout.
Si je n'avais eu que 2 piles, je pense que l'avantage aurait nettement été à cette version.

[Graffito]

Le plus rapide serait de connaître la taille des stack et de gérer des array à la place avec un index de pile.

Si on ne connait pas la taille max, on peut gèrer l'allocation mémoire des tableaux à la mano comme dans l'ancien temps en l'initialisant à n items, par exemple 10000, et lorsque l'index de pile dépasse la taille allouée, reallouer un nouveau tableau de taille double et faire un array.copy des valeurs du tableau précédent ....

[MonsieurHelmut]

Le plus rapide serait de connaître la taille des stack et de gérer des array à la place avec un index de pile.

Si on ne connait pas la taille max, on peut gèrer l'allocation mémoire des tableaux à la mano comme dans l'ancien temps en l'initialisant à n items, par exemple 10000, et lorsque l'index de pile dépasse la taille allouée, reallouer un nouveau tableau de taille double et faire un array.copy des valeurs du tableau précédent ....

Oui justement, je connais la profondeur exacte et spécifie généralement la taille de la pile, donc à priori pas de reallocation en interne de la pile.

Cela dit, j'ai testé les Stack avec et sans taille par défaut, et je n'ai aucune différence de performance, je pense que la taille max de ma récursion est vite atteinte et que le gros du boulot est de revenir sur les cases précédentes (donc plus d'impact sur la taille de la pile).

Merci à tous pour vos remarques . En attendant un avis plus approfondit sur la chose.

[elmcherqui]

j'ai pas etudie ton probleme mais si la methode recursif te parait plus naturel et plus concise et que les sous problemes se chevauchent pourquoi ne pas dynamiser le probleme au detriment d'un peu de memoire ? avec sa faut vraiment que tu ai une entree enorme pour faire peter la pile .

[ylarvor]

N'as tu pas intérêt à isoler ta fonction dans une librairie ( dll ) f# ? f# doit être plus à même de résoudre des problèmes de grand nombre de récursion ( récursivité terminale ) ?

[davcha]

Ce que je constate, c'est que d'un côté, tu as un parcours en profondeur (récursif) et de l'autre, tu as un parcours en largeur (itératif, avec ton stack).

[MonsieurHelmut]

@elmcherqui : la n'est pas mon problème, mais oui pourquoi pas.

@ylarvor : j'ai un doute quant à l'avantage de F# en termes de performances pour ce problème ci.

@davcha : les deux sont des parcours en profondeur (stack LIFO, non FIFO). Avec des parcours différents mes résultats ne seraient pas les mêmes, ce qui n'est pas le cas.


Merci pour les réponses .

[LLB]

N'as tu pas intérêt à isoler ta fonction dans une librairie ( dll ) f# ? f# doit être plus à même de résoudre des problèmes de grand nombre de récursion ( récursivité terminale ) ?

La pile est gérée de la même façon en C# et en F# (c'est le JIT .NET qui s'en occupe, via l'opcode "tail"). Le grand nombre de récursions sera traité de la même façon dans les deux langages.

F# transforme parfois lui-même en boucle, mais ça ne change pas grand-chose au final. Le gain reste faible, et C# est plus rapide sur certains autres points.

Passer de C# à F# ou l'inverse pour les performances me semble peu pertinent.


La différence de performance est peut-être liée à la récursion terminale. Ton dernier appel récursif ne sera pas empilé, du fait de cette optimisation. À l'inverse, dans ta version itérative, le 4e point est toujours empilé. Je ne sais pas si ça peut justifier les 10% de différence.

À tester, par curiosité :

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
// virer le stack.Push(p);
while (true)
{
    if (...) // condition d'arret
      {
	if (stack.Count == 0) break;
	p = stack.pop();
        continue;
      }
 
    tableau[p.x, p.y] ... // do stuff
 
    stack.Push(new Pos(p.x + 1, p.y));
    stack.Push(new Pos(p.x - 1, p.y));
    stack.Push(new Pos(p.x, p.y + 1));
    p = new Pos(p.x, p.y - 1);
}