Wie sieht Ihre bevorzugte Sprache tiefe Rekursion umgehen? [geschlossen]
https://stackoverflow.com/questions/233013
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
ich das Lernen Python vor kurzem begonnen und ich war ziemlich überrascht, eine 1000 tiefe Rekursion Grenze zu finden (Standard). Wenn Sie es hoch genug eingestellt, etwa 30000, es mit einem Segmentierungsfehler stürzt wie C. Obwohl C ziemlich viel höher zu gehen scheint.
(Die Python Leute sind schnell darauf hin, dass Sie immer rekursive Funktionen iterativ diejenigen umwandeln können und dass sie immer schneller. Das ist 100% wahr. Es ist nicht wirklich das, was meine Frage ist aber,.)
habe ich versucht, das gleiche Experiment in Perl und irgendwo rund 10 Millionen Rekursion es all meinen 4 GB RAM verbraucht und ich ^ C zu stoppen versucht. Offensichtlich Perl nicht die C-Stack verwenden, aber es ist eine lächerliche Menge an Speicher zu verwenden, wenn es recurses -. Nicht sonderlich schockierend man bedenkt, wie viel Arbeit es zu tun hat, Funktionen aufzurufen
habe ich versucht, in Pike und war völlig 100.000.000 Rekursion in etwa 2 Sekunden zu erhalten überrascht. Ich habe keine Ahnung, wie es das tat, aber ich vermute, dass es die Rekursion zu einem iterativen Prozess abgeflacht - es keinen zusätzlichen Speicher zu verbrauchen scheint, während sie es tut. [Anmerkung:. Pike macht triviale Fälle abflachen, aber segfaults auf komplizierteren oder so bin ich gesagt]
Ich habe diese sonst nutzlosen Funktionen:
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
Ich bin sehr gespannt, wie andere Sprachen (zum Beispiel PHP, Ruby, Java, Lua, Ocaml, Haskell) Griff Rekursion und warum sie es auf diese Weise behandeln. Darüber hinaus beachten Sie bitte, ob es einen Unterschied macht, ob die Funktion „tail-rekursive“ (siehe Kommentar) ist.
Lösung
„Die Python Leute sind schnell darauf hin, dass Sie immer rekursive Funktionen iterativ diejenigen umwandeln können und dass sie immer schneller“
Das ist wahr, aber wenn es wie alles, was wirklich so einfach ist, warum Python tut es nicht für mich, so dass mein Code so einfach wie möglich aussehen kann? (Ich sage dies nicht Python Implementierer zuzuschlagen, sondern weil die Antwort erklärt das Problem).
Rekursion Optimierungen haben, da wie in funktionalen Sprachen präsent, dem 14. Jahrhundert oder so etwas. Haskell, CAML, Lisp-Implementierungen alle in der Regel zumindest Schwanz rekursive Funktionen Iterationen konvertieren: Sie tun dies im Grunde durch Spotten, dass es möglich ist, dh dass die Funktion so neu angeordnet werden kann, dass keine lokalen Variablen außer dem Rückgabewert nach dem rekursiven Aufruf verwendet werden . Ein Trick, um es zu ermöglichen, wenn es eine Arbeit ist getan, um den rekursiv Rückgabewert vor Rückkehr, ist ein zusätzlichen „Akkumulator“ Parameter einzuführen. In einfachen Worten bedeutet dies, kann die Arbeit effektiv auf dem Weg „nach unten“ durchgeführt werden, anstatt auf dem Weg „nach oben“: Suche rund um für ‚wie eine Funktion tail-rekursive machen‘ für Details
.Die tatsächlichen Details der einen Schwanz rekursive Funktion in eine Schleife drehen ist im Grunde mit dem Aufrufkonvention jigger so Sie „den Anruf durchführen“ kann einfach durch die Einstellung der Parameter und zurück zum Start der Funktion springen, ohne sich die Mühe zu sparen das ganze Zeug in Rahmen, die Sie wissen, dass Sie nicht immer verwenden. In Assembler ausgedrückt, müssen Sie nicht auf Anrufer-Speicherungs-Register zu erhalten, wenn die Daten-Flow-Analyse sagt Ihnen sind sie darüber hinaus den Ruf ungenutzt, und das gleiche gilt für alles, was auf dem Stapel: Sie haben nicht den Stapelzeiger zu bewegen wenn Sie ein Gespräch nicht dagegen, „Ihr“ Bit des Stapels durch die nächste Rekursion / Iteration bekritzelt.
Im Gegensatz zu, wie Sie den Python Leute umschrieben, eine allgemeine rekursive Funktion zu einer Iteration Umwandlung ist nicht trivial: zum Beispiel, wenn es mehrfach rekursiv ist dann in einem einfachen Ansatz, den Sie noch einen Stapel bräuchten.
memoization ist eine nützliche Technik, obwohl, für willkürlich rekursiven Funktionen, dass Sie, wenn Sie in den möglichen Ansätzen interessiert sind sehen gefallen könnten. Was es bedeutet, ist, dass jedes Mal, wenn eine Funktion ausgewertet wird, können Sie das Ergebnis in einem Cache-Speicher-Stick. Zur Nutzung dieser Rekursion zu optimieren, im Grunde, wenn Ihre rekursive Funktion zählt „down“, und Sie memoize es, dann kann man es bewertet iterativ durch eine Schleife hinzugefügt, was zählt „bis“ jeden Wert der Funktion wiederum die Berechnung, bis Sie das erreichen Ziel. Dies verbraucht sehr wenig Stapelspeicher vorgesehen, dass die Memo-Cache groß genug ist, um alle Werte zu halten, die Sie benötigen,: zum Beispiel, wenn f (n) ist abhängig von f (n-1), f (n-2) und f (n -3) Sie brauchen nur Platz für drei Werte im Cache: wie Sie steigen Sie den Leiter weg kicken können. Wenn f (n) ist abhängig von f (n-1) und f (n / 2), benötigen Sie viel Platz im Cache, aber immer noch weniger als Sie für Stapel in einer nicht optimierten Rekursion verwenden würde.
Andere Tipps
Dies ist eher eine Implementierung Frage als eine Sprache Frage. Es gibt nichts, einig (stoopid) C-Compiler-Implementierer Stoppen aus auch ihren Call-Stack bis 1000 zu begrenzen Es gibt dort viele kleine Prozessoren aus, den Stapelspeicherplatz nicht einmal, dass viele.
haben würde(Die Python Leute sind schnell darauf hin, dass Sie immer rekursive Funktionen iterativ diejenigen umwandeln können und dass sie immer schneller. Das ist 100% wahr. Es ist nicht wirklich das, was meine Frage ist aber,.)
Vielleicht sagen sie das, aber das ist nicht ganz richtig. Rekursion kann immer zu Iteration umgewandelt werden, manchmal aber auch erfordert es manuelle Verwendung eines Stapel zu. Unter diesen Umständen könnte ich die rekursive Version sehe schneller sein (vorausgesetzt, Sie sind intelligent genug, um einfache Optimierungen zu machen, wie das Ziehen unnötige Erklärungen außerhalb der rekursive Routine). Schließlich drückt der Stapel umgebende Prozeduraufrufe ein gut abgegrenzte Problem sind, dass Ihr Compiler wissen sollte, wie sehr gut zu optimieren. Manuelle Stapeloperationen, auf der anderen Seite, sind zu haben, nicht spezialisierte Optimierungs Code in Ihrem Compiler und haften alle Arten von User-Interface-Plausibilitätsprüfungen haben, dass zusätzliche Zyklen dauern wird.
Es kann der Fall sein, dass die iterativen / Stack-Lösung ist immer schneller in Python . Wenn ja, das ist ein Mangel von Python, nicht von Rekursion.
PHP hat eine Standardlimit von 100, bevor er stirbt:
Fatal error: Maximum function nesting level of '100' reached, aborting!
Edit: Sie können das Limit mit ini_set('xdebug.max_nesting_level', 100000); ändern, aber wenn man über etwa 1150 Iterationen gehen PHP stürzt ab:
[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.
C # /. NET Endrekursion in einem bestimmten Satz von Umständen verwendet werden. (Die C # Compiler emittieren kein opcode tailcall, aber die JIT wird implementieren Endrekursion in einigen Fällen .
Shri Borde hat auch einen Beitrag zu diesem Thema . Natürlich wird die CLR ständig ändern, und mit .NET 3.5 und 3.5SP1 es wieder in Bezug auf Endrekursion verändert hat.
Mit dem folgend in der F # interaktiven Konsole, lief es in weniger als eine Sekunde:
let rec f i l =
match i with
| i when i < l -> f (i+1) l
| _ -> l
f 0 100000000;;
Ich habe dann versucht, eine gerade Übersetzung d.
let rec g i l = if i < l then g (i+1) l else l
g 0 100000000;;
Die gleiche Ergebnis, aber unterschiedliche Zusammenstellung.
Dies ist, was f sieht aus wie in, wenn in C # übersetzt:
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 , aber dazu übersetzt:
int g(int i, int l)
{
while(i < l)
{
l = l;
i++;
}
return l;
}
Es ist interessant, dass zwei Funktionen, die im Grunde gleich sind unterschiedlich von dem F # -Compiler generieren. Es zeigt auch, dass die F # -Compiler tail-rekursive Optimierung hat. Somit sollte dies Schleife, bis ich erreicht die Grenze für die 32-Bit-Integer.
Nach diesem Thread um 5.000.000 mit java , 1 GB RAM. (Und das mit der ‚Kunden‘ Version des Hotspots)
Das war mit einem Stapel (-Xss) von 300Mo.
Mit einer -Server Option , dass könnte erhöht werden.
versucht Auch kann man den Compiler ( mit JET zum Beispiel) zu optimieren, zu reduzieren, die Stack-Overhead auf jeder Ebene.
In einigen nicht pathologischen Fällen (wie Ihr), (spätestens) Lua wird mit Endaufruf Rekursion , dh. es wird nur direkt, ohne Daten in Stapeln zu schieben. So ist die Anzahl der Rekursion Schleifen können fast unbegrenzt sein.
Getestet mit:
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))
Auch mit:
function g(i, l)
if i >= l then
return i
end
return g(i+1, l)
end
und sogar Quer Rekursion versucht (f g Aufruf und g Aufruf f ...).
Unter Windows Lua 5.1 verwendet um 1,1MB (konstant), dies zu laufen, beendet in wenigen Sekunden.
Beim Laufen Rubin 1.9.2dev (2010-07-11 Revision 28618) [x86_64-darwin10.0.0] auf einem älteren weißen macbook:
def f
@i += 1
f
end
@i = 0
begin
f
rescue SystemStackError
puts @i
end
Ausgänge 9353 für mich, was bedeutet, Rubin scheißt heraus mit weniger als 10.000 Anrufen auf dem Stapel.
Mit Quer Rekursion, wie zum Beispiel:
def f
@i += 1
g
end
def g
f
end
es scheißt in der Hälfte der Zeit, auch auf 4677 (~ = 9353/2).
Ich kann ein paar Iterationen auspressen durch den rekursiven Aufruf in einem proc Verpackung:
def f
@i += 1
yield
end
@i = 0
@block = lambda { f(&@block) }
begin
f(&@block)
rescue SystemStackError
puts @i
end
, die 4850 aufsteht vor erroring aus.
Visual Dataflex wird Überlauf stapeln.
Ich bin ganz ein Fan von der funktionalen Programmierung, und da die meisten dieser langauges Endrekursion Optimierung implementieren, können Sie so viel Sie mögen :-P Rekursion
Allerdings praktisch, ich habe eine Menge von Java zu nutzen und vielen Python verwenden. Keine Ahnung, welche Grenze Java, aber für Python hatte ich eigentlich geplant (aber noch nicht getan) einen Dekorateur zu implementieren, die Endaufruf die eingerichtete Funktion optimieren würde. Ich habe geplant, diese nicht Rekursion zu optimieren, sondern vor allem als eine Übung in Python-Bytecode dynamisch Patchen und mehr über Pythons Interna zu lernen. Heres einige itneresting Links: http://lambda-the-ultimate.org/node/1331 und http://www.rowehl.com/blog/?p=626
Es gibt einen Weg, auf dem Perl Code zu verbessern, um eine konstante Größe Stapel zu machen verwenden. Sie tun dies durch eine besondere Form des goto verwendet wird.
sub f{
if( $_[0] < $_[1] ){
# return f( $_[0]+1, $_[1] );
@_ = ( $_[0]+1, $_[1] );
goto &f;
} else {
return $_[0]
}
}
Wenn es zuerst genannt Platz auf dem Stapel zuteilen wird. Dann wird er seine Argumente ändern, und das Unterprogramm neu starten, ohne etwas mehr auf den Stapel zu legen. Es wird daher behaupten, dass es nie seine Selbst genannt, es in einen iterativen Prozess zu verändern.
Sie können auch die Sub :: Aufruf :: Wiederholt Modul. Das macht den Code leichter zu verstehen und kürzer.
use Sub::Call::Recur;
sub f{
recur( $_[0]+1, $_[1] ) if $_[0] < $_[1];
return $_[0];
}
clojure stellt eine spezielle Form für Endrekursion „wiederholen“ kann dies nur in tail Orte des ast verwendet werden. Ansonsten verhält es sich wie Java und wird wahrscheinlich eine StackverflowException werfen.
