Discussion :

[akrobat]

salut, j'ai une méthode récursive qui modifie le contenu d'un tableau 2D passé sous forme de vecteur de vecteur en paramètre vu qu'il ne compile pas avec un simple tableau étant donné que la taille du tableau n'est pas connue au préalable.

J'ai testé cette méthode sur un petit tableau 5x5 et ça marche parfaitement.

Par contre quand je le fais dans un cas concret, par exemple un tableau de 245x419, la méthode a l'air de s'executer mais le programme s'arrête dès que la méthode est terminée, le code après l'appel de la fonction n'est pas executé...

Alors j'aimerais bien savoir ce que ça veut dire, si ça vient du fait que j'utilise Visual C++ j'en sais rien et surtout comment résoudre ce problème assez étrange

le pire c'est qu'aucune erreur n'est lancée, pas de bug...

merci

[BigNic]

difficile de répondre sans un code minimal qui reproduit le pb
Miantenant si ta fonction est recursive, il peut y avoir un problème de nombre d'appel. En effet selon les OS le nombre d'appel recursif est limité. Je ne connais pas les limites surtout sur windows que je ne n'utilise pas. Vue la description que tu fais de ton problème difficile de t'aider plus.

[Matthieu Brucher]

Si la méthode n'est jamais exécutée, c'est que l'erreur n'est pas dû à la récursivité.
Solution efficace pour savoir ce qui cloche : débuggeur.

[akrobat]

la méthode s'execute, c'est ce qui suit après l'appel qui n'est pas executé !

le code de la fonction :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
void Contamination::contamine(int x, int y, std::vector<std::vector<int>>& populus)
{
    if(populus[x][y]!=0 && populus[x][y]!=2)
    {
        populus[x][y] = 2;
        if(y-1>=0 && populus[x][y-1]!=2) Contamination::contamine(x,y-1,populus);
        if(x-1>=0 && populus[x-1][y]!=2) Contamination::contamine(x-1,y,populus);
        if(x+1<(int)populus.size() && populus[x+1][y]!=2) Contamination::contamine(x+1,y,populus);
        if(y+1<(int)populus[0].size() && populus[x][y+1]!=2) Contamination::contamine(x,y+1,populus);
    }
}

voici l'appel de la fonction :

Code :

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

1
2
3
4
 
printf("aaaaaa");
Contamination::contamine(gravityCenter->x - rec->x, gravityCenter->y - rec->y, populade);
printf("bbbbb");

aaaaaa s'imprime
le code s'execute visiblement sans erreur et le programme s'arrête après sans imprimer bbbbb

voilà si ça peut vous éclairer, pour ce qui est du nombre d'appels limité c'est spécial, et cette fonction fonctionne parfaitement en java alors pourquoi pas en C++ ??

merci

[10_GOTO_10]

En général, lorsqu'il y a un problème en retour d'une fonction, c'est généralement un problème de corruption de la pile. Cette fonction est récursive, ce qui semble corroborer cette hypothèse. En particulier:

Code :

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

if (x-1>=0 && populus[x-1][y]!=2)

me semble dangereux: suivant l'ordre d'évaluation des deux termes, il se peut qu'on lise populus[x-1][y] avec un x égal à zéro (donc x-1 négatif) => comportement aléatoire voire plantage.

[akrobat]

je comprends pas des masses, désolé...

ce que tu veux dire c'est qu'une expression booléenne en C++ n'est pas forcément évaluée dans l'ordre dans lequel elle a été écrite, c'est assez étrange et je dirais même pas performant du tout en terme de développement.

par contre, si j'évalue

Code :

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

 populus[x-1][y]!=2

en premier, et que x vaut 0 alors le programme devrait planter et me lancer une erreur du style 'array index out of bounds' or je n'ai aucune erreur, aucun message d'alerte, rien, le programme se finit "propremement" même s'il n'a pas exécuté le code qui suivait.

De plus, quand j'essaye sur un tableau 5x5 ça marche parfaitement! j'ai vraiment du mal avec le c++, et j'ai surtout vraiment besoin que ça marche !

merci de vous intéresser à mon problème

[Matthieu Brucher]

On sent les warnings comparison signed int, unsigned int qui ont été mal corrigés
La méthode devrait prendre en paramètre des unsigned int, pas des int car ce sont des indices de tableau.
Pour le test x-1>=0 tu feras à la place x>=1, ...

[Matthieu Brucher]

En général, lorsqu'il y a un problème en retour d'une fonction, c'est généralement un problème de corruption de la pile. Cette fonction est récursive, ce qui semble corroborer cette hypothèse. En particulier:

Code :

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

if (x-1>=0 && populus[x-1][y]!=2)

me semble dangereux: suivant l'ordre d'évaluation des deux termes, il se peut qu'on lise populus[x-1][y] avec un x égal à zéro (donc x-1 négatif) => comportement aléatoire voire plantage.

Il n'y a aucun problème si on a pas surchargé l'opérateur &&, le premier opérande est évalué puis le deuxième si besoin est. C'est très utilisé en C++, et c'est imposé dans le standard. Ca marche donc sous réserve de n'avoir pas surchargé && maladroitement.

[akrobat]

On sent les warnings comparison signed int, unsigned int qui ont été mal corrigés
La méthode devrait prendre en paramètre des unsigned int, pas des int car ce sont des indices de tableau.
Pour le test x-1>=0 tu feras à la place x>=1, ...

ce qui veut dire que les tableaux dynamiques en C++ commencent à 1 ? mais alors comment ça se fait que lorsque j'écris l'expression 'populus[0][0] = 2' par exemple ça fonctionne ?

