Memoization performance - SICP exercise 3.27 似乎是错误的
Memoization performance - SICP exercise 3.27 seems to be wrong
我是否在 SICP 书中发现了实际的错误？它说：
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))))))
然后它说
Explain why memo-fib computes the nth Fibonacci number in a number of steps proportional to N.
insert!和lookup程序在书中定义如下：
(define (lookup key table)
(let ((record (assoc key (cdr table))))
(if record
(cdr record)
false)))
(define (assoc key records)
(cond ((null? records) false)
((equal? key (caar records))
(car records))
(else (assoc key (cdr records)))))
(define (insert! key value table)
(let ((record (assoc key (cdr table))))
(if record
(set-cdr! record value)
(set-cdr! table
(cons (cons key value)
(cdr table)))))
'ok)
现在，assoc 的步数与 n 成正比。由于 lookup 和 insert! 使用 assoc，它们的步数都与 N 成正比。
我不明白 memo-fib 的步数如何与 N 成正比。我的观察是：
- 由于
memo-fib 参数的定义（具有 n 作为形式参数的 lambda），table 将主要是有序键，并且键将以有序的方式进行查找。因此可以安全地假设对查找的任何调用都接近于恒定时间操作。
另一方面，Insert! 不会知道密钥将按某种顺序添加。如果 table 中不存在某个值，insert! 将始终扫描整个列表，因此每次的步数都与 n 成正比。- 如果我们在 table 中有
n-1 个元素并且我们希望计算 (memo-fib n)，它的步数将与 n 成正比由于 insert!. 中的 assoc
- 如果我们没有密钥，那么
(memo-fib n) 的步数将与 n2 成正比，因为 insert! 每次递归调用 memo-fib.
如果 lookup 和 insert! 是常数，那么 memo-fib 的步数与 n 成比例是有意义的。但是实际的步骤数看起来像 n * (n-k) 其中 k 是 中已有的键数88=].
我做错了吗？我错过了什么？
看来你是对的。它 运行 的二次方 "complexity"、empirically。 insert!中的assoc根本不需要；删除它不会改变 return 值，只会使其 运行 快得多。
为了使测试更清晰，我已将记忆更改为 不 在调用之间共享 table。
#lang r5rs
(#%require srfi/19)
(define false #f)
(define true #t)
(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))))))
(define (lookup key table)
(let ((record (assoc key (cdr table))))
(if record
(cdr record)
false)))
(define (assoc key records)
(cond ((null? records) false)
((equal? key (caar records))
(car records))
(else (assoc key (cdr records)))))
(define (insert! key value table)
(let ((record #f ; NB
; (assoc key (cdr table)) ; NB
))
(if record
(set-cdr! record value)
(set-cdr! table
(cons (cons key value)
(cdr table)))))
'ok)
(define (make-table)
(list '*table*))
(define memo-fib
(lambda (n)
(letrec ((mf (memoize ; NB
(lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else
(+ (mf (- n 1))
(mf (- n 2)))))))))
(mf n))))
(define (tt n)
(let* ((t1 (current-time))
(f (memo-fib n))
(t2 (current-time))
(td (time-difference t2 t1))
(n (time-nanosecond td)))
(/
(+ (* (time-second td) 1000000000)
n)
1000000.0))) ; time in milliseconds
; > (memo-fib 100)
; 354224848179261915075
(define (tt2 n1 n2)
(let* ((t1 (tt n1))
(t2 (tt n2)))
(values t1 t2
(cond ((> t1 0)
(/ (log (/ t2 t1)) (log (/ n2 n1))))))))
测试以非常基本的方式完成。时间以毫秒为单位。
; with the lookup in insert!:
; n1 n2 t1 t2 a in t ~ n^a, empirically
; > (tt2 2000 3000) ;=> 90.0 200.0 1.96936
; > (tt2 2000 3000) ;=> 100.0 220.0 1.94457
; > (tt2 2000 3000) ;=> 90.0 210.0 2.08969
; without the lookup: 80,000 takes under 1 second
; but run times are wildly erratic
所以这看起来确实像是作者的疏忽，他们使用了一般的 insert! 程序，实际上我们 知道 我们只插入 table 中的新 条目 -- 因为我们首先 memoize 函数！
因此，insert! 应替换为 insert-new!:
(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-new! x result table)
result))))))
(define (insert-new! key value table)
(set-cdr! table
(cons (cons key value)
(cdr table)))
'ok)
然后是应该变成线性的。
我是否在 SICP 书中发现了实际的错误？它说：
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))))))
然后它说
Explain why memo-fib computes the nth Fibonacci number in a number of steps proportional to N.
insert!和lookup程序在书中定义如下：
(define (lookup key table)
(let ((record (assoc key (cdr table))))
(if record
(cdr record)
false)))
(define (assoc key records)
(cond ((null? records) false)
((equal? key (caar records))
(car records))
(else (assoc key (cdr records)))))
(define (insert! key value table)
(let ((record (assoc key (cdr table))))
(if record
(set-cdr! record value)
(set-cdr! table
(cons (cons key value)
(cdr table)))))
'ok)
现在，assoc 的步数与 n 成正比。由于 lookup 和 insert! 使用 assoc，它们的步数都与 N 成正比。
我不明白 memo-fib 的步数如何与 N 成正比。我的观察是：
- 由于
memo-fib参数的定义（具有n作为形式参数的 lambda），table 将主要是有序键，并且键将以有序的方式进行查找。因此可以安全地假设对查找的任何调用都接近于恒定时间操作。
另一方面， Insert!不会知道密钥将按某种顺序添加。如果 table 中不存在某个值，insert!将始终扫描整个列表，因此每次的步数都与n成正比。- 如果我们在 table 中有
n-1个元素并且我们希望计算(memo-fib n)，它的步数将与n成正比由于insert!. 中的 - 如果我们没有密钥，那么
(memo-fib n)的步数将与 n2 成正比，因为insert!每次递归调用memo-fib.
assoc
如果 lookup 和 insert! 是常数，那么 memo-fib 的步数与 n 成比例是有意义的。但是实际的步骤数看起来像 n * (n-k) 其中 k 是 中已有的键数88=].
我做错了吗？我错过了什么？
看来你是对的。它 运行 的二次方 "complexity"、empirically。 insert!中的assoc根本不需要；删除它不会改变 return 值，只会使其 运行 快得多。
为了使测试更清晰，我已将记忆更改为 不 在调用之间共享 table。
#lang r5rs
(#%require srfi/19)
(define false #f)
(define true #t)
(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))))))
(define (lookup key table)
(let ((record (assoc key (cdr table))))
(if record
(cdr record)
false)))
(define (assoc key records)
(cond ((null? records) false)
((equal? key (caar records))
(car records))
(else (assoc key (cdr records)))))
(define (insert! key value table)
(let ((record #f ; NB
; (assoc key (cdr table)) ; NB
))
(if record
(set-cdr! record value)
(set-cdr! table
(cons (cons key value)
(cdr table)))))
'ok)
(define (make-table)
(list '*table*))
(define memo-fib
(lambda (n)
(letrec ((mf (memoize ; NB
(lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else
(+ (mf (- n 1))
(mf (- n 2)))))))))
(mf n))))
(define (tt n)
(let* ((t1 (current-time))
(f (memo-fib n))
(t2 (current-time))
(td (time-difference t2 t1))
(n (time-nanosecond td)))
(/
(+ (* (time-second td) 1000000000)
n)
1000000.0))) ; time in milliseconds
; > (memo-fib 100)
; 354224848179261915075
(define (tt2 n1 n2)
(let* ((t1 (tt n1))
(t2 (tt n2)))
(values t1 t2
(cond ((> t1 0)
(/ (log (/ t2 t1)) (log (/ n2 n1))))))))
测试以非常基本的方式完成。时间以毫秒为单位。
; with the lookup in insert!:
; n1 n2 t1 t2 a in t ~ n^a, empirically
; > (tt2 2000 3000) ;=> 90.0 200.0 1.96936
; > (tt2 2000 3000) ;=> 100.0 220.0 1.94457
; > (tt2 2000 3000) ;=> 90.0 210.0 2.08969
; without the lookup: 80,000 takes under 1 second
; but run times are wildly erratic
所以这看起来确实像是作者的疏忽，他们使用了一般的 insert! 程序，实际上我们 知道 我们只插入 table 中的新 条目 -- 因为我们首先 memoize 函数！
因此，insert! 应替换为 insert-new!:
(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-new! x result table)
result))))))
(define (insert-new! key value table)
(set-cdr! table
(cons (cons key value)
(cdr table)))
'ok)
然后是应该变成线性的。