¿Cómo memorizo ??una función recursiva en Lisp?

Question

Soy un principiante de Lisp. Estoy intentando memorizar una función recursiva para calcular la cantidad de términos en una secuencia de Collatz (para 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 se da en On Lisp libro.

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

EDITAR: Se corrigió 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 había puesto erróneamente:

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

Ver ese error me dio otra idea, e intenté usar este último defvar y cambiar las llamadas recursivas a

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

Esto parece realizar la memorización (aceleración de unos 60 segundos a 1,5 segundos), pero requiere cambiar la función original. ¿Existe una solución más limpia que no implique cambiar la función original?

Answer 1

Supongo que estás usando Common-Lisp, que tiene espacios de nombres separados para los nombres de funciones y variables. Para memorizar la función nombrada por un símbolo, necesita cambiar su enlace de funció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))))))))

IOW: su función original (no memorizada) es anónima, y ??solo le da un nombre al resultado de la memorización.

Answer 3

Aquí hay una función memoize que vuelve a vincular 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)))))))

Entonces harías 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)

Te lo dejaré a ti para que hagas una función de desmantelar.

Answer 4

Cambiando el " original " la función es necesaria porque, como usted dice, no hay otra manera de que las llamadas recursivas se actualicen para llamar a la versión memorizada.

Afortunadamente, la forma en que funciona lisp es encontrar la función por nombre cada vez que se debe llamar. Esto significa que es suficiente reemplazar el enlace de la función con la versión memorizada de la función, para que las llamadas recursivas busquen y vuelvan a ingresar automáticamente a través de la memoria.

El código de huaiyuan muestra el paso clave:

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

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

Algunas implementaciones de lisp proporcionan un sistema llamado " advice " ;, que proporciona una estructura estandarizada para reemplazar funciones con versiones mejoradas de sí mismas. Además de las actualizaciones funcionales como memoization, esto puede ser extremadamente útil en la depuración insertando impresiones de depuración (o deteniendo completamente y dando un aviso continuo) sin modificar el código original.

Answer 5

Note algunas cosas:

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

Arriba hay una función que tiene una llamada a sí misma.

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

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

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

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

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

Answer 6

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

Consulte la figura 3 (la función 'Hailstone') de su artículo original sobre memoización (" Uso de la memorización automática como herramienta de ingeniería de software en los sistemas AI de la vida real '').

Supongo que, incluso si consigues que funcionen los mecanismos de la memoria, en este caso realmente no la acelerará.

Answer 7

Hace un tiempo escribí una pequeña rutina de memorización para Scheme que usaba una cadena de cierres para realizar un seguimiento del estado de la memoria:

(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 debe usarse así:

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

Estoy seguro de que esto puede ser portado a tu sabor Lisp favorito de ámbito léxico con facilidad.

Answer 8

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. El inconveniente es que no obtienes una versión práctica y sin remordimientos para probar, y borrar la memoria caché es muy difícil de "