Discussion :

[esperance]

salut,

j'ai developper un programme en java qui permet de determiner toute les chemins possibles sans cycle entre les elements d'une matrice n*n avec est le nombre des elements a traiter.
l'algorithme qui j'ai developper est tres complexe mais pour moi au debut la complexite ne m'intersse pas mais j'ai essayer de travailler seulement sur la partie triangulaire superieur de la matrice.
mon algorithme a l'aspect suivant : pour chaque couple (di,dj) de la matrice je calcule toutes les chemins possibles (chemin de longeur 1 puis de longeur2,.....j'usqu'a chemin de longeur n-1) cette etape et repeter j'usqu'a toutes les elements sont traiteés: on peut cet algorithme par la notion de la fermeture transitive dans un graphe mais dans un graphe en utilise la matrice d'adjacence qui, cet derniere peut contenir les valuer 0 si pas de connection entre deux noeuds et 1 si oui. pour moi je travaille sur un graphe complet dans laquelle un noeud est connecter avec N-1 autres du graphe(N nombre de noeuds du graphe).
je traite la matrice ligne par ligne et je determine pour chaque couple de noeuds tous les chemins possibles: je stocke ses chemins pour chaque ligne dans vecteur globale(car ma fonction et recursive sur le vecteur de chemins a chaque niveau

le probleme recontre : java.lang.OutOfMemoryError
j'ai essayer de resoudre cette probleme avec ses trucs:
1- j'ai changer le type de mes elements de double en float
2- j'ai augmenter la taille de lancement de la JVM avec la commande Msdos suivante : java -ms300m -mx300m
avec ses truc la meme exception qui me gene:
j'ai remarque que lorsque la taille du vecteur depasse se 3000000 l'exception se lance
j'ai essayer de stocker mes elements dans un Hashtable : avant de reecrire mon prog j'ai un code de test pour la taille du Hashtable: Il signale la meme exception que le vecteur

Code :

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

1
2
3
4
5
6
7
8
public void test()
    {
     Hashtable tableHa = new Hashtable();
    for(int i=0; i<3000000;i++)
         tableHa.put(i+"", "23");        
    System.out.println(tableHa.toString());
 
    }

Est ce que vous pouvez m'aider pour ce probleme
Exemple de la sortie de mon algorithme:

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
Entre: a b c d e : 
Sortie: 
 
			Chemin=1
 
	ab ac ad ae bc bd be cd ce de 
 
			Chemin=2
 
	abc abd abe acb acd ace adb adc ade aeb aec aed bca bcd bce
	bda bdc bde bea bec bed cda cdb cde cea ceb ced dea deb dec 
 
			Chemin=3
 
	abcd abce abdc abde abec abed acbd acbe acdb acde aceb aced
	adbc adbe adcb adce adeb adec aebc aebd aecb aecd aedb aedc 
	bcad bcae bcda bcde bcea bced bdac bdae bdca bdce bdea bdec 
	beac bead beca becd beda bedc cdab cdae cdba cdbe cdea cdeb 
	ceab cead ceba cebd ceda cedb deab deac deba debc deca decb 
 
			Chemin=4
 
	abcde abced abdce abdec abecd abedc acbde acbed acdbe acdeb
 	acebd acedb adbce adbec adcbe adceb adebc adecb aebcd aebdc 
	aecbd aecdb aedbc aedcb bcade bcaed bcdae bcdea bcead bceda 
	bdace bdaec bdcae bdcea bdeac bdeca beacd beadc becad becda 
	bedac bedca cdabe cdaeb cdbae cdbea cdeab cdeba ceabd ceadb 
	cebad cebda cedab cedba deabc deacb debac debca decab decba

apres cette etape je prends chaque chemin et je calcule son score selon les valeurs de la matrice formes par ses elements et je remplie une matrice de sortie

[®om]

En gros tu veux trouver toutes les combinaisons possibles d'un ensemble (2 parmi 5, 3 parmi 5, 4 parmi 5... pour l'ensemble { a b c d e })?

[Celeborn]

Bonsoir,

A mon avis, il faudrait regarder du côté de ton algo, c'est souvent le cas lorsqu'il y a dépassement de memoire de la jvm. As tu besoin de conserver en mémoire tout tes résultats ? Si comme le suppose Rom tu souhaites juste faire du dénombrement, est-ce que la sortie ne suffirais pas ? Peut-être écrire au fur et à mesure du calcul.

