[Java, Algoritmi] StackOverflowError (ordinamento-sorting)

[curie88]

Buona sera,

Ho implementato un algoritmo iterativo di ordinamento numerico, e questo funziona abbastanza bene; sebbene sembra essere più veloce della versione semplificata del <bubble sort>, cioè circa il doppio più veloce, ma più lento di circa il doppio dell' <insert sort> iterativo e molto più lento del <merge sort> iterativo.
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.

[vict85]

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

[curie88]

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?

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

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

[vict85]

@claudio: martedì dovevo essere un po' stanco.

[curie88]

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.

[claudio86]

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?

[curie88]

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?

[claudio86]

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.

[curie88]

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

Codice:

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.