如何在Lisp中记住递归函数? [英] How do I memoize a recursive function in Lisp?

问题描述

我是Lisp初学者.我正在尝试记住一个递归函数，用于计算 Collat​​z序列(对于 Project Euler 中的问题14.).到目前为止，我的代码是:

I'm a Lisp beginner. I'm trying to memoize a recursive function for calculating the number of terms in a Collatz sequence (for problem 14 in Project Euler). My code as of yet is:

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

备忘录功能与在Lisp上提供的功能相同书.

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

This code doesn't actually give any speedup compared to the non-memoized version. I believe it's due to the recursive calls calling the non-memoized version of the function, which sort of defeats the purpose. In that case, what is the correct way to do the memoization here? Is there any way to have all calls to the original function call the memoized version itself, removing the need for the special m-collatz-steps symbol?

更正了具有

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

这就是我在代码中所拥有的. 在编辑之前，我错误地输入了:

which is what I had in my code. Before the edit I had erroneously put:

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

看到该错误给了我另一个主意，我尝试使用最后一个defvar本身并将递归调用更改为

Seeing that error gave me another idea, and I tried using this last defvar itself and changing the recursive calls to

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

这似乎可以执行记忆(从大约60秒加速到1.5秒)，但是需要更改原始功能.是否有一个不涉及更改原始功能的更清洁的解决方案?

This does seem to perform the memoization (speedup from about 60 seconds to 1.5 seconds), but requires changing the original function. Is there a cleaner solution which doesn't involve changing the original function?

推荐答案

我假设您使用的是Common-Lisp，它具有用于变量名和函数名的独立命名空间.为了记住以符号命名的函数，您需要通过访问器"fdefinition"更改其函数绑定:

I assume you're using Common-Lisp, which has separate namespaces for variable and function names. In order to memoize the function named by a symbol, you need to change its function binding, through the accessor `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))

这篇关于如何在Lisp中记住递归函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！