代码之家 › 专栏 › 技术社区 › lightning_missile

记忆化性能-SICP练习3.27似乎是错误的

sicp dynamic-programming big-o lisp scheme

lightning_missile · 技术社区 · 7 年前

我发现了一个真实的错误在SICP的书里?上面写着:

练习3.27:记忆(也称为表格)是一种技巧使过程能够在本地表中记录具有之前已经计算过了。这项技术可以在很大程度上改变其中以前调用的值存储为键当被要求计算一个值时,它首先检查表以确定值已经存在,如果存在,则返回该值。否则, 桌子。作为回忆录的一个例子,回想一下1.2.2中的指数计算斐波那契数的过程:

(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))))))

然后它说

这个 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 查找 插入! 使用 协会 ,它们的步数与 N

我不明白怎么回事 memo-fib 步骤数与 N

由于参数的定义 备忘录 (具有 n 作为形式参数),表中的键大部分是有序的,并且会以有序的方式查找键。因此,可以安全地假设对lookup的任何调用都接近于一个常数时间操作。
Insert! 另一方面,我们不会意识到这些键是按某种顺序添加的。如果表中不存在值, 将始终扫描整个列表,因此它的步数将与 n 每一次。
n-1 (memo-fib n) ,它的步数与 n 由于 协会 插入! .
如果我们没有钥匙 (备忘录) n ² 由于 插入! 每次递归调用 .

如果 查找 和 插入! 备忘录 n . 但实际步骤数看起来哪里是数字 表中已有键

我做错了吗?我错过了什么?

1 回复 | 直到 7 年前

Will Ness Derri Leahy 7 年前

empirically . 这个 assoc 在里面 insert!

为了让测试更清晰,我把备忘录改成了在两个电话之间共用一张桌子。

#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-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)

然后是应该变成线性。