[Baptiste Wicht]

java -ms300m -mx300m

Ce n'est pas ça qu'il faut employer, mais c'est

Code :

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

java -Xms300m -Xmx300m

[pseudocode]

idem wichtounet, c'est Xms et Xmx pour modifier la memoire utilisable pas la JVM

conseil: ecrire un post dans le forum "Algorithmie" parceque ca me parrait pas super top optimum comme algo

[Celeborn]

Augmenter la taille mémoire de la jvm ne fera que déplacer le problème, il resurgira, plus loin, plus tard, mais tout aussi fatal.

[Baptiste Wicht]

Augmenter la taille mémoire de la jvm ne fera que déplasser le problème, il resurgira, plus loin, plus tard, mais tout aussi fatal.

Pas toujours...

Avec 64Mo, tu ne peut pas faire grand chose...

Souvent tu es dans l'obligation d'augmenter la taile du tas de la JVM, même si ton algo est hyper optimisé...

[Celeborn]

Je te l'accorde il est parfois indispensable d'allouer d'avantage de taille mémoire que celle par défaut, ..., mais seulement quand la taille de objet est controlé, fixé et surtout réduit à son maximum.
Dans le cas de son calcul de dénombrement, la taille explose de manière exponentielle là où elle ne devrait pas.

"Espérance", à mon avis ce que ton prog fait, est qu'il stocke en mémoire ton résultat, et une fois terminé il reparcours ta list et ecrit le résultat sur ta sortie. En écrivant au fur et à mesure sur la sortie, tu résolverais ton problème. Au pire montre moi ton code et j'essayerai de t'aider plus concrètement dans ton optimisation.

Avec 64Mo, tu ne peut pas faire grand chose...

64 Mo c'est déjà énorme !!! et cela suffit à développez 90% des applis voir plus, c'est par exemple la taille en mémoire d'un eclipse. Rappelons-nous qu'il y a une époque pas si lointaine 64 Mo était la taille des barettes de mémoire, alors que le ce type de dénombrement cela fait des lustres qu'on le réalise.

[Baptiste Wicht]

64 Mo c'est déjà énorme !!! et cela suffit à développez 90% des applis voir plus, c'est par exemple la taille en mémoire d'un eclipse.

Tu as quoi comme Eclipse toi

Au boulot, avec quelques plugins et un projet assez conséquent d'ouvert, je suis toujours entre 120 et 250 Mo d'utilisés, et parfois ca monte encore plus haut...

[pseudocode]

Tu as quoi comme Eclipse toi

Au boulot, avec quelques plugins et un projet assez conséquent d'ouvert, je suis toujours entre 120 et 250 Mo d'utilisés, et parfois ca monte encore plus haut...

Yes. Pareil... 128Mo c'est le minimum pour un petit projet Java sous le JDT.
Des que je commence a ouvrir un projet un peu gros (CVS) avec qq plugin eclipse (UML,...) j'ai vite des OutOfMemory: 256Mo c'est la bonne config pour moi.

[Celeborn]

Eclipse sans laisser ouvert tout vos projets et plein de plugins peu facilement tourner sur une centaine de mega, et peut bien évidement toujours trouver moyen d'augmenter de beaucoup... Rapellons tout de même que Eclipse est une véritable usine à gaz. Donc désolé mais je persiste à dire que 64 Mo c'est largement suffisant pour la plupart des personnes qui poste dans ce forum. L'informatique n'est pas né avec l'invention de capacité de ram > 256 Mo, java non plus.

Ne croyez-vous pas que si la limite fixé par défaut pour la jvm était "insuffisant pour faire qqchose", celle-ci aurait été repoussée ?

Conseiller à Espérance d'augmenter sa taille resolvera sa limite de 300000 mais à coup sur, une nouvelle limite inhérente à son algo apparaitera aussitôt, donc ce n'est pas une solution viable...

En revanche il est parfois en effet indispensable d'augmenter la taille mémoire, car la compléxité de l'appli son nombre d'objet, et leurs capacités sont trop important pour être contenu dans l'intervalle.