In che modo il tuo linguaggio preferito gestisce la ricorsione profonda?[Chiuso]
https://stackoverflow.com/questions/233013
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Recentemente ho iniziato a studiare Python e sono rimasto piuttosto sorpreso di trovare un limite di ricorsione profonda di 1000 (per impostazione predefinita).Se lo imposti abbastanza alto, circa 30000, si blocca con un errore di segmentazione proprio come C.Tuttavia, C sembra andare molto più in alto.
(Quelli di Python si affrettano a sottolineare che è sempre possibile convertire funzioni ricorsive in funzioni iterative e che sono sempre più veloci.Questo è vero al 100%.Non è proprio questo l'argomento della mia domanda però.)
Ho provato lo stesso esperimento in Perl e da qualche parte circa 10 milioni di ricorsioni ha consumato tutti i miei 4 giga di RAM e ho usato ^C per smettere di provare.Chiaramente Perl non usa lo stack C, ma usa una quantità ridicola di memoria quando ricorre, il che non è terribilmente scioccante considerando quanto lavoro deve fare per chiamare le funzioni.
Ho provato con Pike e sono rimasto completamente sorpreso di ottenere 100.000.000 di ricorsioni in circa 2 secondi.Non ho idea di come sia successo, ma sospetto che abbia appiattito la ricorsione a un processo iterativo: non sembra consumare memoria aggiuntiva mentre lo fa.[Nota:Pike appiattisce i casi banali, ma fa dei segfault su quelli più complicati, o almeno così mi hanno detto.]
Ho utilizzato queste funzioni altrimenti inutili:
int f(int i, int l) { if(i<l) return f(i+1,l); return i; }
sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] };
def f(i,l):
if i<l:
return f(i+1,l)
return i
Sono molto curioso di sapere come altri linguaggi (ad esempio PHP, Ruby, Java, Lua, Ocaml, Haskell) gestiscono la ricorsione e perché la gestiscono in questo modo.Inoltre, nota se fa differenza se la funzione è "ricorsiva in coda" (vedi commento).
Soluzione
" Le persone di Python sono veloci nel sottolineare che puoi sempre convertire le funzioni ricorsive in funzioni iterative e che sono sempre più veloci "
Questo è vero, ma se è davvero così facile, perché Python non lo fa per me, in modo che il mio codice possa apparire il più semplice possibile? (Lo dico non per sbattere gli implementatori di Python, ma perché la risposta spiega il problema).
Le ottimizzazioni della ricorsione sono presenti nei linguaggi funzionali fin dal XIV secolo o qualcosa del genere. Le implementazioni di Haskell, CAML, Lisp in genere convertono almeno le funzioni ricorsive della coda in iterazioni: sostanzialmente lo fai individuando che è possibile, cioè che la funzione può essere riorganizzata in modo tale che nessuna variabile locale diversa dal valore restituito venga utilizzata dopo la chiamata ricorsiva . Un trucco per rendere possibile se c'è qualche lavoro fatto sul valore restituito ricorrente prima del ritorno, è introdurre un & Quot; accumulatore & Quot; parametro. In termini semplici, ciò significa che il lavoro può essere effettivamente svolto sulla via & Quot; down & Quot; invece che sulla strada " su " ;: cerca "come rendere una funzione ricorsiva di coda" per i dettagli.
I dettagli effettivi della trasformazione di una funzione ricorsiva di coda in un loop sono fondamentalmente il jigger con la convenzione di chiamata in modo da poter " eseguire la chiamata " semplicemente impostando i parametri e tornando indietro all'inizio della funzione, senza preoccuparsi di salvare tutte quelle cose nell'ambito che sai di non usare mai. In termini di assemblatore, non è necessario preservare i registri di salvataggio dei chiamanti se l'analisi del flusso di dati ti dice che sono inutilizzati oltre la chiamata e lo stesso vale per qualsiasi cosa nello stack: non devi spostare il puntatore dello stack su una chiamata se non ti dispiace " il tuo " un po 'di stack viene scarabocchiato dalla prossima ricorsione / iterazione.
Contrariamente a come hai parafrasato la gente di Python, convertire una funzione ricorsiva generale in una iterazione non è banale: per esempio se è multiplo ricorsivo, in un semplice approccio avresti comunque bisogno di uno stack.
La memoizzazione è una tecnica utile, sebbene, per funzioni arbitrariamente ricorsive, che potresti cercare se sei interessato ai possibili approcci. Ciò significa che ogni volta che viene valutata una funzione, si attacca il risultato in una cache. Per usarlo per ottimizzare la ricorsione, fondamentalmente, se la tua funzione ricorsiva conta & Quot; down & Quot ;, e la memorizzi, allora puoi valutarla iterativamente aggiungendo un ciclo che conta & Quot; up < !> quot; calcolare a turno ciascun valore della funzione fino a raggiungere l'obiettivo. Questo utilizza pochissimo spazio di stack a condizione che la cache dei memo sia abbastanza grande da contenere tutti i valori necessari: ad esempio se f (n) dipende da f (n-1), f (n-2) ef (n -3) hai solo bisogno di spazio per 3 valori nella cache: man mano che sali puoi scalare la scala. Se f (n) dipende da f (n-1) ef (n / 2), hai bisogno di molto spazio nella cache, ma comunque inferiore a quello che utilizzeresti per lo stack in una ricorsione non ottimizzata.
Altri suggerimenti
Questa è più una domanda di implementazione che una domanda di lingua. Non c'è nulla che impedisca a un (stoopid) implementatore di compilatori C di limitare anche il loro stack di chiamate a 1000. Ci sono molti piccoli processori là fuori che non avrebbero spazio di stack anche per molti.
(La gente di Python è pronta a sottolineare che puoi sempre convertire le funzioni ricorsive in funzioni iterative e che sono sempre più veloci. È vero al 100%. Non è proprio quello di cui mi occupo.)
Forse lo dicono, ma questo non è del tutto corretto. La ricorsione può sempre essere convertita in iterazione, ma a volte richiede anche l'uso manuale di uno stack . In tali circostanze, ho potuto vedere la versione ricorsiva più veloce (supponendo che tu sia abbastanza intelligente da fare semplici ottimizzazioni, come estrarre dichiarazioni non necessarie al di fuori della routine ricorsiva). Dopotutto, lo stack spinge le chiamate di procedura circostanti sono un problema ben limitato che il compilatore dovrebbe sapere come ottimizzare molto bene. Le operazioni manuali dello stack, d'altra parte, non avranno un codice di ottimizzazione specializzato nel compilatore e sono suscettibili di avere tutti i tipi di controlli di integrità dell'interfaccia utente che richiederanno cicli extra.
È possibile che la soluzione iterativa / stack sia sempre più veloce in Python . Se è così, questo è un fallimento di Python, non di ricorsione.
PHP ha un limite predefinito di 100 prima che muoia:
Fatal error: Maximum function nesting level of '100' reached, aborting!
Modifica: puoi modificare il limite con ini_set('xdebug.max_nesting_level', 100000);, ma se superi le 1150 iterazioni si verificano arresti anomali di PHP:
[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.
C # /. NET utilizzerà la ricorsione della coda in una particolare serie di circostanze. (Il compilatore C # non emette un codice operativo tailcall, ma il JIT implementerà la ricorsione della coda in alcuni casi .
Shri Borde ha anche un post su questo argomento . Ovviamente, il CLR cambia continuamente e con .NET 3.5 e 3.5SP1 potrebbe essere cambiato di nuovo rispetto alle chiamate di coda.
Utilizzando quanto segue nella console interattiva F #, è stato eseguito in meno di un secondo:
let rec f i l =
match i with
| i when i < l -> f (i+1) l
| _ -> l
f 0 100000000;;
Ho quindi provato una traduzione diretta, ad esempio
let rec g i l = if i < l then g (i+1) l else l
g 0 100000000;;
Stesso risultato ma compilazione diversa.
Ecco come appare f quando tradotto in C #:
int f(int i, int l)
{
while(true)
{
int num = i;
if(num >= l)
return l;
int i = num;
l = l;
i = i + 1;
}
}
g , tuttavia è tradotto in questo:
int g(int i, int l)
{
while(i < l)
{
l = l;
i++;
}
return l;
}
È interessante notare che due funzioni sostanzialmente uguali sono rese diversamente dal compilatore F #. Mostra anche che il compilatore F # ha un'ottimizzazione ricorsiva della coda. Pertanto, questo dovrebbe essere eseguito fino a quando non raggiungo il limite per gli interi a 32 bit.
Secondo questa discussione, circa 5.000.000 con java, 1 GB di RAM. (e quello, con la versione "client" dell'hotspot)
Questo era con un stack (-Xss) di 300Mo.
Con un'opzione -server , che potrebbe essere aumentato.
Inoltre si può provare a ottimizzare il compilatore ( con JET per esempio) per ridurre il impilare sopra ogni livello.
In alcuni casi non patologici (come il tuo), (ultimo) Lua utilizzerà ricorsione di chiamata in coda , vale a dire. salterà semplicemente senza spingere i dati in pila. Quindi il numero di cicli di ricorsione può essere quasi illimitato.
Testato con:
function f(i, l)
if i < l then
return f(i+1, l)
end
return i
end
local val1 = arg[1] or 1
local val2 = arg[2] or 100000000
print(f(val1 + 0, val2 + 0))
Anche con:
function g(i, l)
if i >= l then
return i
end
return g(i+1, l)
end
e ho persino provato la ricorsione incrociata (f chiamando ge g chiamando f ...).
Su Windows, Lua 5.1 utilizza circa 1,1 MB (costante) per eseguirlo, termina in pochi secondi.
Esecuzione di Ruby 1.9.2dev (2010-07-11 revisione 28618) [x86_64-darwin10.0.0] su un vecchio MacBook bianco:
def f
@i += 1
f
end
@i = 0
begin
f
rescue SystemStackError
puts @i
end
restituisce 9353 per me, il che significa che Ruby fa schifo con meno di 10.000 chiamate in stack.
Con ricorsione incrociata, come:
def f
@i += 1
g
end
def g
f
end
va a male nella metà del tempo, a 4677 (~= 9353 / 2).
Posso spremere qualche altra iterazione racchiudendo la chiamata ricorsiva in un proc:
def f
@i += 1
yield
end
@i = 0
@block = lambda { f(&@block) }
begin
f(&@block)
rescue SystemStackError
puts @i
end
che arriva fino a 4850 prima di generare errori.
Visual Dataflex impilerà l'overflow.
Sono un grande fan della programmazione funzionale e poiché la maggior parte di questi linguaggi implementa l'ottimizzazione delle chiamate di coda, puoi fare affidamento quanto vuoi :-P
Comunque, praticamente, devo usare molto Java e usare anche Python molto. Non ho idea di quale limite abbia Java, ma per Python avevo effettivamente pianificato (ma non l'ho ancora fatto) di implementare un decoratore che avrebbe chiamato la coda per ottimizzare la funzione decorata. Non stavo pianificando questo per ottimizzare la ricorsione, ma principalmente come esercizio per patchare dinamicamente il bytecode di Python e imparare di più sugli interni di Pythons. Ecco alcuni link interessanti: http://lambda-the-ultimate.org/node/1331 e http://www.rowehl.com/blog/?p=626
C'è un modo per migliorare il codice Perl, per farlo usare uno stack di dimensioni costanti. A tale scopo, utilizza una forma speciale di goto.
sub f{
if( $_[0] < $_[1] ){
# return f( $_[0]+1, $_[1] );
@_ = ( $_[0]+1, $_[1] );
goto &f;
} else {
return $_[0]
}
}
Quando viene chiamato per la prima volta, alloca spazio nello stack. Quindi cambierà i suoi argomenti e riavvierà la subroutine, senza aggiungere altro allo stack. Farà quindi finta di non chiamarsi mai, trasformandolo in un processo iterativo.
Puoi anche utilizzare Sub :: Call :: Recur modulo. Ciò rende il codice più semplice da comprendere e più breve.
use Sub::Call::Recur;
sub f{
recur( $_[0]+1, $_[1] ) if $_[0] < $_[1];
return $_[0];
}
clojure fornisce un modulo speciale per la ricorsione della coda " recur " questo può essere usato solo nei punti di coda dell'ast. Altrimenti si comporta come Java e probabilmente genererà una StackverflowException.
