¿Cómo puedo memorizar una función recursiva en Lisp?

Question

Soy un principiante de Lisp. Estoy intentando memorizar una función recursiva para calcular el número de términos en un Collatz sequence (para el problema 14 en Project Euler). Mi código hasta el momento es:

(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))))))) 

La función memoize es la misma que la dada en el libro On Lisp.

Este código en realidad no da ninguna aceleración en comparación con la versión no memorable. Creo que se debe a las llamadas recursivas que llaman a la versión no memorable de la función, que en cierto modo frustra el propósito. En ese caso, ¿cuál es la forma correcta de hacer la memorización aquí? ¿Hay alguna manera de hacer que todas las llamadas a la función original llamen a la versión modificada, eliminando la necesidad del símbolo especial m-collatz-steps?

EDIT: Se ha corregido el código para tener

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

que es lo que tenía en mi código. antes de la edición que había erróneamente puesto:

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

Al ver que el error me dio otra idea, y yo probamos el uso de esta última en sí defvar y el cambio de las llamadas recursivas a

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

Esto parece llevar a cabo la memorización (aceleración de aproximadamente 60 segundos a 1.5 segundos), pero requiere cambiar la función original. ¿Hay una solución más limpia que no implique cambiar la función original?

Answer 1

Supongo que está utilizando Common-Lisp, que tiene espacios de nombres separados para nombres de variables y funciones. Con el fin de memoize la función nombrada en un símbolo, es necesario cambiar su función de unión, a través del descriptor de acceso `fdefinition ':

(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

algo como esto:

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

OIA: su función original (no memoized) es anónima, y ​​sólo dar un nombre al resultado de memoizing ella.

Answer 3

Aquí es una función memoize que vuelve a enlazar la función de símbolo:

(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))))))) 

a continuación, hacer algo como esto:

(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) 

lo dejaré hasta que haga una función unmemoize.

Answer 4

Es necesario cambiar la función "original", porque, como dices, no hay otra manera de actualizar las llamadas recursivas para llamar a la versión modificada.

Afortunadamente, la forma en que funciona lisp es encontrar la función por el nombre cada vez que necesita ser llamado. Esto significa que es suficiente reemplazar la función vinculante con la versión memorizada de la función, de modo que las llamadas recursivas se busquen automáticamente y vuelvan a entrar a través de la memorización.código

de Huaiyuan muestra el paso clave:

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

Este truco también funciona en Perl. En un lenguaje como C, sin embargo, una versión memorada de una función debe codificarse por separado.

Algunas implementaciones de lisp proporcionan un sistema llamado "consejo", que proporciona una estructura estandarizada para reemplazar funciones con versiones mejoradas de sí mismos. Además de las actualizaciones funcionales como la memorización, esto puede ser extremadamente útil en la depuración mediante la inserción de impresiones de depuración (o detener completamente y dar un mensaje de continuación) sin modificar el código original.

Answer 5

Hace un tiempo escribí una pequeña rutina memoization para el esquema que utiliza una cadena de cierres para realizar un seguimiento del estado memoized:

(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)))))) 

Esto tiene que ser utilizado de esta manera:

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

Estoy seguro de que esto se puede trasladar a su sabor favorito de Lisp con léxico con facilidad.

Answer 6

probablemente haría algo como:

(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))))))))) 

No es agradable y funcional, pero, entonces, no es mucha molestia y funciona. Lo malo es que no se obtiene una versión práctica no conmemorada para probar y borrar el caché es rayano en "muy difícil".

Answer 7

Nota: algunas cosas

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

anterior es una función que tiene una llamada a sí mismo.

En Common Lisp, el compilador de archivos puede suponer que FOO no cambia. NO llamará a un FOO actualizado más tarde. Si cambia el enlace de la función de FOO, entonces la llamada de la función original seguirá yendo a la función anterior.

Por lo tanto, la memorización de una función auto recursiva NO funcionará en el caso general. Especialmente si estás usando un buen compilador.

Puede trabajar alrededor de ella para ir siempre a través del símbolo, por ejemplo: (funcall 'foo 3)

(defvar ...) es un formulario de nivel superior. No lo use dentro de funciones. Si ha declarado una variable, configúrela con SETQ o SETF más tarde.

Para su problema, usaría una tabla hash para almacenar los resultados intermedios.

Answer 8

Esta función es exactamente la que da Peter Norvig como ejemplo de una función que parece ser un buen candidato para la memorización, pero que no lo es.

Vea la figura 3 (la función 'Hailstone') de su documento original sobre memorización ("Uso de la memorización automática como herramienta de ingeniería de software en sistemas AI reales").

Así que supongo que, incluso si funciona la mecánica de la memorización, en este caso no lo acelerará.