[Java, Algoritmi] StackOverflowError (ordinamento-sorting)
Buona sera,
Ho implementato un algoritmo iterativo di ordinamento numerico, e questo funziona abbastanza bene; sebbene sembra essere più veloce della versione semplificata del
Tentando la strada della ricorsione per renderlo più veloce, mi si genera lo spiacevole, e ben noto errore citato nel titolo: "StackOverflowError"
Poiché con l'implementazione ricorsiva la funzione si ferma dopo aver ordinato circa $4000$ numeri(ma pare più veloce), quale può essere la motivazione dell' errore?
Grazie per l' eventuale aiuto.
Ho implementato un algoritmo iterativo di ordinamento numerico, e questo funziona abbastanza bene; sebbene sembra essere più veloce della versione semplificata del
Tentando la strada della ricorsione per renderlo più veloce, mi si genera lo spiacevole, e ben noto errore citato nel titolo: "StackOverflowError"
Poiché con l'implementazione ricorsiva la funzione si ferma dopo aver ordinato circa $4000$ numeri(ma pare più veloce), quale può essere la motivazione dell' errore?
Grazie per l' eventuale aiuto.
Risposte
Stack overflow generalmente significa che stai lavorando al di fuori dell'array. Senza il codice è difficile dirti cosa succede. Detto questo, usare la ricorsione è difficilmente un modo per rendere più veloce un codice. In linguaggi come C, C++ e Java un codice ricorsivo è quasi sempre più lento del suo "equivalente" iterativo (seppur molto più semplice da scrivere).
Buongiorno @vict85, grazie per la risposta.
In effetti con la ricorrenza il 'programma' è più lento.
Hai scritto che in linguaggi come C, C++ e Java, la ricorsione è generalmente più lenta, per cui esistono linguaggi in cui avviene l' opposto?
In effetti con la ricorrenza il 'programma' è più lento.
Hai scritto che in linguaggi come C, C++ e Java, la ricorsione è generalmente più lenta, per cui esistono linguaggi in cui avviene l' opposto?
Tentare di accedere ad elementi fuori da un array è più un "buffer" overflow che uno "stack" overflow.
In questo caso è più probabile che le chiamate ricorsive siano troppe ed esauriscano la memoria disponibile (lo stack è relativamente piccolo, in Java di default è 1 MiB). Tutte le variabili locali di una funzione occupano spazio sullo stack, e chiamando ricorsivamente la funzione il consumo di memoria aumenta linearmente.
Alcuni linguaggi/compilatori/interpreti supportano la tail cail optimization, che permette di eseguire chiamate ricorsive con consumo di memoria costante invece che lineare (in alcuni casi, non sempre). In Java credo succeda solo in rari casi, in C e C++ dipende dal compilatore/interprete e probabilmente ci sono altre limitazioni. Inoltre una chiamata a funzione può essere un'operazione relativamente costosa in questi linguaggi.
Altri linguaggi sono progettati fin dall'inizio per usare la ricorsione e queste ottimizzazioni sono parte delle specifiche, quindi non c'è differenza di prestazioni da un'implementazione iterativa. Per esempio in Haskell, dove i cicli non esistono e l'unico modo per simulare un'iterazione è usare la ricorsione (in realtà il discorso è più complicato a causa della lazy evaluation, ma il concetto è quello).
In questo caso è più probabile che le chiamate ricorsive siano troppe ed esauriscano la memoria disponibile (lo stack è relativamente piccolo, in Java di default è 1 MiB). Tutte le variabili locali di una funzione occupano spazio sullo stack, e chiamando ricorsivamente la funzione il consumo di memoria aumenta linearmente.
Alcuni linguaggi/compilatori/interpreti supportano la tail cail optimization, che permette di eseguire chiamate ricorsive con consumo di memoria costante invece che lineare (in alcuni casi, non sempre). In Java credo succeda solo in rari casi, in C e C++ dipende dal compilatore/interprete e probabilmente ci sono altre limitazioni. Inoltre una chiamata a funzione può essere un'operazione relativamente costosa in questi linguaggi.
Altri linguaggi sono progettati fin dall'inizio per usare la ricorsione e queste ottimizzazioni sono parte delle specifiche, quindi non c'è differenza di prestazioni da un'implementazione iterativa. Per esempio in Haskell, dove i cicli non esistono e l'unico modo per simulare un'iterazione è usare la ricorsione (in realtà il discorso è più complicato a causa della lazy evaluation, ma il concetto è quello).
@claudio: martedì dovevo essere un po' stanco.
"claudio86":
Tentare di accedere ad elementi fuori da un array è più un "buffer" overflow che uno "stack" overflow.
In questo caso è più probabile che le chiamate ricorsive siano troppe ed esauriscano la memoria disponibile (lo stack è relativamente piccolo, in Java di default è 1 MiB). Tutte le variabili locali di una funzione occupano spazio sullo stack, e chiamando ricorsivamente la funzione il consumo di memoria aumenta linearmente.
.
Grazie per la risposta molto articolata. Credo che quello stack molto piccolo in java sia la causa del problema..., e di ben altri.
Speravo di gestire qualche numero con questo linguaggio, ma non è progettato, credo, per questo.
Consigli su un linguaggio altrettanto semplice, per gestire i numeri?
Ad esempio mi sono accorto che Java arrotonda numeri in virgola mobile molto grandi...ma se servono tutte le cifre, pare essere un problema ricomporre il numero.
Il linguaggio Haskell non lo conoscevo, eppure esiste da molto, ed il linguaggio funzionale mi ha sempre affascinato,
mi informerò se ne vale la pena apprenderlo.
Java non è progettato per tail call optimization e uso "intenso" di funzioni ricorsive, ma è assolutamente adatto a "gestire qualche numero" (che vuol dire?). Dovrai usare un approccio iterativo, ma tutte le funzioni possono essere implementate così (anche se a volte è necessario usare uno stack esplicito).
Non mi viene in mente nessun linguaggio che non arrotondi numeri in virgola mobile molto grandi. Proprio perché sono rappresentati in virgola mobile. Un generico numero reale anche piccolo ha bisogno di infinita memoria per essere rappresentato, quindi devi per forza arrotondare. Esistono librerie per aumentare il numero di cifre significative, in Java puoi usare BigDecimal, ma nella maggior parte delle applicazioni, anche scientifiche e ingegneristiche, 16 cifre significative sono più che sufficienti.
Detto questo, potrebbero esserci linguaggi più adatti di Java per "gestire i numeri". Julia è da poco arrivato alla versione 1.0 e si propone come moderna alternativa per la programmazione scientifica. R è storicamente il linguaggio di riferimento per la statistica. Python va forte per machine learning. Fortran è il classico linguaggio per programmazione numerica.
Che obiettivi hai di preciso?
Non mi viene in mente nessun linguaggio che non arrotondi numeri in virgola mobile molto grandi. Proprio perché sono rappresentati in virgola mobile. Un generico numero reale anche piccolo ha bisogno di infinita memoria per essere rappresentato, quindi devi per forza arrotondare. Esistono librerie per aumentare il numero di cifre significative, in Java puoi usare BigDecimal, ma nella maggior parte delle applicazioni, anche scientifiche e ingegneristiche, 16 cifre significative sono più che sufficienti.
Detto questo, potrebbero esserci linguaggi più adatti di Java per "gestire i numeri". Julia è da poco arrivato alla versione 1.0 e si propone come moderna alternativa per la programmazione scientifica. R è storicamente il linguaggio di riferimento per la statistica. Python va forte per machine learning. Fortran è il classico linguaggio per programmazione numerica.
Che obiettivi hai di preciso?
In crittografia per esempio so che vengono utilizzati numeri primi, e questi sono molto grandi, non credo vengano eliminate delle cifre. Forse si usano stringhe?
I numeri primi sono interi, perché rappresentarli in virgola mobile? In ogni caso, per rappresentare interi arbitrariamente grandi è ancora necessaria infinita memoria. Nella maggior parte dei linguaggi i tipi interi sono limitati alle dimensioni dei registri hardware, tipicamente 64 bit (o fino 512 su hardware specializzato), per motivi di prestazioni, e perché sono sufficienti per la maggior parte delle applicazioni.
Quando effettivamente serve lavorare con interi arbitrariamente grandi si usano librerie apposta, per esempio BigInteger in Java, implementati grosso modo come stringhe (di byte). Sono però molto più lenti.
Quando effettivamente serve lavorare con interi arbitrariamente grandi si usano librerie apposta, per esempio BigInteger in Java, implementati grosso modo come stringhe (di byte). Sono però molto più lenti.
Buona sera, grazie mille per i suggerimenti.
Ritornando alla fonte del problema, posto un esempio di codice che genera overflow, scritto in java, quando richiama un numero $N$ troppo alto di volte la seguente funzione, che ritorna approssimativamente il valore della radice quadrata di un dato numero $x$:
La funzione richiama un identità per effettuare la radice quadrata.
Qui inserisco il valore di $x$, ed il valore $N$ che serve a terminarne l' esecuzione ed è allo stesso tempo un indice di precisione.
Ora potrei anche implementarla in BigDecimal, per avere più valori decimali di un certo valore.
Ma vorrei prima capire se è possibile risolvere il problema dell' overflow.
Buona sera, e grazie per l' eventuale aiuto.
Ritornando alla fonte del problema, posto un esempio di codice che genera overflow, scritto in java, quando richiama un numero $N$ troppo alto di volte la seguente funzione, che ritorna approssimativamente il valore della radice quadrata di un dato numero $x$:
private static double sqrt(double x, int N){
if (N>-x) {N--; return 1+(x-1)/(1+sqrt(x,N)); }
else return x;
}La funzione richiama un identità per effettuare la radice quadrata.
Qui inserisco il valore di $x$, ed il valore $N$ che serve a terminarne l' esecuzione ed è allo stesso tempo un indice di precisione.
Ora potrei anche implementarla in BigDecimal, per avere più valori decimali di un certo valore.
Ma vorrei prima capire se è possibile risolvere il problema dell' overflow.
Buona sera, e grazie per l' eventuale aiuto.
Innanzitutto: in una sola riga 1) confronti due valori, 2) modifichi una variabile, 3) chiami ricorsivamente la funzione e 4) restituisci un valore. Sono tutte operazioni separate, mettile su righe separate. In generale, dopo un punto e virgola vai sempre a capo, la leggibilità è importante.
Il problema è che chiami la tua funzione ricorsivamente N volte. Ogni volta che chiami la funzione viene consumata memoria sullo stack (almeno l'indirizzo di ritorno, più tutte le variabili locali). Se N è troppo grande lo stack non può contenere tutte le funzioni.
Hai due alternative:
- Riscrivere la funzione in modo che sia tail-recursive
- Riscrivere la funzione in modo iterativo (che è concettualmente la stessa cosa, una funzione tail-recursive è implementabile tramite iterazione)
Una funzione è tail-recursive se, ogni volta che chiama se stessa ricorsivamente, è l'ultima istruzione che esegue. La tua funzione non lo è: dopo aver chiamato se stessa deve usare il risultato nell'espressione da restituire. Quella funzione causerà uno stack overflow in qualsiasi linguaggio, non è un problema di Java.
La procedura standard per trasformare una funzione ricorsiva in una funzione tail-recursive è di usare un accumulatore. L'esempio classico del fattoriale:
Come vedi, in factorial_tail_recursive_inner() quando chiami ricorsivamente la funzione non hai più altre operazioni, restituisci direttamente il risultato. Questo permette al programma di liberare lo spazio prima della chiamata, dato che non servono più informazioni sulla funzione chiamante, quindi lo stack non cresce (semplificando molto).
Invece di usare il valore restituito dalla ricorsione mantieni un accumulatore continuamente aggiornato che viene passato lungo la ricorsione. Come vedi la soluzione iterativa è praticamente identica a quella tail-recursive. Si tratta esattamente di un ciclo implementato tramite ricorsione.
Quindi devi trovare un modo di riscrivere la tua funzione in modo che usi un accumulatore.
Il problema è che chiami la tua funzione ricorsivamente N volte. Ogni volta che chiami la funzione viene consumata memoria sullo stack (almeno l'indirizzo di ritorno, più tutte le variabili locali). Se N è troppo grande lo stack non può contenere tutte le funzioni.
Hai due alternative:
- Riscrivere la funzione in modo che sia tail-recursive
- Riscrivere la funzione in modo iterativo (che è concettualmente la stessa cosa, una funzione tail-recursive è implementabile tramite iterazione)
Una funzione è tail-recursive se, ogni volta che chiama se stessa ricorsivamente, è l'ultima istruzione che esegue. La tua funzione non lo è: dopo aver chiamato se stessa deve usare il risultato nell'espressione da restituire. Quella funzione causerà uno stack overflow in qualsiasi linguaggio, non è un problema di Java.
La procedura standard per trasformare una funzione ricorsiva in una funzione tail-recursive è di usare un accumulatore. L'esempio classico del fattoriale:
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int factorial_tail_recursive_inner(int n, int accumulator) {
if (n == 0) {
return accumulator;
} else {
int new_accumulator = n * accumulator;
return factorial_tail_recursive_inner(n - 1, new_accumulator);
}
}
int factorial_tail_recursive(int n) {
int initial_accumulator = 1;
return factorial_tail_recursive_inner(n, initial_accumulator);
}
int factorial_iterative(int n) {
int accumulator = 1; // initial_accumulator
for (int i = 0; i < n; ++i) {
accumulator = n * accumulator; // recursive step
}
return accumulator;
}Come vedi, in factorial_tail_recursive_inner() quando chiami ricorsivamente la funzione non hai più altre operazioni, restituisci direttamente il risultato. Questo permette al programma di liberare lo spazio prima della chiamata, dato che non servono più informazioni sulla funzione chiamante, quindi lo stack non cresce (semplificando molto).
Invece di usare il valore restituito dalla ricorsione mantieni un accumulatore continuamente aggiornato che viene passato lungo la ricorsione. Come vedi la soluzione iterativa è praticamente identica a quella tail-recursive. Si tratta esattamente di un ciclo implementato tramite ricorsione.
Quindi devi trovare un modo di riscrivere la tua funzione in modo che usi un accumulatore.
Ciao @claudio86,
Ho dovuto aggirare la ricorsione con un codice iterativo, per il calcolo della radice quadrata d' esempio, perché non ne venivo a capo; posto il codice e lascio a voi interventi migliorativi:
Come vedete, ho ulteriormente aggiornato il codice, ora funziona anche per valori non interi di $x$ e l' esecuzione non è più lenta per valori grandi di $x$. Accetto comunque critiche se migliorano ulterriormente il programma.
Buona giornata e grazie.
Ho dovuto aggirare la ricorsione con un codice iterativo, per il calcolo della radice quadrata d' esempio, perché non ne venivo a capo; posto il codice e lascio a voi interventi migliorativi:
private static double sqrtX(double x, double sqX){
//restituisce il valore approssimato della radice di x in funzione di x
//e della sua radice approssimata sqX
x = 1+(x-1)/(1+sqX);
return x;
}
private static double sqrt(double x, int n_cifre){
double Sq=sqrt2(x,0);
if (Sq*Sq==x) return Sq;
else return sqrt2(x,n_cifre);
}
private static double sqrt2(double x,int n_cifre){
//ottiene la lunghezza della radice quadrata di x:
int lngRadInt=Integer.toString((int)x).length();
if (lngRadInt>1) lngRadInt/=2;
double Sq=sqrtX(x,x); //calcola il primo valore approssimato della radice
double apx = Math.pow(10,-n_cifre);
double S=Sq;
Sq=sqrtX(x,Sq); //calcola il secondo valore approssimato della radice
double Q=Sq*Sq; //esegue il quadrato della radice
double diff=Math.abs(Sq-S);
//Ricalcola la radice fino all' approssimazione apx opportuna:
while (Q!=x && diff>apx){
S=Sq;
Sq=sqrtX(x,Sq);
Q=Sq*Sq;
diff=Math.abs(Sq-S);
}
//Tronca il numero alla cifra significativa opportuna:
String str = Double.toString(Sq).substring(0, n_cifre+lngRadInt+1);
Sq = Double.parseDouble(str);
return Sq; //restituisce il valore della radice quadrata di x
}
Come vedete, ho ulteriormente aggiornato il codice, ora funziona anche per valori non interi di $x$ e l' esecuzione non è più lenta per valori grandi di $x$. Accetto comunque critiche se migliorano ulterriormente il programma.
Buona giornata e grazie.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo