StackOverflowError et Random

Version imprimable

03/07/2007, 19h52
jokoss

StackOverflowError et Random

Bonjour,

J'ai une fonction récursive qui permet de créer un arbre. A l'intérieur de cette fonction, j'appele une méthode qui me renvoie une liste liée d'éléments choisi aléatoirement dans un plus grand ensemble.

L'exécution du programme se fait itérativement sur des valeurs d'arbres de plus en plus grande. Jusqu'a une certaine taille je n' ai aucun problème.

A un moment donné l'exécution s'arrete et j'ai un "StackOverflowError" avec un probleme a la ligne où on appele la fonction random. (random.nextInt(int)).

Je me suis dabord dis que le problème ne venait pas de là mais si j'enleve le coté aléatoire de la fonction en prenant par exemple les n premiers élément de l'ensemble, la je n ai plus aucun probleme et je peux construire mes arbres avec des tailles encore bien plus importantes.

Je n'ai pas trouvé réellement de problème similaire sur internet. J'espere que quelqu'un pourra m'aider.

merci.
03/07/2007, 20h09
TIFéç

Salut Jokoss,

Comme il est dit dans le thread suivant (assez approchant, un probleme de stackoverflow sur un arbre): http://www.developpez.net/forums/arc...p/t-20101.html
Le stackoverflow est généralement issu d'une récursivité infinie. Maintenant selon la version de JVM utilisée il est possible qu'il y est une limite plus ou moins atteignable d'objets (ça doit quand même être assez énorme, je mise plutot sur la boucle infinie).

Tu devrai essayer de vérifier ce que te renvoi ton random, il est assez probable qu'à un moment ou un autre il te forme une boucle qui provoque l'erreur.

J'espère que cela pourra t'aider, bon courage,
Cordialement,
Tif

bonjour,

