Odd Frage in Zusammenhang mit Projekt euler 72 (Lispeln)

stimmen
5

Ich erkenne, dass es offensichtlich, dass die Muster in der Ausgabe dieses, ich möchte nur wissen, warum lispbox der REPL bricht, wenn ich versuche etwas> 52. Auch zu laufen, irgendwelche Vorschläge auf den Code verbessern, sind mehr als willkommen. ^ - ^

(defun count-reduced-fractions (n d sum)
  (setf g (gcd n d))
  (if (equal 1 d)
      (return-from count-reduced-fractions sum)
      (if (zerop n)
          (if (= 1 g)
              (count-reduced-fractions (1- d) (1- d) (1+ sum))
              (count-reduced-fractions (1- d) (1- d) sum))
          (if (= 1 g)
              (count-reduced-fractions (1- n) d (1+ sum))
              (count-reduced-fractions (1- n) d sum)))))

Alles, was ich bekommen, wenn ich rufe

(count-reduced-fractions 53 53 0)

ist

; Auswertung abgebrochen

Es braucht nicht viel Sinn für mich, wenn man bedenkt, es wird laufen (und das genaue Ergebnis zurück) auf alle Zahlen darunter, und dass ich tun konnte, in meinem Kopf 53 (wenn ich wollte), auf Papier, oder eine Zeile zu einer Zeit, in Lisp. Ich habe sogar auf vielen verschiedenen Nummern getestet größer als 53, um sicherzustellen, es war nicht spezifisch 53. Nichts funktioniert.

Veröffentlicht am 10/12/2008 um 01:03
quelle vom benutzer
In anderen Sprachen...                            


4 antworten

stimmen
6

Dieses Verhalten deutet auf eine fehlende Endrekursion Optimierung, so dass Ihre Rekursion den Stapel bläst. Ein möglicher Grund ist, dass Sie mit dem Debuggen Optimierung deklamiert haben.

By the way, müssen Sie nicht auf einen expliziten Aufruf zu machen return-from. Da sumein Selbst Auswertung Symbol ist, können Sie diese Zeile ändern

(return-from count-reduced-fractions sum)

zu

sum

edit: Erläuterung der vorgeschlagenen Änderung: „sum“ wertet seinen eigenen Wert, der den Rückgabewert der „if“ Anweisung wird, die (da dies die letzte Anweisung in der defun ist) , um den Rückgabewert der Funktion wird.

edit: Erklärung der deklamierte Optimierung: Sie könnten die folgende in der obersten Ebene hinzufügen:

(declaim (optimize (speed 3)
                   (debug 0)))

oder verwenden Sie das gleiche, aber mit declarestatt declaimals erste Anweisung in Ihrer Funktion. Sie könnten auch versuchen (Platz 3) und (Sicherheit 0) , wenn es nicht funktioniert.

Endaufruf Optimierung bedeutet, dass ein Funktionsaufruf, deren Rückgabewert zurückgegeben wird, direkt in einen Rahmen Ersatz auf dem Stapel übersetzt (statt Aufstapeln), effektiv „Abflachen“ eine rekursive Funktionsaufruf zu einer Schleife, und die Beseitigung der rekursiven Funktionsaufrufe. Dies macht ein bisschen schwieriger debuggen, weil es keine Funktionsaufrufe sind, wo man sie bzw. erwarten. Sie wissen nicht, wie „tief“ in eine Rekursion ein Fehler auftritt (so als ob Sie eine Schleife beginnen geschrieben hatte). Ihre Umgebung möglicherweise einige Standard Deklamationen, die Sie haben außer Kraft zu setzen TCO zu ermöglichen.

edit: Genau diese Frage erneuten Besuch, was ist g? Ich denke , dass Sie tatsächlich zu

(let ((g (gcd n d)))
  ;; ...
  )
Beantwortet am 10/12/2008 um 01:21
quelle vom benutzer

stimmen
3

Meine Vermutung ist, dass es eine eingebaute Stack-Tiefenbegrenzung mit lispbox. Da Common Lisp bietet keine Garantie für tail-rekursive Funktionen konstanten Stapelspeicher verwenden, ist es möglich, dass jeder Aufruf von Count-reduzierten Fraktionen auf dem Stapel eine weitere Ebene hinzufügt.

By the way, läuft SBCL diesen Algorithmus ohne Problem.

* (count-reduced-fractions 53 53 0)
881

* (count-reduced-fractions 100 100 0)
3043
Beantwortet am 10/12/2008 um 01:11
quelle vom benutzer

stimmen
1

Als eine Frage des Stils, könnten Sie d und summieren optional machen.

(defun test (n &optional (d n) (sum 0)) .. )
Beantwortet am 10/12/2008 um 01:15
quelle vom benutzer

stimmen
0

Wahrscheinlich ein Stack-Überlauf (heh).

Beantwortet am 10/12/2008 um 01:10
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more