闭包的记忆化示例：来自《Lisp之国》

Question

闭包的记忆化示例：来自《Lisp之国》

9

在《Lisp之国》的第329页，Conrad Barski通过以下示例代码解释了记忆化技术。

(let ((old-neighbors (symbol-function 'neighbors))
      (previous (make-hash-table)))
  (defun neighbors (pos)
    (or (gethash pos previous)
        (setf (gethash pos previous) (funcall old-neighbors pos)))))

这个想法很好：当我调用neighbors函数时，将结果保存到哈希表中，这样下次再调用neighbors函数并使用相同的pos值时，可以直接查找结果，而无需重新计算。

所以我在想，通过编辑和重新编译源代码（书上第314页有），将函数neighbors重命名为old-neighbors是否更容易。然后memoization示例就可以简化为：

(let ((previous (make-hash-table)))
  (defun neighbors (pos)
    (or (gethash pos previous)
        (setf (gethash pos previous) (funcall old-neighbors pos)))))

或者，事先将previous转换为全局变量*previous-neighbors*，甚至可以转换成。

(defun neighbors (pos)
  (or (gethash pos *previous-neighbors*)
      (setf (gethash pos *previous-neighbors*) (funcall old-neighbors pos))))

因此使闭包不再必要。

所以我的问题是：这样做的原因是什么？

我能想到的原因：

1.这是教学性的，展示了使用闭包（之前已经解释过）并提供了symbol-function的示例。

2.即使在您无法或不允许更改neighbors的源代码的情况下，也可以使用这种技术。

3.我可能漏掉了什么重要的东西。

- Dominik Mokriš

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rainer Joswig · Accepted Answer

你提出了一些不错的观察。

通常像这样使用闭包的风格更容易在Scheme代码中找到——在那里，Scheme开发人员经常使用函数返回函数。

从你发现的情况来看，一般而言，让memoize函数foo调用一个函数old-foo是没有什么意义的。使用全局变量会降低封装性（->信息隐藏），但会增加程序调试的能力，因为可以更轻松地检查记忆化值。

类似的模式，但更有用的是:

(defun foo (bar)
  <does some expensive computation>)

(memoize 'foo)

在IT技术中，“memoize”类似于以下内容

(defun memoize (symbol)
  (let ((original-function (symbol-function symbol))
        (values            (make-hash-table)))
    (setf (symbol-function symbol)
          (lambda (arg &rest args)
            (or (gethash arg values)
                (setf (gethash arg values)
                      (apply original-function arg args)))))))

优点是您不需要为每个函数编写记忆化代码。您只需要一个函数memoize。在这种情况下，闭包也有意义——尽管您也可以有一个全局表来存储记忆化表。

请注意上述的限制：比较使用EQL，并且仅使用要进行记忆化的函数的第一个参数。

还有更广泛的工具可提供类似的功能。

例如，请参见：

使用我上面的memoize：

CL-USER 22 > (defun foo (n)
               (sleep 3)
               (expt 2 n))
FOO

CL-USER 23 > (memoize 'foo)
#<Closure 1 subfunction of MEMOIZE 40600008EC>

第一个带参数 10 的调用需要运行三秒钟。

CL-USER 24 > (foo 10)
1024

第二次调用参数为10的速度更快：

CL-USER 25 > (foo 10)
1024

第一次调用参数为2的函数耗时三秒钟。

CL-USER 26 > (foo 2)
4

第二个带参数 2 的调用运行更快：

CL-USER 27 > (foo 2)
4

第三个使用参数 10 的调用速度很快：

CL-USER 28 > (foo 10)
1024