Was sind die Vor- und Nachteile der manuellen Liste Iteration vs Rekursion durch Fehler

8

Ich stoße die ganze Zeit darauf und ich bin mir nie sicher, auf welche Weise ich es angreifen kann. Im Folgenden sind zwei Methoden zur Verarbeitung einiger Saison Fakten.

Was ich versuche herauszufinden, ist, ob Methode 1 oder 2 zu verwenden ist, und was die Vor- und Nachteile jedes Einzelnen sind, besonders große Mengen an Fakten.

methodone scheint verschwenderisch zu sein, da die Fakten verfügbar sind, warum sollte man sich eine Liste von ihnen zusammenstellen (besonders eine große Liste). Dies muss auch Auswirkungen auf den Speicher haben, wenn die Liste groß genug ist? Und es nutzt nicht Prologs natürliche Backtracking-Funktion.

methodtwo nutzt den Vorteil der Rückverfolgung, um die Rekursion für mich durchzuführen, und ich würde annehmen, dass dies viel effizienter ist, aber ist es eine gute Programmierpraxis, dies generell zu tun? Es ist wohl hässlicher zu folgen, und könnte es irgendwelche anderen Nebenwirkungen geben?

Ein Problem, das ich sehen kann, ist, dass jedes Mal, wenn fail aufgerufen wird, die Fähigkeit verloren geht, irgendetwas zurück an das aufrufende Prädikat zu übergeben, z. wenn es methodtwo(SeasonResults) war, da wir fortwährend das Prädikat absichtlich nicht erfüllen. Also müsste methodtwo Tatsachen zum Speichern des Zustands bestätigen.

Vermutlich (?) Methode 2 wäre schneller, da es keine (große) Liste Verarbeitung zu tun hat?

Ich könnte mir vorstellen, dass, wenn ich eine Liste hätte, methodone der richtige Weg wäre ... oder ist das immer wahr? Könnte es unter irgendwelchen Bedingungen sinnvoll sein, die Liste mit methodone auf Fakten zu setzen und sie dann mit Methode zwei zu verarbeiten? Voller Wahnsinn?

Aber andererseits habe ich gelesen, dass die Behauptung von Fakten ein sehr "teures" Geschäft ist, also könnte die Listenbearbeitung auch für große Listen der richtige Weg sein?

Irgendwelche Gedanken? Oder ist es manchmal besser, einen zu benutzen und nicht den anderen, abhängig von (welcher) Situation? z.B. für die Speicheroptimierung, verwenden Sie Methode 2, einschließlich der Geltendmachung von Fakten und für die Geschwindigkeit verwenden Methode 1?

%Vor%     
magus 16.03.2012, 21:17
quelle

3 Antworten

7
  

Methode man scheint verschwenderisch, da die Fakten zur Verfügung stehen, warum sich Mühe machen, eine Liste von ihnen zu bauen (vor allem eine große Liste). Dies muss auch Auswirkungen auf den Speicher haben, wenn die Liste groß genug ist?

Ja, Methode 1 benötigt Θ ( n ) Speicher. Es ist der primäre Vorteil, dass es deklarativ ist, d. H. Es hat eine einfache logische Bedeutung.

Methode 2, die "failure-driven loop", wie Prolog-Programmierer sie nennen, benötigt konstanten Speicher, ist prozedural und wird vielleicht bevorzugt, wenn Sie prozedurale (extra-logische) Dinge machen; im I / O-Code ist es in Ordnung, es zu verwenden.

Beachten Sie, dass SWI-Prolog eine dritte Möglichkeit zum Schreiben dieser Schleife hat:

%Vor%

Dies funktioniert nur, wenn showseason für jede Bindung von season(S) erfolgreich ist.

    
Fred Foo 16.03.2012, 21:23
quelle
8

Sehen wir uns Ihr Beispiel an. Es ist sehr einfach, also werden wir uns vorstellen, dass es komplexer ist. Es scheint jedoch selbstverständlich zu sein, dass Nebenwirkungen essentiell sind. Lass mich das ein wenig in Frage stellen:

In Ihrem Beispiel haben Sie eine sehr interessante Entdeckung gemacht: Die Namen aller Jahreszeiten sind gleich lang. Was für eine welterschütternde Erkenntnis! Aber warte, ist es wirklich wahr? Der einfachste Weg, dies zu überprüfen, ist:

%Vor%

Keine Notwendigkeit für findall/3 , keine Notwendigkeit für write/1 .

Bei einer größeren Anzahl von Antworten ist eine visuelle Inspektion nicht praktikabel. Stellen Sie sich 400 Jahreszeiten vor. Aber wir können das überprüfen mit:

%Vor%

Wir wissen also jetzt sicher, dass es keine Saison von unterschiedlicher Länge gibt.

