我怎么memoize递归功能在舌头?

StackOverflow https://stackoverflow.com/questions/256507

  •  05-07-2019
  •  | 
  •  

题

我是一个口齿不清的初学者。我想memoize递归功能的计算数量的条款中的一个 Collatz序列 (对问题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的功能相同，一定在 在口齿不清 书。

这个代码实际上并没有得到任何加速相比，非memoized版本。我相信这是由于递电话叫的非memoized版本的功能，这种失败的目的。在这种情况下，什么是正确的方式做到的性记忆化在这里？是否有任何方法拥有的所有电话的原有功能叫memoized版本身，除了需要特别m-collatz步骤的象征？

编辑：修正的有代码 

(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秒)，但需要改变原有的功能。是有一个更清洁的解决方案，这不涉及改变原有功能吗？

有帮助吗？

解决方案

我假设你正在使用的共口齿不清，它具有单独的名字空间的用于可变和功能名称。为了memoize的功能，名为，通过一个符号，你需要改变它的功能结合，通过访问`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))

其他提示

事情是这样的：

(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:你原来的(非memoized)的功能是匿名的，并且，你只给一个名字的结果的memoizing。

这里是一个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功能。

更改"原始的"功能是必要的，因为，正如你所说，没有其他的方式为递归的呼吁(s)进行更新，以叫memoized版本。

幸运的是，路口齿不清的工作是找到功能 的名称 每次需要呼吁。这意味着就足以替换的功能结合的memoized版本的功能，因此，递电话会自动查找并重新输入通过性记忆化.

怀远的码表示的关键步骤：

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

这一招也在Perl。在语言等C，但是，一个memoized版本的功能必须分开编码。

一些口齿不清的实现提供一个系统，称为"建议"，它提供了一个标准化结构，用于更换功能的增强版本的本身。此外，功能升级样性记忆化，这可能是极其有用的，在调试通过插入"调试"打印(或完全停止，并给予一个连续的提示)，而不修改原始代码。

注意几件事情：

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

上述是一种功能，具有一个电话本身。

在公共口齿不清的文件编译器可以假设，FOO不会改变。它不会叫一个更新的FOO后。如果你改变的功能结合的FOO，那么呼叫的原有功能还是会去的老的功能。

所以memoizing自递归功能将不会的工作在一般情况。尤其不如果您使用的是一个很好的编译器。

你可以工作围绕着它去总是通过符号，例如：(funcall'foo3)

(DEFVAR...)是一个顶级的形式。不要使用它内部的功能。如果你已经宣布一个可变的，它设置与SETQ或SETF后。

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

这种功能上是完全一彼得Norvig给作为例子的一个函数，似乎是一个很好的候选人性记忆化，但它不是。

请参见图3(功能'的冰雹')他原来的纸上的性记忆化("使用自动性记忆化作为一个软件工程的工具，在现实世界的艾系统")。

因此我猜测，即使你得到的机制性记忆化的工作，它不会真正加快它在这个情况。

一段时间前，我写了一个小小的性记忆化程序的计划，用一个链的封锁，以跟踪memoized状态：

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

我敢肯定，这可以移植到你最喜欢的词法范围内的口齿不清的味道。

我可能会做这样的事情:

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

这是不好的功能，但是，那么，它就不太麻烦和它的工作。缺点是，你没有得到一个方便的unmemoized版本，以测试和清除缓接壤上的"非常困难"。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top