[JAVA] Problema StackOverFLow

[Sprizzy]

Ciao a tutti,
ho scritto un programma in java in cui vi sono 3 metodi che si richiamano ricorsivamente in questo ordine:
1-->2-->3-->1-->2... ecc e fin qui non ho riscontrato alcun problema(ma così è incompleto).
Il programma completo consta di 4 metodi che si dovrebbero richiamare così:
1-->2-->3-->4-->1-->2 .. ecc.
Ora mi da stackOverflowerror ... ho pensato che il programma andasse in crash a causa di una ricorsione infinita. Così ho creato una variabile che si decrementa ogni volta che il 4 metodo viene richiamato,per vedere se mi dava lo stesso errore pur facendolo eseguire un numero n finito di volte. Questo programma l'ho fatto girare su più pc.. su alcuni da errore cmqe su altri no. Ho provato a mettere come opzione in esecuzione java nome -Xmx512m ..ma niente!
In determinati istanti n=10000 per esempio va bene... ma in altri lo devo decrementare altrimenti mi ridà stackOverFlowerror!!
...
Il programma apre un file di testo di circa 20 mega e memorizza i dati in un array che viene elaborato nei metodi.
So disperata!

[banryu79]

Domanda: se in esecuzione la virtual machine lancia uno StackOverflowError, tu sai cosa significa?
Indizio: la dumentazione descrive StackOverflowError così:

Thrown when a stack overflow occurs because an application recurses too deeply.



Ho provato a mettere come opzione in esecuzione java nome -Xmx512m ..ma niente!

La memoria heap è diversa dallo stack.
Le istanze create con new vengono allocate nella memoria heap.
Quindi aumentare lo heap può essere utile se il tuo programma alloca molte istanze o comunque esegue operazioni avide di ram.

Il "problema" nel tuo programma, a naso, è che esegui troppe chiamate ricorsive... troppe almeno per lo stack, che viene saturato tutto prima che il numero effettivo di chiamate ricorsive eseguite a runtime nel tuo programma venga espletato completamente.

Probabilmente doresti cercare di modellare la soluzione al tuo problema evitando di fare uso di così tante chiamate ricorsive.
Che problema stai cercando id risolvere con il tuo programma?

[Sprizzy]

Il problema è che è l'algoritmo che richiede chiamate ricorsive.
E' inevitabile: con un metodo creo k matrici dove k=num nodi del grafo che elaboro poi se è verificATA UNA CERTA CONDIZIONE RICHIAMO IL METODO 3 CHE A SUA volta obbligatoriamente deve richiamare il 4 metodo che richiama il 1.In pratica io lavoro con un grafo... ogni elemento dell'array è un arco del grafo.
il lavoro consiste nell'eliminare ed aggiungere ricorsivamnte gli archi da grafo che ho creato leggendo il file di testo.
Non potrei organizzare il lavoro altrimenti, non posso cambiare l'algoritmo che mi è stato imposto di utilizzare.
Non conosco bene l'errore che mi da la jvm per questo chiedo aiuto... ad esempio potrei impostare da qualche parte l'utilizzo di una memoria dedicata all'esecuzione del programma più grande?? Altrimenti nn so proprio come risolvere... GRAZIE :)))

[banryu79]

Il problema è che è l'algoritmo che richiede chiamate ricorsive.
[cut]

1) In generale, un algoritmo ricorsivo può essere trasformato in uno iterativo.

2) Se non stai eseguendo un compito scolastico oppure se hai carta bianca nell'implementare la tua soluzione, per Java, esistono JGraph/JGraphT, due librerie (tra le millemila) per lavorare con i grafi (la prima per la visualizzazione grafica, la seconda per algoritmi e strutture dati associate).

3) Se ci spieghi cosa devi fare di preciso con questi grafi magari salta fuori che ti servono uno o più algoritmi già esistenti che magari devi solo "piegare" un po' alle tue esigenze specifiche (in JGraph sono già presenti delle implementazioni di detti algoritmi e/o trovi dei "componenti" da usare per costruire i tuoi algoritmi).
In ogni caso, nell'implementare la soluzione bisogna tenere conto della tecnologia/linguaggio/strumento che si sta usando.
Se il tuo algoritmo, così com'è, sta saturando lo stack a furia di chiamate ricorsive, potrà anche rappresentare, sulla carta, una soluzione teorica corretta del problema ma ovviamente non va bene in pratica, ergo devi trovare un'altra strada.

[PGI-Bis]

Prova ad aumentare la dimensione dello stack. Non so quale sia la dimensione predefinita ma ho letto che 128k è normale, 2 megabyte è gigantesca. Il comando è "-Xss" seguito dalla dimensione

java -Xss512k il main

[Sprizzy]

Allora il programma fa le seguenti cose:
Legge un file di testo di circa 20 mega.
Ogni riga la salvo in un oggetto arco dell'array.
L'oggetto arco ha dei campi:
coda testa popolazione costo pixel servito
la coda e la testa rappresentano i nodi.
Grafo base()
{Prende in ingresso l'array di archi e confronta quelli paralleli(stessa testa e coda), l'arco con il costo minore verrà memorizzato anche in un nuovo array piu piccolo. Mentre gli altri rimangono cmqe nel vecchio array.
}
MatriceD(){
Crea una matrice dove in posizione i,j vi è un costo molto elevato e in pos i,i costo 0... per l'algoritmo è la matrice iniziale.}
Floyd(){
crea k matrici con k=num di nodi del grafo. in ogni matrice k sostituisce in posizione i,j e i,i il costo se e solo se il percorso nuovo da i a j costa meno del precedente. ad esempio se sto in matrice k=3 io posso utilizzare per arrivare da uyn qualsiasi nodo i,j solo gli archi 1 2 e 3 e cosi via. infine qst metodo controlla se in pos i,i vi è un costo<0. se vero si avvia il metodo seguente(cicloN) altrimenti da un risultato(ossia quanta popolazione viene servita).. con elementi i,i negativi non si avrebbe una soluzione ammisibile.}
cicloN(){
Trova il cammino, cioè i nodi, attrtaversati per arrivare dal nodo i al nodi i stesso(bisogna controllare solo la positività degli alementi della diagonale principale). una volta risaliti al ciclo negativo si elimina un arco del ciclo secondo un criterio(costo minimo)}
..
Questo è il metodo che mi da problemi..
NuovoGB(){
ho la posizione in grafo base dell'arco eliminato ed in tale posizione provo a riaggiungere un arco a lui parallelo che si trova nel vecchio array(per servire + popolazione possibile). Ovviamente gli archi eliminati nn verranno piu ripescati sennò il programma nn terminerebbe mai...
}
ora si richiama matriceD...
il programma termina quando in floyd nn si trovano piu elementi <0 sulla diagonale principale...

[WarDuck]

Sei sicura che hai implementato correttamente l'algoritmo?

La prima cosa da fare in questi casi è controllare se hai specificato correttamente la condizione base per la quale esci dalla ricorsione.

Inoltre ti suggerisco di provare prima con un set di dati più piccolo, in modo da facilitare anche il debug.

[Sprizzy]

Sì sì certamente ho lavorato con file moto più piccoli e non da' errore.
Inoltre ho messo la condizione di cui parli... :(

[Sprizzy]

Vi ringrazio... alla fine ho risolto! :)