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.