et quel est le dernier indice du tableau ? populus.size() -1 ou simplement populus.size() ??


j'ai vraiment du mal, désolé, je programme pas souvent en C++

merci

[hiko-seijuro]

les indices commencent à zero et le dernier indice est size()-1 !!

quand tu fais x-1 =0 ca equivaut à x=1 donc quand tu fais x-1 >=0 ca equivaut à x>=1

[akrobat]

quand tu fais x-1 =0 ca equivaut à x=1 donc quand tu fais x-1 >=0 ca equivaut à x>=1

ouhai ça se tient parfaitement, je sais pas pourquoi j'ai vu ça autrement?

Mais du coup, à quoi ça sert de changer la façon d'écrire l'expression si mathématiquement c'est la même chose ? c'est en rapport avec les unsigned int ? à quoi servent ils exactement dans mon cas ?

merci d'avance

[akrobat]

bon, je viens d'essayer de mettre des unsigned int (j'ai pas eu le temps avant) mais ça ne change absolument rien au problème, je sais pas quoi faire, peut-être que le problème vient de ce qu'a dit BigNic, il y'a peut-être un nombre limité d'appel, pourtant la même méthode fonctionne en java, alors pourquoi pas en C++, c'est le même OS ?

[Matthieu Brucher]

Fait une fois une sortie des appels des fonctions avec un std::cout << x << " " << y << std::endl; pour voir ce qui se passe, et vérifie que c'est ce que tu voulais.

[HanLee]

bon, je viens d'essayer de mettre des unsigned int (j'ai pas eu le temps avant) mais ça ne change absolument rien au problème, je sais pas quoi faire, peut-être que le problème vient de ce qu'a dit BigNic, il y'a peut-être un nombre limité d'appel, pourtant la même méthode fonctionne en java, alors pourquoi pas en C++, c'est le même OS ?

Y'a pas de nombre limité d'appels dans ton cas normalement, vu que c'est récursif terminal. Le problème est sûrement autre part.

Edit : ah non j'ai rien dit c'est une juxtaposition de if, et pas des if séparés...

[akrobat]

Fait une fois une sortie des appels des fonctions avec un std::cout << x << " " << y << std::endl; pour voir ce qui se passe, et vérifie que c'est ce que tu voulais.

ouha je sais pas trop ce que ça veut dire, désolé, j'ai placé la ligne que tu m'as donné tout de suite après l'entête de la fonction mais je sais pas du tout si c'est là qu'il fallait le mettre

Code :

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

1
2
3
4
 
void Contamination::contamine(unsigned int x, unsigned int y, std::vector<std::vector<int>>& populus)
{
    std::cout << x << " " << y << std::endl;

à l'execution les valeurs de x et de y s'affichent toutes visiblement !

[Matthieu Brucher]

Regarde si ce sont les bonnes valeurs attendues et quand ça plante, à quel degré de profondeur, ...

[thewho]

Bonjour,

Ta méthode est correcte, je l'utilise également, mais seulement pour des tableaux de taille "raisonnable" (80*80 commence à être lourd, avec Visual Studio, il faut que je commence à augmenter la taille réservée pour la pile), car elle a le grave défaut (mais si !) d'être récursive, ce qui consomme pas mal de mémoire pour la pile.

J'ai fait le test quand même, et en affichant une valeur incrémentée à chaque appel de la fonction, la limite "de plantage" augmente avec la taille attribuée à la pile, ce qui est le comportement attendu.

Pour faire le même travail, il existe des méthodes non récursives.

Il y a entre autres les algorithmes de SMITH, de LIEBERMAN, de SHANI et de PAVLIDIS.

J'ai un bouquin qui en parle : "Gérard Hégron - Synthèse d'image : algorithmes élémentaires, Dunod, 1985".

Je n'ai pas cherché de références sur le net.
Si tu ne trouves rien, je pourrai sans doute t'envoyer des scans de quelques pages.

[akrobat]

ouha c'est super sympa merci,

j'ai déjà commencé à programmer une version non récursive pour voir si le problème venait de là justement, mais j'ai peur que ce soit beaucoup plus long en terme de temps d'itérations qu'avec la méthode récursive...

merci pour les indocations

[10_GOTO_10]

Ta méthode est correcte, je l'utilise également, mais seulement pour des tableaux de taille "raisonnable" (80*80 commence à être lourd, avec Visual Studio, il faut que je commence à augmenter la taille réservée pour la pile), car elle a le grave défaut (mais si !) d'être récursive, ce qui consomme pas mal de mémoire pour la pile.

Forcément, le traitement ne se finit que quand toutes les cases adjacentes on été traitées... lesquelles cases ne sortent de la fonction que quand toutes les cases adjacentes à ces case on été traitées, etc...
Ce qui veut dire qu'à un certain moment, il y a autant d'appels à la fonction empilées dans la pile que de cases à traiter. Avec pour chaque appel trois arguments, plus les arguments cachés (le "this" puisqu'on est en C++), l'adresse de retour, les quelques registres que le compilateur sauvegarde systématiquement en début de chaque fonction, ça commence à faire du monde.

[thewho]

Bonjour,

ouha c'est super sympa merci,

j'ai déjà commencé à programmer une version non récursive pour voir si le problème venait de là justement, mais j'ai peur que ce soit beaucoup plus long en terme de temps d'itérations qu'avec la méthode récursive...

merci pour les indocations

Non, la plupart du temps, une méthode récursive est plus lente.

De plus, à moins de savoir combien de niveaux d'appels seront nécessaires, il faut faire très attention, sinon débordement rapide de la pile (ta procédure en est un bel exemple).