Discussion :

[jokoss]

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.

[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

[jokoss]

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 :

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
 
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 :

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
 
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.

[CyberChouan]

Code :

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

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

[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

[CyberChouan]

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 :

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
 
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;
}

[jokoss]

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 :

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
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.

[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.

[adiGuba]

Salut,

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++

[jokoss]

Bonjour,

voici ma stack trace :

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
 
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 :

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

1
2
 
int k = random.nextInt(maxAttr) + 1;

la ligne 136 est :

Code :

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

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.

[adiGuba]

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

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...

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 :

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
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 :

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

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

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

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 :

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
	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++

[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 :

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

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.

[adiGuba]

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...

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++