Exercise 3.27 · 习题

Exercise 3.27:
Memoization (also
called
tabulation) is a technique that enables a procedure to record,
in a local table, values that have previously been computed. This technique
can make a vast difference in the performance of a program. A memoized
procedure maintains a table in which values of previous calls are stored using
as keys the arguments that produced the values. When the memoized procedure is
asked to compute a value, it first checks the table to see if the value is
already there and, if so, just returns that value. Otherwise, it computes the
new value in the ordinary way and stores this in the table. As an example of
memoization, recall from 1.2.2 the exponential process for
computing Fibonacci numbers:

(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))

The memoized version of the same procedure is

(define memo-fib
(memoize
(lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else
(+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))

where the memoizer is defined as

(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result
(lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))

Draw an environment diagram to analyze the computation of (memo-fib 3).
Explain why memo-fib computes the n

th Fibonacci number in a number

of steps proportional to n. Would the scheme still work if we had simply

defined memo-fib to be (memoize fib)?

练习 3.27：记忆化 (memoization)（也称为制表法 (tabulation)）是一种技术，使过程能够在局部表中记录之前已计算过的值。这种技术能够极大地改善程序的性能。经过记忆化的过程维护一张表，其中以产生各结果的实际参数为键来存储先前调用的值。当记忆化过程被要求计算某个值时，它首先检查表中是否已有该值；如果有，就直接返回该值；否则，以正常方式计算新值并将其存入表中。以记忆化为例，回忆 1.2.2 节中计算 Fibonacci 数的指数型计算过程：

(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))

同一过程的记忆化版本为：

(define memo-fib
(memoize
(lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else
(+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))

其中记忆器定义为：

(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result
(lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))

请画出环境图，分析 (memo-fib 3) 的计算过程。解释为什么 memo-fib 计算第 n 个 Fibonacci 数所需的步骤数正比于 n。如果我们只是简单地将 memo-fib 定义为 (memoize fib)，这个方案还能奏效吗？