如何在Lisp中记忆递归函数？

Question

我是Lisp的初学者.我正在尝试记忆递归函数来计算Collat​​z序列中的项数(对于Project Euler中的问题14 ).我的代码是:

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

memoize函数与On Lisp书中给出的函数相同.

与非memoized版本相比,此代码实际上没有提供任何加速.我相信这是由于调用函数的非memoized版本的递归调用,这有点违背了目的.在这种情况下,这里进行记忆的正确方法是什么？有没有办法让所有调用原始函数调用memoized版本本身,不需要特殊的m-collat​​z-steps符号？

编辑:更正了代码

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

这是我在我的代码中所拥有的.在编辑之前我错误地说:

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

看到这个错误给了我另一个想法,我尝试使用这个最后的defvar本身并更改递归调用

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

这似乎执行了memoization(加速从大约60秒到1.5秒),但需要更改原始功能.有没有更清洁的解决方案,不涉及改变原有的功能？

Answer 1

我假设您使用的是Common-Lisp,它具有用于变量和函数名称的单独命名空间.为了记住符号命名的函数,需要通过访问器"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))