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

发布于 2024-07-09 06:23:10 字数 1900 浏览 9 评论 0原文

我是一个 Lisp 初学者。我试图记住一个递归函数，用于计算 Collatz 序列中的项数（对于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 函数与中给出的函数相同关于 Lisp 的书。

与非记忆版本相比，此代码实际上并没有提供任何加速。我相信这是由于递归调用调用了函数的非记忆版本，这有点违背了目的。在这种情况下，这里进行记忆的正确方法是什么？有没有办法让对原始函数的所有调用都调用记忆版本本身，从而消除对特殊 m-collatz-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 秒），但需要改变原来的功能。有没有更干净的解决方案，不涉及更改原始功能？

原文

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

The memoize function is the same as the one given in the On Lisp book.

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?

EDIT: Corrected the code to have

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

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

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

半世蒼涼 2024-07-16 06:23:10

我假设您使用的是 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))

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

回复收藏 0 原文

混浊又暗下来 2024-07-16 06:23:10

像这样的东西：

(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：你的原始（非记忆）函数是匿名的，你只为记忆它的结果命名。

something like this:

(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: your original (non-memoized) function is anonymous, and you only give a name to the result of memoizing it.

回复收藏 0 原文

不奢求什么 2024-07-16 06:23:10

这是一个重新绑定符号函数的 memoize 函数：

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

然后你会做这样的事情：

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

我将由你来创建一个 unmemoize 函数。

Here is a memoize function that rebinds the symbol function:

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

You would then do something like this:

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

I'll leave it up to you to make an unmemoize-function.

回复收藏 0 原文

千纸鹤 2024-07-16 06:23:10

请注意以下几点：

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

上面是一个调用自身的函数。

在 Common Lisp 中，文件编译器可以假设 FOO 不会改变。稍后它不会调用更新的 FOO。如果你改变FOO的函数绑定，那么原来函数的调用仍然会转到旧函数。

因此，记忆自递归函数在一般情况下不起作用。尤其是如果您使用的是好的编译器。

您可以解决这个问题，始终通过符号，例如： (funcall 'foo 3)

(DEFVAR ...) 是顶级形式。不要在函数内部使用它。如果您已声明变量，请稍后使用 SETQ 或 SETF 设置它。

对于您的问题，我只是使用哈希表来存储中间结果。

Note a few things:

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

Above is a function that has a call to itself.

In Common Lisp the file compiler can assume that FOO does not change. It will NOT call an updated FOO later. If you change the function binding of FOO, then the call of the original function will still go to the old function.

So memoizing a self recursive function will NOT work in the general case. Especially not if you are using a good compiler.

You can work around it to go always through the symbol for example: (funcall 'foo 3)

(DEFVAR ...) is a top-level form. Don't use it inside functions. If you have declared a variable, set it with SETQ or SETF later.

For your problem, I'd just use a hash table to store the intermediate results.

回复收藏 0 原文

ヤ经典坏疍 2024-07-16 06:23:10

更改“原始”函数是必要的，因为正如您所说，没有其他方法可以更新递归调用来调用记忆版本。

幸运的是，lisp 的工作方式是在每次需要调用函数时按名称查找该函数。这意味着用函数的记忆版本替换函数绑定就足够了，这样递归调用将通过记忆自动查找并重新输入。

huaiyuan 的代码显示了关键步骤：

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

这个技巧在 Perl 中也适用。然而，在像 C 这样的语言中，函数的记忆版本必须单独编码。

一些 lisp 实现提供了一个称为“advice”的系统，该系统提供了一个标准化的结构，用于用增强版本的函数替换函数。除了记忆等功能升级之外，通过插入调试打印（或完全停止并给出连续的提示）而无需修改原始代码，这在调试中非常有用。

Changing the "original" function is necessary, because, as you say, there's no other way for the recursive call(s) to be updated to call the memoized version.

Fortunately, the way lisp works is to find the function by name each time it needs to be called. This means that it is sufficient to replace the function binding with the memoized version of the function, so that recursive calls will automatically look up and reenter through the memoization.

huaiyuan's code shows the key step:

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

This trick also works in Perl. In a language like C, however, a memoized version of a function must be coded separately.

Some lisp implementations provide a system called "advice", which provides a standardized structure for replacing functions with enhanced versions of themselves. In addition to functional upgrades like memoization, this can be extremely useful in debugging by inserting debug prints (or completely stopping and giving a continuable prompt) without modifying the original code.

回复收藏 0 原文

机场等船 2024-07-16 06:23:10

这个函数正是 Peter Norvig 给出的一个函数示例，它看起来像是一个很好的记忆化候选函数，但事实并非如此。

请参见他关于记忆化的原始论文（“在现实世界人工智能系统中使用自动记忆化作为软件工程工具”）的图 3（函数“Hailstone”）。

所以我猜，即使你让记忆机制发挥作用，在这种情况下也不会真正加快速度。

回复收藏 0 原文

挽你眉间 2024-07-16 06:23:10

不久前，我为Scheme写了一个小记忆例程，它使用闭包链来跟踪记忆状态：

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

这需要像这样使用：

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

我确信这可以移植到你最喜欢的词法范围的Lisp风格舒适。

A while ago I wrote a little memoization routine for Scheme that used a chain of closures to keep track of the memoized state:

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

This needs to be used like so:

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

I'm sure that this can be ported to your favorite lexically scoped Lisp flavor with ease.

回复收藏 0 原文

老子叫无熙 2024-07-16 06:23:10

我可能会这样做：

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

它既不美观也不实用，但是，它并不麻烦，而且确实有效。缺点是您没有方便的未记忆版本来测试，并且清除缓存近乎“非常困难”。

I'd probably do something like:

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

It's not Nice and Functional, but, then, it's not much hassle and it does work. Downside is that you don't get a handy unmemoized version to test with and clearing the cache is bordering on "very difficult".

回复收藏 0 原文

~没有更多了~