Ich versuche, eine tail-rekursive Listensortierfunktion in OCaml zu implementieren, und ich habe den folgenden Code entwickelt:
%Vor%Aber es scheint, dass es nicht tatsächlich tail-rekursiv ist, da ich einen "Stapelüberlauf während der Auswertung (Schleifenrekursion?)" -Fehler erfahre.
Könnten Sie mir bitte helfen, den nicht tailrekursiven Aufruf in diesem Code zu erkennen? Ich habe ziemlich viel gesucht, ohne es zu finden. Könnte es die gebundene Bindung in der Funktion sort sein?
Merge sort ist inhärent nicht tail-rekursiv. Eine Sortierung erfordert zwei rekursive Aufrufe und bei jeder Ausführung einer Funktion höchstens eins dynamischer Aufruf kann in Endposition sein. ( split wird auch von der Nicht-Tail-Position aufgerufen, aber da es einen konstanten Stapelspeicherplatz verwenden sollte, der OK sein sollte).
Stellen Sie sicher, dass Sie eine aktuelle Version von OCaml verwenden. In Versionen 3.08 und älter könnte List.rev den Stack durchbrechen. Dieses Problem wurde in Version 3.10 behoben. Mit Version 3.10.2 kann ich eine Liste von zehn Millionen Elementen mit Ihrem Code sortieren. Es dauert ein paar Minuten, aber ich blase den Stapel nicht. Ich hoffe also, dass dein Problem einfach darin besteht, dass du eine alte Version von OCaml hast.
Wenn nicht, wäre ein guter nächster Schritt, die Umgebungsvariable
zu setzen %Vor%gibt eine Stapelspur, wenn Sie den Stapel blasen.
Ich möchte auch die Länge der Arrays wissen, die Sie sortieren; Obwohl Merge-Sort nicht tail-rekursiv sein kann, sollte seine Nicht-Tail-Eigenschaft Sie logarithmischen Stack-Speicherplatz kosten.
Wenn Sie mehr als 10 Millionen Elemente sortieren müssen, sollten Sie sich vielleicht einen anderen Algorithmus anschauen? Oder, wenn Sie möchten, könnten Sie CPS-Mergesort von Hand konvertieren, was eine tail-rekursive Version auf Kosten der Zuweisung von Contiuations auf dem Heap ergeben wird. Aber ich schätze, dass es nicht notwendig sein wird.
Tags und Links sorting ocaml tail-recursion