Wie stelle ich eine rekursive Funktion in Lisp fest?

Question

Ich bin ein Lisp Anfänger. Ich versuche, eine rekursive Funktion zur Berechnung der Anzahl der Begriffe in einem Collatz sequence (für Problem 14 in Project Euler) Memo. Mein Code als die noch ist:

(defun collatz-steps (n) 
    (if (= 1 n) 0 
     (if (evenp n) 
      (1+ (collatz-steps (/ n 2))) 
      (1+ (collatz-steps (1+ (* 3 n))))))) 

(defun p14() 
    (defvar m-collatz-steps (memoize #'collatz-steps)) 
    (let 
     ((maxsteps (funcall m-collatz-steps 2)) 
     (n 2) 
     (steps)) 
    (loop for i from 1 to 1000000 
      do 
      (setq steps (funcall m-collatz-steps i)) 
      (cond 
      ((> steps maxsteps) 
      (setq maxsteps steps) 
      (setq n i)) 
      (t()))) 
    n)) 


(defun memoize (fn) 
    (let ((cache (make-hash-table :test #'equal))) 
    #'(lambda (&rest args) 
     (multiple-value-bind 
       (result exists) 
      (gethash args cache) 
      (if exists 
       result 
       (setf (gethash args cache) 
        (apply fn args))))))) 

Die memoize Funktion ist das gleiche wie die in dem On Lisp Buch gegeben ist.

Dieser Code gibt keine Beschleunigung im Vergleich zu der nicht memoisierten Version. Ich glaube, es liegt an den rekursiven Aufrufen, die die nicht memoisierte Version der Funktion aufrufen, die den Zweck vereitelt. Was ist in diesem Fall die richtige Art, die Memo-Erstellung hier durchzuführen? Gibt es eine Möglichkeit, alle Aufrufe der ursprünglichen Funktion die Memo-Version selbst aufrufen zu lassen, ohne das spezielle m-collatz-steps-Symbol zu benötigen?

EDIT: Korrigierte der Code

(defvar m-collatz-steps (memoize #'collatz-steps)) 

zu haben, das ist, was ich in meinem Code hatte. Vor der Bearbeitung hatte ich fälschlicherweise gesagt:

(defvar collatz-steps (memoize #'collatz-steps)) 

zu sehen, dass Fehler gab mir eine andere Idee, und ich versuchte, diese letzte defvar mit sich selbst und das Ändern der rekursiven Aufrufe zu

 (1+ (funcall collatz-steps (/ n 2))) 
     (1+ (funcall collatz-steps (1+ (* 3 n)))) 

Diese zu führen scheint zu die Memoisierung (Beschleunigung von etwa 60 Sekunden auf 1,5 Sekunden), erfordert jedoch das Ändern der ursprünglichen Funktion. Gibt es eine sauberere Lösung, bei der die ursprüngliche Funktion nicht verändert wird?

Answer 1

Ich nehme an, dass Sie Common-Lisp verwenden, das über separate Namespaces für Variablen- und Funktionsnamen verfügt. Um die Funktion durch ein Symbol genannt zu memoize, müssen Sie die Funktion zu binden, durch die Accessor `fdefinition 'ändern:

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps)) 

(defun p14() 
    (let ((mx 0) (my 0)) 
    (loop for x from 1 to 1000000 
      for y = (collatz-steps x) 
      when (< my y) do (setf my y mx x)) 
    mx)) 

Answer 2

etwas wie folgt aus:

(setf collatz-steps (memoize lambda (n) 
    (if (= 1 n) 0 
    (if (evenp n) 
     (1+ (collatz-steps (/ n 2))) 
     (1+ (collatz-steps (1+ (* 3 n)))))))) 

IOW: Ihre ursprüngliche (nicht-memoized) Funktion ist anonym, und Sie haben nur einen Namen auf das Ergebnis der memoizing geben.

Answer 3

Hier ist eine memoize Funktion, die die Symbolfunktion erneut bindet:

(defun memoize-function (function-name) 
    (setf (symbol-function function-name) 
    (let ((cache (make-hash-table :test #'equal))) 
     #'(lambda (&rest args) 
      (multiple-value-bind 
       (result exists) 
       (gethash args cache) 
       (if exists 
        result 
        (setf (gethash args cache) 
         (apply fn args))))))) 

Sie würden dann so etwas tun:

(defun collatz-steps (n) 
    (if (= 1 n) 0 
     (if (evenp n) 
      (1+ (collatz-steps (/ n 2))) 
      (1+ (collatz-steps (1+ (* 3 n))))))) 

(memoize-function 'collatz-steps) 

ich werde es Ihnen überlassen, um eine unmemoize-Funktion zu machen.

Answer 4

Das Ändern der "Original" -Funktion ist notwendig, da, wie Sie sagen, es keine andere Möglichkeit gibt, die rekursiven Aufrufe zu aktualisieren, um die Memo-Version aufzurufen.

Glücklicherweise funktioniert die Art, wie Lisp funktioniert, die Funktion mit Namen jedes Mal, wenn es aufgerufen werden muss. Dies bedeutet, dass es ausreicht, die Funktionsbindung durch die memoisierte Version der Funktion zu ersetzen, so dass rekursive Aufrufe automatisch durch die Memoisierung suchen und erneut eintreten.

Huaiyuan Code zeigt den Schlüsselschritt:

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps)) 

Dieser Trick funktioniert auch in Perl. In einer Sprache wie C muss jedoch eine gespeicherte Version einer Funktion separat codiert werden.

Einige Lisp-Implementierungen bieten ein System namens "advice", das eine standardisierte Struktur zum Ersetzen von Funktionen durch erweiterte Versionen von sich selbst bietet. Zusätzlich zu funktionalen Upgrades wie Memoization kann dies beim Debuggen äußerst nützlich sein, indem Debug-Ausdrucke eingefügt werden (oder vollständig gestoppt werden und eine fortlaufende Eingabeaufforderung gegeben wird), ohne den ursprünglichen Code zu ändern.

Answer 5

Vor einiger Zeit schrieb ich ein wenig memoization Routine für Schema, die eine Kette von Verschlüssen verwendet Spur des memoized Zustand zu halten:

(define (memoize op) 
    (letrec ((get (lambda (key) (list #f))) 
      (set (lambda (key item) 
        (let ((old-get get)) 
        (set! get (lambda (new-key) 
           (if (equal? key new-key) (cons #t item) 
            (old-get new-key)))))))) 
    (lambda args 
     (let ((ans (get args))) 
     (if (car ans) (cdr ans) 
      (let ((new-ans (apply op args))) 
       (set args new-ans) 
       new-ans)))))) 

Dies muss wie so verwendet werden:

(define fib (memoize (lambda (x) 
         (if (< x 2) x 
          (+ (fib (- x 1)) (fib (- x 2))))))) 

Ich bin mir sicher, dass dies mit Leichtigkeit auf Ihren bevorzugten lexikalischen Lisp-Geschmack portiert werden kann.

Answer 6

Ich würde wahrscheinlich so etwas wie:

(let ((memo (make-hash-table :test #'equal))) 
    (defun collatz-steps (n) 
    (or (gethash n memo) 
    (setf (gethash n memo) 
      (cond ((= n 1) 0) 
      ((oddp n) (1+ (collatz-steps (+ 1 n n n)))) 
      (t (1+ (collatz-steps (/ n 2))))))))) 

Es ist nicht schön und funktional, aber dann ist es nicht viel Aufwand und es funktioniert. Nachteil ist, dass Sie keine handliche unmemoisierte Version zum Testen bekommen und der Cache auf "sehr schwer" grenzt.

Answer 7

Hinweis ein paar Dinge:

(defun foo (bar) 
    ... (foo 3) ...) 

oberhalb einer Funktion, die eine Verbindung zu sich selbst hat.

In Common Lisp kann der Dateicompiler davon ausgehen, dass sich FOO nicht ändert. Es wird später kein aktualisiertes FOO aufrufen. Wenn Sie die Funktionsbindung von FOO ändern, wird der Aufruf der ursprünglichen Funktion immer noch an die alte Funktion übergeben.

Das Memoisieren einer selbstrekursiven Funktion funktioniert NICHT im allgemeinen Fall. Vor allem nicht, wenn Sie einen guten Compiler verwenden.

Sie können arbeiten um ihn herum immer durch das Symbol zum Beispiel zu gehen: (FUNCALL ‚foo 3)

(DEFVAR ...) ist eine Top-Level-Form. Benutze es nicht innerhalb von Funktionen. Wenn Sie eine Variable deklariert haben, setzen Sie sie später mit SETQ oder SETF.

Für Ihr Problem würde ich nur eine Hash-Tabelle verwenden, um die Zwischenergebnisse zu speichern.

Answer 8

Diese Funktion ist genau die, die Peter Norvig als ein Beispiel für eine Funktion gibt, die wie ein guter Kandidat für Memoisierung scheint, aber das ist nicht.

Siehe Abbildung 3 (die Funktion "Hailstone") seiner Originalarbeit zum Memoisieren ("Verwendung automatischer Memoisierung als Software-Entwicklungswerkzeug in realen AI-Systemen").

Also ich rate, auch wenn Sie die Mechanik von Memoization arbeiten, wird es in diesem Fall nicht wirklich beschleunigen.Ja