lisp - 我如何在 Lisp 中内存一个递归函数？

Question

我是 Lisp 初学者。我正在尝试内存一个递归函数来计算 Collatz sequence 中的项数(对于 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 中给出的函数相同书。

与非内存版本相比，这段代码实际上并没有提供任何加速。我相信这是由于递归调用调用了函数的非记忆化版本，这有点违背了目的。在那种情况下，在这里进行内存的正确方法是什么？有没有办法让所有对原始函数的调用都调用内存版本本身，从而消除对特殊 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))))

这似乎确实执行了内存(从大约 60 秒加速到 1.5 秒)，但需要更改原始功能。是否有不涉及更改原始功能的更清洁的解决方案？

Answer 1

我假设您使用的是 Common-Lisp，它为变量名和函数名提供了单独的命名空间。为了记住由符号命名的函数，您需要通过访问器“fdefinition”更改其函数绑定(bind):

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