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

Question

我是否在SICP书中发现了实际错误？它说:

练习3.27:Memoization(也称为制表)是一种技术,它使过程能够在本地表中记录先前已计算过的值.这种技术可以在程序的性能上产生巨大的差异.memoized过程维护一个表,其中使用产生值的参数作为键存储先前调用的值.当要求memoized过程计算一个值时,它首先检查表以查看该值是否已存在,如果是,则返回该值.否则,它以普通方式计算新值并将其存储在表中.作为记忆的一个例子,从1.2.2回忆计算Fibonacci数的指数过程:

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

相同程序的memoized版本是

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

将memoizer定义为

(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以与N成比例的多个步骤计算第n个Fibonacci数.

这些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,它们都具有的步骤成正比数ñ.

我不明白memo-fib有多少步骤与N成正比.我的观察是:

• 由于memo-fib(lambda具有n作为形式参数)的参数的定义,该表将主要具有有序键,并且将以有序的方式查找键.因此,可以安全地假设对查找的任何调用都接近于恒定时间操作.
• Insert!另一方面,将不会意识到密钥将按某种顺序添加.如果表中不存在某个值,insert!则始终会扫描整个列表,因此n每次都会有一定数量的步骤.
• 如果我们n-1在表中有元素并且我们希望计算(memo-fib n),那么它将具有n与associn中成比例的步数insert!.
• 如果我们没有密钥,那么由于每次递归调用都会调用,(memo-fib n)因此会有与n ²成比例的步数.insert!memo-fib

如果lookup并且insert!是常数,那么memo-fib有多个步骤与n成比例是有意义的.但实际步数看起来像n*(nk),其中k是表中已有的键数.

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

Answer 1

看来你是对的。根据经验，它确实以大约二次“复杂性”运行。in根本不需要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!过程，实际上我们知道我们只将新条目插入表中 - 因为我们首先记住了该函数！

因此，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)

然后应该变成线性的。