Salut,

J'ai un problème assez chiant...
Je suis en C#, j'ai codé un algorithme qui nécessite beaucoup de récursions pour fonctionner (et il y a un cas d'arrêt à tous les coup)
Le problème, c'est que passé la barre des 2500, le programme se stop pour m'annoncer un stackoverflow... il me dise que c'est possible que ça soit une récursion infinie alors que c'est faux

Y'a un moyen d'empêcher ça mise à part optimiser mon algo ?

Parce que franchement, 2500 récursions, ça devrait aller pour un processeur i7 non ?

le probleme n'est pas le processeur, c'est que la pille a une taille limite sinon elle devient inutile. Si tu as besoin de 2500 recursion, tu devrais utiliser une pile allouer dynamiquement.

Ah oui, j'avais oublier ça

Je vais test merci

En fait apparemment j'ai un problème au niveau de System.Drawing (en fait j'utilise GetPixel, beaucoup trop de fois certes )

Sinon, tu peux recoder ta fonction récursive avec une boucle, suffit devoir ton algo d'un autre point de vue.

J'ai trouver une petite alternative qui a l'air de marcher et d'être plus opti

Mais sinon, malgré que je sois beaucoup plus itératif que récursif, je n'arrive pas à voir comment le faire en itératif

C'est pas toujours evident, mais mettre une pile explict devrait toujours etre facil.

Et comment tu fais ça en C# ?

En utilisant l'objet Stack de C#. Et tu peux regarder quelques cours sur la dérécursification sur internet aussi, ça peut être intéressant.

Sinon le problème peut venir d'un trop grand nombre d'appels à GetPixel. Combien fais-tu d'appel environ ?
Est-ce que ton image est bien stockée en mémoire RAM et pas dans la mémoire du GPU ?

Disons 500x500 max, c'est à dire 25000 appels au grand maximum imo.

Je pas comment on voit qu'elle est stocké dans la RAM, mais je pense que oui elle y est

La stack en .NET est de 1MB par thread, donc c'est normal que ça dépasse assez vite. Je sais pas combien de bytes sont alloués pour une fonction simple en .NET, mais si on part sur 64 octets, avec 25000 récursion, ça dépasse largement.

Je vais peut être dire une connerie mais es-tu sure d'avoir besoin d'utiliser la récursivité ?

Car la récursivité a pour principale intérêt de stocker l'ensemble des données dans la pile système, une simple boucle while ne suffis pas ?

"Disons 500x500 max, c'est à dire 25000 appels au grand maximum imo. "

Juste pour info, 500x500 ça fait pas 25 000 mais 250 000 Si c'est pour du temps réel ça commence à demander pas mal de performances.

"Je pas comment on voit qu'elle est stocké dans la RAM, mais je pense que oui elle y est "

Je viens de regarder la doc de la classe Bitmap et y a rien qui précise où est stockée l'image, donc j'imagine que ça doit bien être en RAM.

Pour en revenir au problème de stack overflow, si tu peux nous donner la structure générale de ton algo récursif on pourra peut-être t'aider à dérécursiver.

"Pour en revenir au problème de stack overflow, si tu peux nous donner la structure générale de ton algo récursif on pourra peut-être t'aider à dérécursiver."

De memoire, toutes les structures ne sont pas derecursivable: fibo ca se passe mal par exemple. Si il y a un expert en recursivite dans le coin (chris?), il va certainement me tapper dessus

C'est pas du temps réel, c'est un algo exécuté quand l'utilisateur le demande. Si ça prends une dizaine de seconde au pire, c'est pas grave.

Le soucis c'est que sur des petits sprites ça prends <1 sec, sur des moyens >1 sec, et sur des plus gros ça fait stackoverflow au lieu de prendre 5-10sec... ça je comprends pas

Le stackoverflow se déclenche au bout du ~2500e appel de la fonction

Je viens de test un truc... j'ai fait 5000 appels et ça n'a même pas planté, et ça a pris moins d'une seconde

Alors je sais pas si le programme sait à l'avance si y'aura 250 000 appels ou pas mais y'a un problème quelque part

Je vous donne l'algo si vous voulez m'aider à regler ce problème :
http://pastebin.com/Y6sgpRcX

En fait j'ai rien dis j'ai fait un gros fail

Je viens d'optimiser un petit peu le code, ça marche nickel jusqu'à 2400 (moins d'une seconde d’exécution...)

Mais bon ça plante toujours et cette fois le stackoverflow est sur le "contains"

(Toujours dans le Drawing.dll d'ailleurs )

Tu pourrais expliquer ce que ton programme fait schématiquement ?

Parce que là à part créer des points et des rectangles que t'utilises pas dedans...

Tu veux faire quoi exactement ?

on dirait un parcours en profondeur, mais c'est difficile a voir precisement.

Plus de contexte (explication+code) aiderait.

Une image est plus simple qu'un long discours en général

http://img708.imageshack.us/img708/8607/algojg.png

Au niveau du code, à part InBounds() qui regarde juste si le pixel n'est pas en dehors des limites, je n'ai pas de fonctions vont vous aider

Ok, ce que tu fait s'appelle un parcours en profondeur, il est execute par un appel recursif. http://en.wikipedia.org/wiki/Depth_first_search

L'algorithme est trivial a implementer avec une pile.

En vrai, tu n'as pas besoin d'un parcours en profondeur, un parcours en largeur fonctionnerai egalement. http://en.wikipedia.org/wiki/Breadth-first_search

En vrai, n'importe quel type de parcours fonctionnera.

J'ai implementer un algorithme similaire dans mon Qix en C++. http://bmi.osu.edu/~esaule/Qix-website/

En utilisant une pile, le code ressemblerait a : http://pastebin.com/SGwczVEu
Note que je ne fias pas de C# donc ce code ne fonctionne certainement pas. En particulier, l'appel a stack est certainement incorrect.

Note que tu cree des gazillions d'objet Rectangle sas bonne raison. Je te conseille de garder des haut, bas, gauche, droite sous forme d'entier et de creer le rectangle a la fin. Comme ceci: http://pastebin.com/nhdzymRn

YMMV