如何在球拍中制作一个函数的记忆版本
How to make a function a memoized version of it in racket
我正在尝试定义一个以函数 f 作为参数的 make-memoize 函数。这个想法是 make-memoize 将 return 一个 运行 带有记忆的过程 f。在使用函数 f 作为参数定义 make-memoize 之后，我已经能够 return 一个过程。但是，我无法实际应用该函数来表示加、减或乘数字。 IE。如果我将带有加一功能的 make-memoize 作为参数应用到数字 28，我应该得到 29 作为结果。
这是我目前得到的：
(define (make-memoize f)
(let ((memoized-values (make-hash)))
(lambda (n)
(if (hash-has-key? memoized-values n)
(hash-ref memoized-values n)
(f n)))))
当我 运行 使用函数对 28 加一进行记忆时：
(make-memoize (add-one 28))
这是我得到的：
> (make-memoize (slow-add-one 28))
#<procedure:...s/rack-folder/test-file.rkt:26:4>
好像是把程序和目录丢给我？感谢您的帮助。
我看到几个问题：
- 您没有使用计算值
更新散列 table
make-memoize 是一个从函数
所以正确的用法是这样的：
(define (add-one n)
(+ n 1))
(let ((fast-add-one (make-memoize add-one)))
(fast-add-one 1)
(fast-add-one 1)
(fast-add-one 1))
完整代码如下，可以从Racket IDE:
执行
(define (add-one n)
(+ n 1))
(define (make-memoize f)
(let ((memoized-values (make-hash)))
(lambda (n)
(if (hash-has-key? memoized-values n)
;; Get and return the value from hash-table
(let ((previous-value (hash-ref memoized-values n)))
(printf "READ VALUE ~A->~A~%" n previous-value)
previous-value)
;; Update the value in the hash table
(let ((new-value (f n)))
(printf "SET VALUE ~A->~A~%" n new-value)
(hash-set! memoized-values n new-value)
new-value)))))
(let ((fast-add-one (make-memoize add-one)))
(fast-add-one 1)
(fast-add-one 1)
(fast-add-one 1))
评估结果应如下所示：
SET VALUE 1->2 ;; Here, this is the first computation of add-one
READ VALUE 1->2 ;; Here, we just read from hash table
READ VALUE 1->2 ;; Here, we just read from hash table
编辑：您的错误问题
的答案
> (make-memoize (slow-add-one 28))
#<procedure:...s/rack-folder/test-file.rkt:26:4>
这不是错误，Racket 解释器只是 return 在给定的 filename/line.[=21= 中定义的 procedure （函数） ]
在我提供的代码中，函数调用 (make-memoize add-one)) 也是 return 一个 procedure。
> (make-memoize add-one))
#<procedure>
记忆化最常见的用途之一是减少递归过程调用中的计算量。即使单独修复发布的代码也不允许这样做。此外，将使用 make-memoize 创建的过程绑定到新标识符将无效，因为未记忆的过程仍在所有递归调用中使用。
至于原始发布的代码，给定一些密钥，目标是用新密钥更新散列 table 除非该密钥已经在 table 中找到（表明计算已经做了并存储。如果没有找到key，那么应该为key计算一个值，并将结果存储在table中。无论哪种情况，应返回与密钥关联的值。
这是对刚才描述内容的非常直白的转录：
(define (memo f)
(let ((lookup (make-hash)))
(lambda (x)
(unless (hash-has-key? lookup x)
(hash-set! lookup x (f x)))
(hash-ref lookup x))))
这里，memo returns 一个过程，当用 x 调用时，检查 lookup 键 x。如果未找到 x，则将其添加到 lookup 并与 (f x) 的值相关联。最后，返回与 x 关联的值。
let-绑定仅适用于有限的情况
当memo化过程递归时，没有得到预期的效果。每个递归调用都使用 f，而不是 f 的 memo 化版本，因此除了初始调用之外没有进一步的查找。例如，给定：
(define (fibonacci n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fibonacci (- n 2))
(fibonacci (- n 1))))))
这将无法正常工作：
(let ((fast-fib (memo fibonacci)))
(fast-fib 40))
这里 fast-fib 绑定到 memo 化的过程，但是 fibonacci 被调用用于递归调用，因为这就是 fibonacci 的定义方式。这也行不通：
(let ((fibonacci (memo fibonacci)))
(fibonacci 40))
这里 fibonacci 是反弹到 memo 化的程序，但是 fibonacci 调用了 原始 版本的 fibonacci在定义时，并继续这样做。
您需要找到一种方法来更改 fibonacci 的定义，以便它本身就是 memo 化的过程。您可以使用 set! 来完成此操作。您可以在使用 fibonacci 之前评估 (set! fibonacci (memo fibonacci))。如果有一个宏可以为你做这件事会更好：
(define-syntax-rule (memoize! f)
(set! f (memo f)))
这是一个非常简单的宏，它只是重新定义了给定的过程，因此它是 memo 化的。以下是一些比较失败方法和成功方法的示例：
memoize.rkt> (time (fibonacci 40))
cpu time: 2780 real time: 2780 gc time: 0
102334155
memoize.rkt> (time (let ((fast-fib (memo fibonacci))) (fast-fib 40)))
cpu time: 2800 real time: 2800 gc time: 1
102334155
memoize.rkt> (time (let ((fibonacci (memo fibonacci))) (fibonacci 40)))
cpu time: 2789 real time: 2789 gc time: 0
102334155
memoize.rkt> (memoize! fibonacci)
memoize.rkt> (time (fibonacci 40))
cpu time: 0 real time: 0 gc time: 0
102334155
从上面可以看出，失败的方法根本没有改进 fibonacci 过程的 运行 时间；事实上，这些错误记忆的版本似乎比 fibonacci 的裸调用 慢 一点点。这是因为在 fibonacci 上调用 memo 会产生额外的开销，这会创建一个毫无意义的记忆版本，仅在初始调用时调用 （所有后续调用确实在调用裸 fibonacci 过程）。但是成功记忆的版本在递归调用中调用 自身 ，并且显示出相当大的改进。
为了强调记忆的价值，以及犯错的惩罚，请考虑 (fibonacci 45)。这似乎比之前的 (fibonacci 40):
略有增加
memoize.rkt> (time (let ((fast-fib (memo fibonacci))) (fast-fib 45)))
cpu time: 31042 real time: 31042 gc time: 11
1134903170
memoize.rkt> (memoize! fibonacci)
memoize.rkt> (time (fibonacci 45))
cpu time: 0 real time: 0 gc time: 0
1134903170
并且由于正确记忆的版本在调用之间缓存了结果，我为下一个测试重新启动了 REPL：
memoize.rkt> (memoize! fibonacci)
memoize.rkt> (time (fibonacci 1000))
cpu time: 1 real time: 1 gc time: 0
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
fast-fib版本计算(fast-fib 40)用了将近3秒，计算(fast-fib 45)用了31秒。这是仅将输入值增加 5 的数量级减速。但是，fibonacci 的正确记忆版本花费不到 1 微秒来计算 (fibonacci 40)，再次计算不到 1 微秒(fibonacci 45)，计算 (fibonacci 1000) 大约需要 1 微秒（在所有三种情况下都从空的 lookup table 开始；多次调用 fibonacci 时性能甚至更好不清除缓存）。您将等待非常非常长的时间才能完成 (fast-fib 1000)。
有很多方法可以改进这一点；您可能希望能够记忆多个参数的过程，或者您可能希望能够清除记忆过程的查找 table，或者您可能希望能够取消记忆一个过程，等等。对于任何想要深入研究的人来说，至少可以追溯到 1960 年代，有很多关于记忆的文献。这个从另一个过程创建记忆过程的特定主题称为 自动记忆 。 Here is a paper by Peter Norvig that includes a nice discussion of the technique;注意本文使用Common Lisp作为实现语言
我正在尝试定义一个以函数 f 作为参数的 make-memoize 函数。这个想法是 make-memoize 将 return 一个 运行 带有记忆的过程 f。在使用函数 f 作为参数定义 make-memoize 之后，我已经能够 return 一个过程。但是，我无法实际应用该函数来表示加、减或乘数字。 IE。如果我将带有加一功能的 make-memoize 作为参数应用到数字 28，我应该得到 29 作为结果。
这是我目前得到的：
(define (make-memoize f)
(let ((memoized-values (make-hash)))
(lambda (n)
(if (hash-has-key? memoized-values n)
(hash-ref memoized-values n)
(f n)))))
当我 运行 使用函数对 28 加一进行记忆时：
(make-memoize (add-one 28))
这是我得到的：
> (make-memoize (slow-add-one 28))
#<procedure:...s/rack-folder/test-file.rkt:26:4>
好像是把程序和目录丢给我？感谢您的帮助。
我看到几个问题：
- 您没有使用计算值 更新散列 table
make-memoize是一个从函数 创建新函数的函数
所以正确的用法是这样的：
(define (add-one n)
(+ n 1))
(let ((fast-add-one (make-memoize add-one)))
(fast-add-one 1)
(fast-add-one 1)
(fast-add-one 1))
完整代码如下，可以从Racket IDE:
(define (add-one n)
(+ n 1))
(define (make-memoize f)
(let ((memoized-values (make-hash)))
(lambda (n)
(if (hash-has-key? memoized-values n)
;; Get and return the value from hash-table
(let ((previous-value (hash-ref memoized-values n)))
(printf "READ VALUE ~A->~A~%" n previous-value)
previous-value)
;; Update the value in the hash table
(let ((new-value (f n)))
(printf "SET VALUE ~A->~A~%" n new-value)
(hash-set! memoized-values n new-value)
new-value)))))
(let ((fast-add-one (make-memoize add-one)))
(fast-add-one 1)
(fast-add-one 1)
(fast-add-one 1))
评估结果应如下所示：
SET VALUE 1->2 ;; Here, this is the first computation of add-one
READ VALUE 1->2 ;; Here, we just read from hash table
READ VALUE 1->2 ;; Here, we just read from hash table
编辑：您的错误问题
的答案> (make-memoize (slow-add-one 28))
#<procedure:...s/rack-folder/test-file.rkt:26:4>
这不是错误，Racket 解释器只是 return 在给定的 filename/line.[=21= 中定义的 procedure （函数） ]
在我提供的代码中，函数调用 (make-memoize add-one)) 也是 return 一个 procedure。
> (make-memoize add-one))
#<procedure>
记忆化最常见的用途之一是减少递归过程调用中的计算量。即使单独修复发布的代码也不允许这样做。此外，将使用 make-memoize 创建的过程绑定到新标识符将无效，因为未记忆的过程仍在所有递归调用中使用。
至于原始发布的代码，给定一些密钥，目标是用新密钥更新散列 table 除非该密钥已经在 table 中找到（表明计算已经做了并存储。如果没有找到key，那么应该为key计算一个值，并将结果存储在table中。无论哪种情况，应返回与密钥关联的值。
这是对刚才描述内容的非常直白的转录：
(define (memo f)
(let ((lookup (make-hash)))
(lambda (x)
(unless (hash-has-key? lookup x)
(hash-set! lookup x (f x)))
(hash-ref lookup x))))
这里，memo returns 一个过程，当用 x 调用时，检查 lookup 键 x。如果未找到 x，则将其添加到 lookup 并与 (f x) 的值相关联。最后，返回与 x 关联的值。
let-绑定仅适用于有限的情况
当memo化过程递归时，没有得到预期的效果。每个递归调用都使用 f，而不是 f 的 memo 化版本，因此除了初始调用之外没有进一步的查找。例如，给定：
(define (fibonacci n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fibonacci (- n 2))
(fibonacci (- n 1))))))
这将无法正常工作：
(let ((fast-fib (memo fibonacci)))
(fast-fib 40))
这里 fast-fib 绑定到 memo 化的过程，但是 fibonacci 被调用用于递归调用，因为这就是 fibonacci 的定义方式。这也行不通：
(let ((fibonacci (memo fibonacci)))
(fibonacci 40))
这里 fibonacci 是反弹到 memo 化的程序，但是 fibonacci 调用了 原始 版本的 fibonacci在定义时，并继续这样做。
您需要找到一种方法来更改 fibonacci 的定义，以便它本身就是 memo 化的过程。您可以使用 set! 来完成此操作。您可以在使用 fibonacci 之前评估 (set! fibonacci (memo fibonacci))。如果有一个宏可以为你做这件事会更好：
(define-syntax-rule (memoize! f)
(set! f (memo f)))
这是一个非常简单的宏，它只是重新定义了给定的过程，因此它是 memo 化的。以下是一些比较失败方法和成功方法的示例：
memoize.rkt> (time (fibonacci 40))
cpu time: 2780 real time: 2780 gc time: 0
102334155
memoize.rkt> (time (let ((fast-fib (memo fibonacci))) (fast-fib 40)))
cpu time: 2800 real time: 2800 gc time: 1
102334155
memoize.rkt> (time (let ((fibonacci (memo fibonacci))) (fibonacci 40)))
cpu time: 2789 real time: 2789 gc time: 0
102334155
memoize.rkt> (memoize! fibonacci)
memoize.rkt> (time (fibonacci 40))
cpu time: 0 real time: 0 gc time: 0
102334155
从上面可以看出，失败的方法根本没有改进 fibonacci 过程的 运行 时间；事实上，这些错误记忆的版本似乎比 fibonacci 的裸调用 慢 一点点。这是因为在 fibonacci 上调用 memo 会产生额外的开销，这会创建一个毫无意义的记忆版本，仅在初始调用时调用 （所有后续调用确实在调用裸 fibonacci 过程）。但是成功记忆的版本在递归调用中调用 自身 ，并且显示出相当大的改进。
为了强调记忆的价值，以及犯错的惩罚，请考虑 (fibonacci 45)。这似乎比之前的 (fibonacci 40):
memoize.rkt> (time (let ((fast-fib (memo fibonacci))) (fast-fib 45)))
cpu time: 31042 real time: 31042 gc time: 11
1134903170
memoize.rkt> (memoize! fibonacci)
memoize.rkt> (time (fibonacci 45))
cpu time: 0 real time: 0 gc time: 0
1134903170
并且由于正确记忆的版本在调用之间缓存了结果，我为下一个测试重新启动了 REPL：
memoize.rkt> (memoize! fibonacci)
memoize.rkt> (time (fibonacci 1000))
cpu time: 1 real time: 1 gc time: 0
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
fast-fib版本计算(fast-fib 40)用了将近3秒，计算(fast-fib 45)用了31秒。这是仅将输入值增加 5 的数量级减速。但是，fibonacci 的正确记忆版本花费不到 1 微秒来计算 (fibonacci 40)，再次计算不到 1 微秒(fibonacci 45)，计算 (fibonacci 1000) 大约需要 1 微秒（在所有三种情况下都从空的 lookup table 开始；多次调用 fibonacci 时性能甚至更好不清除缓存）。您将等待非常非常长的时间才能完成 (fast-fib 1000)。
有很多方法可以改进这一点；您可能希望能够记忆多个参数的过程，或者您可能希望能够清除记忆过程的查找 table，或者您可能希望能够取消记忆一个过程，等等。对于任何想要深入研究的人来说，至少可以追溯到 1960 年代，有很多关于记忆的文献。这个从另一个过程创建记忆过程的特定主题称为 自动记忆 。 Here is a paper by Peter Norvig that includes a nice discussion of the technique;注意本文使用Common Lisp作为实现语言