[Problème : StackOverflowError]

nasix
[Problème : StackOverflowError]

Bonjour,

Je suis dans une situation où la récursivité a lieu beaucoup de fois au point que ça génère l'erreur StackOverflowError, j'ai beaucoup réfléchi et j'ai du mal à trouver un autre moyen me permettant de diminuer le nombre d'itérations récursives.

Je m'explique.

Je dois créer une ontologie (une sorte de lexique organisé sous forme d'un arbre avec des relations de généralisation et de spécialisation) et ce à partir d'un ensemble de termes à injecter et un dictionnaire spécifique.

Mon algorithme est très simple :

Pour chaque terme de mon ensemble, je cherche ses parents (les termes avec lien de généralisation) dans le dictionnaire, je commence par les insérer et puis j'insère le terme.
De même que pour le terme, si les parents ne figurent pas dans l'ontologie, je fais le même processus pour chacun.

Dès fois, un seul terme lance tellement d'itérations que ça génère l'erreur citée en haut.

Si vous avez une astuce ou une solution je suis preneur.

Merci pour vos propositions et vos aides.

fredericmazue
Re: [Problème : StackOverflowError]

Bonjour Nasix,

Quote:
Mon algorithme est très simple :

La première chose à faire est malgré tout de t'assurer, d'être certain que le calcul termine.

Sinon, si le calcule termine, ça va peut-être être difficile, je crois que la JVM est incapable d'optimisation de type "tail recursion"

Essaie quand même de réécrire des bouts de code dans cet esprit. A supposer une fonction factorielle classique

return valeur * fact_rec(valeur - 1);

récrire comme ça, avec un accumulteur

int fact_rec_term(int valeur, int accu)
{
	if(valeur == 1)
		return accu;
	return fact_rec_term(valeur-1, valeur*accu); 
}

pour avoir un appel récursif terminal. c'est une technique classique en C/C++, mais je ne sais pas si la JVM saura en tirer partie. Au niveau du byte-code je ne pense pas, mais dans le JIT c'est possible. faut essayer

nasix
Re: [Problème : StackOverflowError]

Bonjour,

Merci d'avoir répondu à mon post.

Quote:
La première chose à faire est malgré tout de t'assurer, d'être certain que le calcul termine.

Oui je vais le faire.

Quote:
pour avoir un appel récursif terminal. c'est une technique classique en C/C++, mais je ne sais pas si la JVM saura en tirer partie. Au niveau du byte-code je ne pense pas, mais dans le JIT c'est possible. faut essayer

Je n'ai pas compris.

Merci.

fredericmazue
Re: [Problème : StackOverflowError]

J'ai voulu dire que la JVM en tant qu'interpréteur de byte-code ne fait aucune optimisation sur les appels récursifs, ni aucune optimisation en général. Mais le compilateur Just-inTime, qui convertit le byte-code en code machine, en fait lui des optimisations. Et heureusement vu que c'est son boulot :-)
Je ne sais pas s'il fait des optimisations sur les appels récursifs terminaux. Mais, c'est possible. Si tu essaies, tu le sauras :-)

nasix
Re: [Problème : StackOverflowError]

Je comprends maintenant.

Merci.