为了简化分析,先将 memoize
转换成一系列表达式:
;;; 27-memoize.scm
(define memoize
(lambda (f)
((lambda (table)
(lambda (x)
((lambda (previously-computed-result)
(or previously-computed-result
((lambda (result)
(insert! x result table)
result)
(f x))))
(lookup x table))))
(make-table))))
memo-fib
已经是 lambda
表达式了,所以不用转换:
;;; 27-memo-fib.scm
(load "p184-table.scm")
(load "27-memoize.scm")
(define memo-fib
(memoize (lambda (n)
(cond ((= n 0)
0)
((= n 1)
1)
(else
(+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
当表达式 (memo-fib 3)
执行时,它首先展开表达式 (memoize (lambda (n) ...))
,调用以下执行序列:
(memo-fib 3) ; 展开 memoize
((lambda (f) ; 展开参数 f
((lambda (table)
(lambda (x)
((lambda (previously-computed-result)
(or previously-computed-result
((lambda (result)
(insert! x result table)
result)
(f x))))
(lookup x table))))
(make-table)))
(lambda (n)
(cond ((= n 0)
0)
((= n 1)
1)
(else
(+ (memo-fib (- n 1))
(memo-fib (- n 2)))))))
((lambda (table) ; 创建表,展开参数 table
(lambda (x)
((lambda (previously-computed-result)
(or previously-computed-result
((lambda (result)
(insert! x result table)
result)
((lambda (n)
(cond ((= n 0)
0)
((= n 1)
1)
(else
(+ (memo-fib (- n 1))
(memo-fib (- n 2))))))
x))))
(lookup x table))))
(make-table))
(lambda (x) ; (memoize (lambda (n) ...)) 展开完毕
((lambda (previously-computed-result)
(or previously-computed-result
((lambda (result)
(insert! x result table)
result)
((lambda (n)
(cond ((= n 0)
0)
((= n 1)
1)
(else
(+ (memo-fib (- n 1))
(memo-fib (- n 2))))))
x))))
(lookup x table)))
以上表达式创建这样一个环境:
+-----------------------------------------------------------------------------------------------------+
| |
global -> | memo-fib |
env | | |
+--|--------------------------------------------------------------------------------------------------+
| ^
| |
| (lambda (f) ...) |
| |
| +-----+
| | |
| | |<---------+
| | | |
| | f ------->[*][*]
| | | parameters: n
| +-----+ body: (cond ((= n 0)
| ^ 0)
| | ((= n 1)
| | 1)
| (lambda (table) | (else
| ...) | (+ (memo-fib (- n 1))
| | (memo-fib (- n 2)))))
| |
| +-------+
| | |
| | |<------------------------------------------+
| | | |
| | table -----------------------------------+ +------------------------------+
| | | | | |
| +-------+ | | local-table: (list '*table*) |
| | ^ | | |
| | | | | assoc |
+--------------->[*][*] | | lookup |
| | | insert! |
| +----->dispatch |
| | |
| +------------------------------+
v
parameters: x
body: ((lambda (previously-computed-result)
(or previously-computed-result
((lambda (result)
(insert! x result table)
result)
(f x))))
(lookup x table))
将参数 3
应用到表达式 (lambda (x) ...)
,将创建这样一个环境:
+-----------------------------------------------------------------------------------------------------+
| |
global -> | memo-fib |
env | | |
+--|--------------------------------------------------------------------------------------------------+
| ^
| |
| (lambda (f) ...) |
| |
| +-----+
| | |
| | |<---------+
| | | |
| | f ------->[*][*]
| | | parameters: n
| +-----+ body: (cond ((= n 0)
| ^ 0)
| | ((= n 1)
| | 1)
| (lambda (table) | (else
| ...) | (+ (memo-fib (- n 1))
| | (memo-fib (- n 2)))))
| |
| +-------+
| | |
| | |<------------------------------------------+
|+--------------| | |
vv | table -----------------------------------+ +------------------------------+
[*][*]--------->| | | | |
| +-------+ | | local-table: (list '*table*) |
v ^ | | |
parameters: x | | | assoc |
body: ... | | | lookup |
| | | insert! |
| +----->dispatch |
(lambda (x) | | |
...) | +------------------------------+
|
+------+
| |
| x: 3 |
| |
+------+
^
|
(lambda |
(previously-computed-result) |
...) |
|
|
+----------------------------------------------+
| |
| previously-computed-result: (lookup x table) |
| |
+----------------------------------------------+
(or previously-computed-result
((lambda (result)
(insert! x result table)
result)
(f x)))
当 (memo-fib 3)
计算完毕之后,环境变成了这样:
+--------------------+
| |
global -> | memo-fib |
env | |
+--------------------+
^
|
(lambda (f) ...) |
|
+-----+
| |
| |<---------+
| | |
| f ------->[*][*]
| | parameters: n
+-----+ body: (cond ((= n 0)
^ 0)
| ((= n 1)
| 1)
(lambda (table) | (else
...) | (+ (memo-fib (- n 1))
| (memo-fib (- n 2)))))
|
+-------+
| |
| |<------------------------------------------+
| | |
| table -----------------------------------+ +---------------------------------------------------------------+
| | | | |
+-------+ | | local-table: (list '*table* (cons 3 2) (cons 2 1) (cons 1 1)) |
| ^ | | |
| | | | assoc |
[*][*] | | lookup |
| | | insert! |
| +----->dispatch |
| | |
| +---------------------------------------------------------------+
v
parameters: x
body: ((lambda (previously-computed-result)
(or previously-computed-result
((lambda (result)
(insert! x result table)
result)
(f x))))
(lookup x table))
注意指向 table
的子环境中的 local-table
的值,在计算开始之前,它除了表头之外没有其他元素,现在它保存了三组斐波那契数的计算结果。
这也是 (memo-fib 3)
可以在线性时间内完成计算的原因: memo-fib
每次计算出一个斐波那契数 (memo-fib i)
,就将 i
和 (memo-fib i)
组成序对,并将这个序对加入进 local-table
里面;如果下次再遇到同样的 i
,那么 memo-fib
就直接返回 local-table
中对应的斐波那契数,从而消除了重复计算。
题目的另一个问题是,如果简单地将 memo-fib
定义为 (memoize fib)
,那么记忆法还能工作吗?
可以在解释器中尝试运行这个新的定义:
;;; 27-another-memo-fib.scm
(load "p184-table.scm")
(load "27-memoize.scm")
(define (fib n)
(cond ((= n 0)
0)
((= n 1)
1)
(else
(+ (fib (- n 1))
(fib (- n 2))))))
(define memo-fib (memoize fib))
测试:
1 ]=> (load "27-another-memo-fib.scm")
;Loading "27-another-memo-fib.scm"...
; Loading "p184-table.scm"... done
; Loading "27-memoize.scm"... done
;... done
;Value: memo-fib
1 ]=> (memo-fib 3)
;Value: 2
需要注意的是,虽然这个新的 memo-fib
也可以正常运行,但它的执行效率并没有太大的提高:因为每次调用 (memo-fib i)
的时候,这个 memo-fib
只保存 i
和 (memo-fib i)
的值,但是其他的斐波那契计算结果,这个 memo-fib
并不保存。
比如说,当调用 (memo-fib 3)
时, (memo-fib 3)
的结果会被保存进表里面,但是 (memo-fib 2)
和 (memo-fib 1)
的计算结果却不会被保存。
因此,这个版本的 memo-fib
仍然会有重复计算,它的复杂度仍然是指数级的。