Ich versuche, eine 10k-Elementliste in Prolog mit bubblesort zu sortieren, und ich bekomme den lokalen Stapelfehler heraus. Mergesort scheint die beste Option zu sein, da ich für die gleiche Eingabe keine Fehler erhalte. Allerdings würde ich gerne einige Laufzeiten für bubblesort mit großen Eingabedaten bekommen, aber ich kann nicht. Irgendwelche Ideen?
Hier ist der Code:
%Vor%Wie Sie sehen können, verwende ich die Tail-Rekursion. Ich habe auch versucht, die Stapel zu vergrößern mit:
%Vor% aber es läuft nur ein bisschen länger. Irgendwann komme ich wieder aus dem lokalen Stapel.
Sollte ich eine andere Sprache wie C und malloc der Liste verwenden oder Rekursion nicht benutzen?
Da es zwei Antworten gibt, und niemand explizit genug darauf hingewiesen hat, warum Sie "außerhalb des lokalen Stacks" Schwierigkeiten haben (Mat sagt im Kommentar zu Ihrer Frage, dass Ihre Prädikate nicht deterministisch sind, aber nicht genau erklären warum).
Zwei der Prädikate, die Sie definiert haben, nämlich bubblesort/3 und bubble/3 , haben sich gegenseitig ausschließende Klauseln. Aber Prolog (zumindest SWI-Prolog) erkennt nicht, dass diese sich gegenseitig ausschließen. Also, Auswahlpunkte werden erstellt, Sie erhalten keine Tail Recursion-Optimierung und wahrscheinlich auch keine Garbage-Collection (Sie müssen die Implementierung Ihrer Wahl messen, wenn Sie wissen möchten, wie viel wo und wann ist).
Sie haben zwei verschiedene Probleme.
Dieses Problem tritt in beiden Prädikaten auf. Im einfachsten möglichen Prädikat:
%Vor%Und dann:
%Vor%Das ist nicht überraschend; beachte:
%Vor%Sie können dies lösen, indem Sie eine Technik namens verzögern verwenden:
%Vor%Dann:
%Vor% In der Definition von bar_1/2 ist das erste Argument der ersten Klausel die leere Liste; Das erste Argument der zweiten Klausel ist eine nicht leere Liste (eine Liste mit mindestens einem Element und einem Tail). Prolog erstellt keine Auswahlpunkte, wenn alle Klauseln offensichtlich exklusiv sind. Was offensichtlich bedeutet, hängt von der Implementierung ab, aber normalerweise, wenn die ersten Argumente für alle Klauseln alle Begriffe mit verschiedenen Funktoren sind, werden keine Auswahlpunkte erstellt.
Versuchen Sie Folgendes (Sie können unterschiedliche Ergebnisse erhalten, aber die Nachricht ist identisch):
%Vor%Siehe diese Frage und die Antwort von Mat, um zu sehen, wie Sie können damit Ihr Programm deterministisch machen.
Mat verwendet in seiner Antwort diesen Ansatz, wenn ich richtig sehe.
Dies ist das Problem mit der zweiten und dritten Klausel von bubble/3 . In dem Lehrbuch "richtiges" Beispiel der Wahl des Minimums von zwei Elementen:
Dann:
%Vor%aber:
%Vor% Sie können das auf zwei Arten lösen: Entweder indem Sie tun, was Mat tut, also mit compare/3 , was deterministisch gelingt; oder, indem man macht, was CapelliC macht, nämlich mit einem Wenn-dann-sonst.
Mat:
%Vor%Und Carlo:
%Vor%Ich weiß, dass es immer mindestens so viele Meinungen geben wird wie Köpfe, aber beides ist gut, abhängig davon, was du tust.
Sie können das eingebaute length/2 verwenden, um eine Liste zu erstellen und Ihr generate_list/3 wie folgt neu schreiben:
Der Helfer random_pos_ints/2 ist ein triviales Prädikat, das in maplist ausgedrückt werden kann:
Hier ist eine Version von bubble/3 , die deterministisch ist, wenn das erste Argument instanziiert wird, so dass die Tail-Call-Optimierung (und insbesondere die Tail-Rekursions-Optimierung) gilt:
Beispiel Verwendung, mit dem Rest des Programms unverändert (Laufzeiten hängen von der Zufallsliste ab, die schlecht ist, wenn Sie diese Ergebnisse reproduzieren wollen - Hinweis: führen Sie den Zufallssaat als Argument ein, um dies zu beheben):
%Vor%Verwenden Sie zum Testen verschiedener Versionen eine Version der Abfrage, die Sie verwenden können, um die gleiche ursprüngliche Liste zuverlässig zu reproduzieren, beispielsweise:
%Vor% Das Schöne ist: Wenn Sie nur zcompare/3 von library(clpfd) anstelle von compare/3 verwenden, erhalten Sie eine Version, die in alle Richtungen verwendet werden kann:
Dies beschreibt die allgemeine Beziehung zwischen ganzen Zahlen.
Haftungsausschluss: Der Hinweis von @mat könnte lohnender sein ...
Ich habe ein bisschen mit Ihrem Code gespielt, in meinem Experiment wurde der lokale Stack-Überlauf mit einer Listenlänge nahe 2500 geworfen. Dann habe ich etwas geschnitten:
%Vor%und ich bekomme
%Vor%Also, es funktioniert, aber sehr langsam, zeigt die quadratische Komplexität ...