Je ne pense pas que celà vienne d'une récursion infinie. J'ai une fonction récursive qui appelle une fonction non récursive et selon que dans cette sous-fonction j'utilise l'aléatoire (ca ne marche que jusqu'une certaine taille d'arbre) ou le non-aléatoire (qui a l'air de marcher pour des tailles supérieur).

Voici les 2 versions de la sous fonction:

celle qui ne marche pas:

Code:

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
 
private ListeNumAtribut choisirEtPlacerAtributsUtilise(int nbAtributs, int maxAttr) {
        ListeNumAtribut firslistnumatr = null; 
 
        ListeNumAtribut dernierAtr = null;
        ListeNumAtribut tmpAttr;
 
        Random random = new Random();
            int k = random.nextInt(maxAttr) + 1;
            firslistnumatr = new ListeNumAtribut(k);
            dernierAtr = firslistnumatr;
 
            int i = 1;
            while (i < nbAtributs) {
                k = random.nextInt(maxAttr) + 1;
                while (existeDeja(k, firslistnumatr)) {
                    k = random.nextInt(maxAttr) + 1;
                }
                tmpAttr = new ListeNumAtribut(k);
                dernierAtr.setChaineSuiv(tmpAttr);
                dernierAtr = dernierAtr.getChaineSuiv();
 
                i++;
            }
 
             return firslistnumatr;
}

et voici la version qui ne provoque pas de stackoverflow:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
private ListeNumAtribut choisirEtPlacerAtributsUtilise(int nbAtributs, int maxAttr) {
        ListeNumAtribut firslistnumatr = null; 
 
        ListeNumAtribut dernierAtr = null;
        ListeNumAtribut tmpAttr;
 
            int tmp = 1;
        while (tmp <= nbAtributs) {
            if (firslistnumatr == null) {
                firslistnumatr = new ListeNumAtribut(tmp);
                dernierAtr = firslistnumatr;
            }
            else {
                tmpAttr = new ListeNumAtribut(tmp);
                dernierAtr.setChaineSuiv(tmpAttr);
                dernierAtr = dernierAtr.getChaineSuiv();
            }
 
            tmp++;
        }
 
             return firslistnumatr;
}

L'argument nbAtributs correspond au nombre d'éléments a choisir et l'argument maxAtr correspond au nombre total d'élément.

merci pour votre aide.

04/07/2007, 10h23
CyberChouan
Code:

1 2 3 4 while (existeDeja(k, firslistnumatr)) { k = random.nextInt(maxAttr) + 1; }
Je pense que le problème vient de là...
Si tu as nbAtributs >= maxAttr, au bout d'un moment, tu as épuisé tous les entiers possibles, et tu veux continuer d'en mettre dans ton arbre.

Comme tu génères un entier, t'aperçois qu'il est déjà dans la liste (puisqu'ils y sont tous), régénère un entier, t'aperçois... etc... et celà te donne une jolie boucle infinie.

De manière générale, ce genre de boucle et de test pour l'insertion d'une valeur aléatoire est à proscrire! Il vaut mieux avoir une liste des possibilités restantes, choisir aléatoirement une valeur parmis celles-ci et la supprimer de la liste des valeurs disponibles.

Comme ça, quand ta liste est vide, tu lèves une exception ou tu quittes la méthode... mais tu ne tombes pas dans une boucle infinie
04/07/2007, 10h29
TIFéç

Salut,

Bien vu CyberChouan, effectivement tout s'explique comme ça.

Juste une petite chose qui m'intrigue, on parlait de récursivité dans les premiers posts, mais ici moi je ne vois que des boucles. Est ce que je me trompe?

Cordialement,
Tif

Non, toi tu n'as que des boucles.

La récursivité, c'est quand une méthode s'appelle elle-même.
Voici l'exemple le plus classique d'une méthode factorielle, écrite récursivement et itérativement.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
public static int fact_recursive(int i) {
   if(i < 0) { return -1; /* erreur */ }
   else if(i ==0 || i == 1) { return 1; }
   else { return i*fact_recursive(i-1); } /* ici on a l'appel recursif */
}
 
public static int fact_iterative(int i) {
   if(i < 0) { return -1; /* erreur */ }
   int resultat = 1;
   while(i > 1) {
      resultat *= i;
      i--;
   }
   return resultat;
}

Bonjour,

Le probleme ne vient pas de la sous boucle "while existeDeja" car meme en l'enlevant ca ne marche quand meme pas. le nombre d'élément a prendre est toujours plus petit que le nombre total d'éléments.

Pour ce qui est de la récursivité, j'ai en fait une fonction principale "creerArbre" qui elle est récursive et qui au court de son exécution appele la fonction non récursive citée plus haut.

voici le code de ma fonction récursive:

Code:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
private void creerArbre(Noeud currentNode) {
 
        if (currentNode.getNombreObjet() <= nombreMinObjetPourFeuille) { 
 
            currentNode.setFeuille(true);
            int tmp = getMainClass(currentNode);
            currentNode.setTypeClass(tmp);
            return;
        }
 
        if (isFeuille(currentNode)) {
 
            currentNode.setFeuille(true);
            int tmp = getMainClass(currentNode);
            currentNode.setTypeClass(tmp);
            return;
        }
 
        ListeNumAtribut temp = choisirEtPlacerAtributsUtilise(nombreAtributATester, nombreTotalAtribut);
 
        //boolean trouve = false;
        int numAttr = -1;
        maxEntropie = -1;
        pivotBest = 10000;
        atributBest = 10000;
        while (temp != null) {
            numAttr = temp.getNumeroAttr();
            trouverBorneMinMax(numAttr, currentNode);
            int nbRandTest = choisirNombreTest();
            for (int i = 0; i < nbRandTest; i++) {
                float pivot = choisirTestAleatoire();
 
                float tmp = calculEntropiePivot(pivot, numAttr, currentNode);
                if (tmp > maxEntropie) {
                    maxEntropie = tmp;
                    pivotBest = pivot;
                    atributBest = numAttr;
                    //trouve = true;
                }
            }
 
            temp = temp.getChaineSuiv();
        }
 
        temp = null;
 
 
        if (maxEntropie <= 0) {
            currentNode.setFeuille(true);
            int tmp = getMainClass(currentNode);
            currentNode.setTypeClass(tmp);
            return;
        }
 
        currentNode.setPivot(pivotBest);
        currentNode.setBestAtribut(atributBest);
 
        Noeud[] tabNoeud = creerArbresDescendant (pivotBest, currentNode, atributBest);
 
 
        currentNode.setNoeudGauche(tabNoeud[0]);
        currentNode.setNoeudDroit(tabNoeud[1]);
 
 
        currentNode.setChaineInt(null);
 
        creerArbre(tabNoeud[0]);
        creerArbre(tabNoeud[1]);
 
 
    }

Je n'avais pas jugé utile de mettre ce code étant donné que l'erreur me semblait venir du random présant dans la fonction non récursive.

merci pour votre aide.

04/07/2007, 20h06
jokoss

Bonjour,

La machine virtuelle java m'indique bien l'erreur au niveau du random de la sous-fonction. De plus si j'enleve l'aléatoire je n'ai aucune erreur, cela nous montre qu'a partir d'un certain point de récursion la méthode de la classe Random ne marche plus.

Pour essayer de contourner le problème y'aurai-t-il moyen de générer des nombres aléatoire sans utiliser la classe Random.

merci.
05/07/2007, 10h26
adiGuba

Salut,

Citation:

Envoyé par jokoss

La machine virtuelle java m'indique bien l'erreur au niveau du random de la sous-fonction.

On pourrait avoir le stacktrace complet et un code source utilisable ?

a++

Bonjour,

voici ma stack trace :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Exception in thread "main" java.lang.StackOverflowError at Aleatoire.choisirEtPlacerAtributsUtilise(Aleatoire.java:706) at Aleatoire.creerArbre(Aleatoire.java:136) at Aleatoire.creerArbre(Aleatoire.java:189) at Aleatoire.creerArbre(Aleatoire.java:189) at Aleatoire.creerArbre(Aleatoire.java:189) at Aleatoire.creerArbre(Aleatoire.java:190) at Aleatoire.creerArbre(Aleatoire.java:189) at Aleatoire.creerArbre(Aleatoire.java:189) at Aleatoire.creerArbre(Aleatoire.java:190) at Aleatoire.creerArbre(Aleatoire.java:189) at Aleatoire.creerArbre(Aleatoire.java:190) at Aleatoire.creerArbre(Aleatoire.java:189) at Aleatoire.creerArbre(Aleatoire.java:189) at Aleatoire.creerArbre(Aleatoire.java:190)
avec +- 1000 lignes 189 et 190 qui se répetent.
Aleatoire est le nom de ma classe.
La ligne 706 est la ligne :
Code:

1 2 int k = random.nextInt(maxAttr) + 1;
la ligne 136 est :
Code:

1 2 ListeNumAtribut temp = choisirEtPlacerAtributsUtilise(nombreAtributATester, nombreTotalAtribut);
Malheureusement il est quasiment impossible de donner un code exploitable. Ce serai trop long et pour voir le moment où ca ne marche plus , il faut le tester avec une base de donnée suffisament grande, en l'ocurence 15000 objets et chaque objets possèdent 800 attribut et une valeur de sortie.
Mon but est donc de créer des arbres de modélisation de problème(apprentissage automatique) à partir d'ensemble d'aprentissage.

Jusqu'a une taille d'apprentissage de 13000+- cela marche parfaitement.

Si j'augmente la taille, j'obtiens une erreur avec le random.

merci.

Le problème ne vient pas du random mais bien de la récursivité de ta méthode creerArbre() !

:arrow: Le nombre de récursivité est trop importante et remplit complètement le stack (on voit bien le grand nombre d'appel de la méthode creerArbre()).

Le fait que cela plante sur un appel de random() est une pure coïncidences à mon avis...

Citation:

Envoyé par jokoss

Jusqu'a une taille d'apprentissage de 13000+- cela marche parfaitement.

Si j'augmente la taille, j'obtiens une erreur avec le random.

Je viens de faire un test tout bête pour voir le nombre d'appel de méthode successif avant le stackoverflow :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public class Main { static int count = 0; public static void recursive() { count++; recursive(); } public static void main(String[] args) { try { recursive(); } catch (StackOverflowError e) { System.err.println("StackOverflowError après " + count + " appels de méthodes..."); } } }
Ce qui me donne :

Code:

StackOverflowError après 16685 appels de méthodes...

Ce qui est quand même assez proche des chiffres que tu donnes...

:arrow: La méthode random() a juste la malchance d'être la 16685 ième méthodes appelée...

Pour revenir à ton problème, il me semble qu'il y a moyen d'augmenter la taille du stack, mais cela ne ferait que "retarder" le problème...

Il serait préférable d'utiliser un code itératif à la place...

Pour cela je pense que le mieux serait d'utiliser une LinkedList (et l'interface Queue si tu es en Java 5.0) :

Tu crées une LinkedList de Noeud au début de ta méthode.
Tu y ajoutes le Noeud de base (celui passé en paramètre à la méthode).
Puis tu fais une boucle qui enlève le premier élément de la liste et qui le traite...
A la fin, au lieu de faire un appel récursif de la méthode avec les nouveaux noeuds, tu te contentes de les ajouter dans la liste et il seront traité plus tard...

Par exemple :
Code:

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 private void creerArbre(Noeud root) { // On crée une Queue qui contiendra les Noeud à traiter : Queue<Noeud> noeuds = new LinkedList<Noeud>(); // Et on y place le premier noeud : noeuds.offer(root); // La variable currentNode représente le noeud dans l'itération Noeud currentNode = null; // Tant qu'il y a des éléments dans la queue, on les traites : while ((currentNode = noeuds.poll()) != null) { // ... TON CODE ICI ... // A Supprimer : plus d'appel récursif // creerArbre(tabNoeud[0]); // creerArbre(tabNoeud[1]); // Au lieu de l'appel récursif on ajoute les noeuds dans la queue // ils seront traités plus tard... noeuds.offer(tabNoeud[0]); noeuds.offer(tabNoeud[1]); } }
Il faudra peut-être un peu adapter un peu ton code (et remplacer les return; par des continue; par exemple).

a++

05/07/2007, 15h03
jokoss
Bonjour,

J'avais vu comment augmenter la taille du tas mais je ne savais pas qu'il y avait moyen d'augmenter la taille de la pile.

J'ai donc vu qu'on pouvait spécifier la taile à l'exécution par :
Code:

1 2 java -Xss taille
J'ai également vu que la taille par défaut était de 16ko ce qui me semble tres peu.

Pour le moment , en augmentant la taille je n'ai plus de problème.

Pensez-vous qu'une version itérative accélererait l'exécution du programme ou au contraire la ralentirait?

Merci d'avoir consacré du temps à mon problème.
05/07/2007, 15h16
adiGuba

Citation:

Envoyé par jokoss

Pour le moment , en augmentant la taille je n'ai plus de problème.

Mais comme je l'ai dit ce n'est pas forcément une bonne solution : si la taille des données augmente le problème peut se renouveler...

Citation:

Envoyé par jokoss

Pensez-vous qu'une version itérative accélererait l'exécution du programme ou au contraire la ralentirait?

Aucune idée, mais je ne pense pas que cela aurait un impact significatif...

a++