18

我是一个 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书中给出的函数相同。

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

4

8 回答 8

11

我假设您使用的是 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))
于 2008-11-02T19:11:29.137 回答
3

这是一个重新绑定符号函数的 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 功能。

于 2008-11-03T19:46:01.140 回答
2

像这样的东西：

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

于 2008-11-02T05:18:10.627 回答
2

注意几点：

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

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

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

所以记忆一个自递归函数在一般情况下是行不通的。如果您使用的是好的编译器，则尤其如此。

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

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

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

于 2010-03-06T18:36:50.167 回答
1

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

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

怀远的代码展示了关键步骤：

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

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

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

于 2008-11-21T04:58:06.113 回答
1

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

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

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

于 2010-08-16T15:19:37.923 回答
0

不久前，我为 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 风格中。

于 2008-11-21T05:13:53.993 回答
0

我可能会做类似的事情：

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

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

于 2010-03-06T17:33:29.570 回答