Das ist meine allererste Antwort auf Ihre Frage:

  

Solange Sie können, verwenden Sie die Toplevel-Shell und nicht Ihre eigenen Nebenwirkungen. Strecken Sie die Dinge etwas weiter, um Nebenwirkungen zu vermeiden. Dies ist der beste Weg, fehlerbehaftete Schleifen von Anfang an zu vermeiden.

Es gibt noch mehr Gründe, warum das Festhalten an der Toplevel-Shell eine gute Idee ist:

  • Wenn Ihre Programme leicht auf der obersten Ebene abgefragt werden können, ist es trivial, Testfälle für sie hinzuzufügen.

  • Die Toplevel-Shell wird von vielen anderen Benutzern verwendet und ist daher sehr gut getestet. Dein eigenes Schreiben ist oft fehlerhaft und ungetestet. Denken Sie an Einschränkungen. Denken Sie daran, Schwimmer zu schreiben. Werden Sie write/1 auch für Floats verwenden? Was ist der richtige Weg, Floats so zu schreiben, dass sie genau zurück gelesen werden können? There ist eine Möglichkeit, dies in . Hier ist die Antwort:

  

In ISO writeq/1,2 , write_canonical/1,2 , write_term/2,3 mit Option quoted(true) garantieren, dass Floats genau zurückgelesen werden können. Das heißt, sie sind die gleichen wr.t. (==)/2

  • Die Toplevel-Shell zeigt Ihnen gültigen Prolog-Text. In der Tat ist die Antwort selbst eine Abfrage! Es kann wieder in den Toplevel eingefügt werden - nur um die gleiche Antwort zu erhalten. Auf diese Weise lernst du die exotischeren, aber unvermeidlichen Details von Prolog kennen, wie Zitate, Flucht und Einklammerung. Es ist praktisch unmöglich, die Syntax anders zu lernen, da Prolog-Parser oft extrem permissiv sind.

  • Ihr Programm wird wahrscheinlich besser für deklaratives Denken zugänglich sein.

Wahrscheinlich sind Ihre beiden Prozeduren methodone und methodtwo falsch: Sie haben nach dem Schreiben von Done eine neue Zeile vergessen. So enthält methodone, methodone eine verzerrte Zeile. Wie kann man das leicht testen?

Aber lassen Sie uns ein wenig weiter in Ihr Programm schauen. Was bei fehlergesteuerten Schleifen so typisch ist, ist, dass sie unschuldig beginnen als etwas, das "nur" Nebenwirkungen hat, aber früher oder später auch mehr semantische Teile anzieht. In Ihrem Fall ist atom_length/2 in der fehlergesteuerten Schleife verborgen und für Testzwecke oder Schlussfolgerungen völlig unzugänglich.

Effizienzbetrachtungen

Prolog-Systeme implementieren häufig Fehler, indem sie einen Stapel freigeben. Ausfallsgesteuerte Schleifen benötigen daher keinen Garbage Collector. Deshalb glauben die Leute, dass fehlergesteuerte Schleifen effizient sind. Dies ist jedoch nicht unbedingt der Fall. Für ein Ziel wie findall(A, season(A), As) wird jede Antwort für A in etwas Leerzeichen kopiert. Dies ist eine triviale Operation für etwas wie Atome, aber stellen Sie sich einen größeren Begriff vor. Sprich:

%Vor%

In vielen Systemen wird findall/3 oder assertz/1 für diesen großen Begriff das System einfrieren.

Auch Systeme wie SWI, YAP, SICStus haben ziemlich ausgefeilte Müllsammler. Und die Verwendung von weniger fehlergesteuerten Loops wird dazu beitragen, diese Systeme noch weiter zu verbessern, da dies eine Nachfrage nach anspruchsvolleren Techniken erzeugt.

>     
false 20.03.2012 16:36
quelle
3

Wenn Sie findall bereits verwenden, warum nicht auch maplist :

%Vor%

Beide sind nicht im reinen logischen Prolog-Kern. Und ja, Sie vergeben eine ganze Liste für alle Lösungen.

Ihre zweite Methode heißt "failure-driven loop", und es ist nichts falsch daran, außer dass es keine Möglichkeit gibt, nach einem Backtracking durch Fehler zu den vorherigen Lösungen zu gelangen. Deshalb ist findall extra logisch. Intern könnte es als ausfallgesteuerte Schleife implementiert werden, die ihre Zwischenergebnisse über Assertion speichert. Die zweite ist also konzeptionell sauberer, zusätzlich wird kein zusätzlicher Speicher zugewiesen. Es wird normalerweise in Prädikaten der obersten Ebene "Treiber" (d. H. UI) verwendet.

    
Will Ness 16.03.2012 22:00
quelle