Discussion :

[IMPRO]

Bonsoir,
j'ai fait un programme qui résout le problème de voyageur de commerce( le problème consiste, à partir d'une matrice qui contient des villes ainsi la distance entre ces villes, de trouver le meilleur chemin ( le plus court) à emprunter pour parcourir toutes les ville ), qui est un problème assez connu en recherche opérationnelle. ce programme suit un algorithme de recherche profondeur, je sais que ce c'est un peu flou ce que je viens de dire pour les gens qui connaissent pas ce problème, mais je vais exposer mon problème en exposant le fonctionnement de mon programme.
à partir de ma matrice j'extrais une ville et j'enregistre dans un objet toute les ville voisines (qu'on peut acceder à partir de cette ville) sous forme de liste (ArrayList) anis d'autre parametre comme le nom de la ville, une liste des villes parcouru jusqu'à cette ville,... Puis j'empile dans une PILE(Stack). Après je dépile un voisin et je fait la même chose pour le voisin (enregistrer ces voisins,... et je l'empile) jusqu'à ce qu'une ville n'aurait pas de voisin. et ainsi de suite.
quand j'ai par exemple moins de 15 villes dans ma matrice sa marche nickel, mais au de-las je reçois des messages d'erreurs différents mais la même exception.

Code :

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

Exception in thread "AWT-EventQueue-0" java.lang.OutOfMemoryError: GC overhead limit exceeded

ou bien une exception

Code :

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

Java Heap space

est ce que quelqu'un peut m'expliquer la raison de cette erreur, et comment faire des teste mémoire (avoir l'état de la mémoire à un instant donnée), et c'est qoui GC overhead et Java heap space
merci pour votre aide.

[hwoarang]

Comme tu dois le savoir, en java, la memoire est gérée par la machine virtuelle. Ainsi, tu n'as qu'a créer des objets et lorsqu'ils ne sont plus utilisés, le garbage collector (GC) libere la mémoire qui leur etait allouée. Cela se fait dans un thread qui tourne en parallele avec l'appli.
L'exception "GC overhead limit exceeded" arrive quand le JVM passe trop de temps à libérer de la mémoire et pas assez dans le programme.
Pour eviter cette exception, tu peux ajouter -XX:-UseGCOverheadLimit dans la ligne de commande. Cela dit, ca ne changera rien au fait que tu passes beaucoup de temps à libérer de la mémoire et pas beaucoup à executer le programme.

L'exception "Java Heap space" arrive quand tu n'as plus de mémoire disponible. Il peut y avoir 2 raisons :
1 - Tu as une boucle infinie qui consomme de la mémoire (typiquement, un while infini ou tu ajoutes un objet dans une arraylist)
2 - Trop de consommation mémoire

Dans ton cas, la solution 2 semble plus probable. Il y a 2 solutions :
- Optimiser le programme pour consommer moins de mémoire
- Augmenter la mémoire disponible en ajoutant -Xmx1024M à la ligne de commande.

En ce qui concerne les outils de debug, ils dependent de ton IDE...

[JoeChip]

Si mes souvenirs sont exact, il s'agit d'un problème NP-complet, donc, par définition, le besoin de ressources est en relation exponentielle avec le nombre de noeuds. Donc forcément, le maximum de noeuds que tu pourras calculer est très bas. Là, en plus, si j'ai bien suivi, tu utilises un algo récursif, or les algos récursifs sont notoirement gourmands en mémoire...

Moralité : tu vas peut-être réussir à finalement calculer la solution pour 15 villes, peut-être même 16 ou 17, mais tu auras du mal à aller bien au-delà... Les seuls algos opérationnels pour un grand nombre de villes sont heuristiques, par exemple la méthode des fourmis.

[Mako 5013]

J'ai déjà eu à traiter ce problème en cours, et je rejoins totalement BenWillard. Un total de 15 villes est déjà un beau score (il faut tout de même tester 15! possibilités, soit la bagatelle de 1.31*10^12...).

J'ajouterais que si tu veux avoir la meilleure solution, il te faut tester toutes les possibilités. Sinon, il faut utiliser des méthodes heuristiques (les fourmis comme déjà mentionné, ou bien Astar par exemple), mais ces dernières ne peuvent pas garantir un résultat optimal. Elles essayent juste de trouver un chemin "qui à l'air pas trop mal" (plus ou moins "pas trop mal" suivant l'heuristique choisie).

Mako.

[thelvin]

Oui, enfin, on sait que les problèmes NP-complets consomment des ressources exponentielles, mais avec la méthode indiquée, ces ressources c'est censé être du temps, pas de la mémoire.
Quand on empile, on a pas d'explosion combinatoire, en tout cas tant qu'on pense à dépiler.

À mon avis, là il y a empilage de trop de données redondantes : à quoi ça sert de stocker à chaque fois la liste de toutes les villes atteignables, c'est déjà dans la matrice, pourquoi le recopier ? Il y a sans doute d'autres redondances de ce genre.

[IMPRO]

Merci pour vos réponses.

thelvin
à quoi ça sert de stocker à chaque fois la liste de toutes les villes atteignables, c'est déjà dans la matrice, pourquoi le recopier

je suis obligé de les stocker parce qu'il faut parcourir les villes juste une fois. je m'explique, par exemple si j'ai par exemple 4 villes : "A","B","C" et "D" et toutes ces villes reliées entre elles. donc si je démarre de "A" par exemple alors je dois stocker dans une liste ces fils qui seront (B->C->D), et à partir de "A'' j'atteins "B" donc mon chemin est pour le moment et " A=>B " . Après je stock les fils de "B" qui sont (C->D) et NON (A->C->D). et ainsi de suite ... c'est pour sa je dois enregistrer dans une liste.

mais j'ai une question, par exemple si je lance mon application pour 15 villes ( avec un bouton)

Code :

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

1
2
3
4
private void jButton3ActionPerformed(java.awt.event.ActionEvent evt) {                                         
        // TODO add your handling code here:
        Profondeur pvc = new Profondeur();
    }

et j'ouvre le gestionnaire de taches, il consomme 400mo de RAM.
et si je lance une deuxième fois avec le même bouton (sans fermer l'application), je constate que la mémoire utilisé pour ce programme est de ~ 800mo !!! alors que normalement la mémoire de la première exécution devrait être libéré.

[IMPRO]

BenWillard:
.. Les seuls algos opérationnels pour un grand nombre de villes sont heuristiques

exactement. j'ai implémenté un algorithme heuristique inspiré de l'algorithme de Kruskal, et sa marche très bien. j'ai essayé jusqu'à 500 villes et sa dure moins d'une minute d'exécution.

[thelvin]

je suis obligé de les stocker parce qu'il faut parcourir les villes juste une fois.

Oui, mais il suffit de maintenir un seul Set de toutes les villes déjà visitées, qu'on se passe d'appel en appel, au lieu d'en empiler encore et encore à chaque fois.

C'est passablement plus économique : pour N villes, on a maximum 1 Set de N éléments en mémoire. C'est avec ce genre de raisonnements qu'on fait ou on évite des explosions combinatoires en mémoire.

mais j'ai une question, par exemple si je lance mon application pour 15 villes ( avec un bouton)

Code :

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

1
2
3
4
private void jButton3ActionPerformed(java.awt.event.ActionEvent evt) {                                         
        // TODO add your handling code here:
        Profondeur pvc = new Profondeur();
    }

et j'ouvre le gestionnaire de taches, il consomme 400mo de RAM.
et si je lance une deuxième fois avec le même bouton (sans fermer l'application), je constate que la mémoire utilisé pour ce programme est de ~ 800mo !!! alors que normalement la mémoire de la première exécution devrait être libéré.

Pas forcément, la mémoire peut attendre un peu pour être libérée, ça dépend où en est le garbage collector. Tant que tu atteins pas la limite de mémoire il se sent pas obligé de passer.
Bon, par ailleurs, une fois que Java a réclamé 800Mo de mémoire, il n'en libérera pas, il la gardera pour lui. Il peut ne plus rien en faire, mais il se la garde pour le moment où il voudra y mettre des trucs. Pas la peine d'attendre qu'elle se libère, ça n'arrivera pas.

[tchize_]

heu si (de mémoire depuis java 6), java rend la mémoire inutilisé au système après un certain temps, mais ce n'est pas le coeur du problème. Le coeur c'est que ton algo bouffe, bouffe et bouffe encore de la mémoire, ce qui est la cause de tes erreurs

[IMPRO]

il bouffe de la mémoire mais j'ai pas trouvé mieux pour optimiser mon programme. mais j'avais en tête que si j'instancie un objet de classe par exemple :

Code :

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

1
2
 
ma_classe obj1 = new ma_classe(arg1,arg2);

et apres j'affecte une valeur à cette obj1

Code :

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

1
2
 
obj1 = new ma_classe(arg3,arg4);

normalement Java va libérer l'espace mémoire de la première instanciation. mais ce n'est pas le cas !!

[tchize_]

il ne le libérera que si ton instance n'est pas utilisé ailleurs. Comem t'empile plein de trucs, je suppose que c'est là qu'elle traine

[IMPRO]

oui, la pile est tout le temps pleine, en plus avec des objet trop complexe. d'ailleurs l'objet empilé contient :
liste des noeuds peres | nom du noeud | cout | niveau | nombre de fils | liste des fils |
mais de toute façon j'ai pas eu le choix pour applique l'algorithme recherche profondeur pour résoudre le problème de voyageur de commerce.
merci encore une fois pour toutes les réponse

[hwoarang]

Basiquement, j'ajouterais que le fait d'avoir une exception "GC overhead limit exceeded" suppose la création/destruction d'un grand nombre d'objets. Si j'avais des optimisations à faire, je regarderais de ce coté la pour créer moins d'objets temporaires...

Au passage, je rappelle (meme si ca a deja été dit) que le fait de ne pas avoir de reference vers un objet n'implique pas que le gc va le ramasser tout de suite. Il passera à l'occasion ou bien s'il y a besoin de mémoire.

[tchize_]

le GC overhead limit est souvent liée au manque de mémoire. Du coup le GC dois tourner à plein régime très souvent et n'arrive à ramasser que des miettes.


Typiquement:

il reste 50k disponible, tu veux allouer 60k, le GC tourne, il ramasse 30k, ce qui te laisse après allocation 20k. Tu libère un objet de 15k, tu refait une allocation de 30k, le gc retourne à plein régime, libère les maleheureux 15k, alloue, il te reste 15k, etc....

T'aura plus vite le GC overhead si ton algo fait alloue N méga par petite tranches, tandis que tu aura plutot un outofmemory direct si t'alloue par grosse tranche.

[IMPRO]

Merci.
j'ai remarqué en utilisant je gestionnaire de tâche de Windows, que mon programme peut utiliser jusqu'à 1Go de RAM. Quand il arrive a ce niveau l'exception est levée.

hwoarang:
Augmenter la mémoire disponible en ajoutant -Xmx1024M à la ligne de commande.

j'ai pas compris sa est ce que vous pouvez svp m'expliquer d'avantage comment procéder.

[deathness]

Cela augmente la taille de la mémoire alloué a ton process, et retarde dont les outOfMemory.

Il faut pour cela le rentrer dans les arg de ta vm.

Tu lances ton prog via quel IDE?

[hwoarang]

Lors de l'execution du jar, il faut ajouter -Xmx2048M (par exemple pour 2Go) à la ligne de commande. C'est à dire faire un truc du genre :

Code :

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

java -Xmx2048M -jar monJar.jar

Pour debugger, ca dépend de l'IDE. Dans Eclipse, il faut aller dans "run configurations", onglet "Arguments" puis ajouter -Xmx2048M dans "VM arguments".

[atha2]

Autrement tu peux toujours essayer de stocker des SoftReference dans ta pile. Mais c'est une solution à l'arrache.

[tchize_]

si on avait le code principal, on pourrais déjà regarder ce qui se passe

[deathness]

si on avait le code principal, on pourrais déjà regarder ce qui se passe

Effectivement, le problème doit surtout être une non optimisation/problèmes sur son algo.