时间戳

首页 > 解决方案 > 记忆化表现 - SICP 练习 3.27 似乎是错误的

scheme - 记忆化表现 - SICP 练习 3.27 似乎是错误的

问题描述

我是否在 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))))))

然后它说

解释为什么 memo-fib 以与 N 成比例的步数计算第 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!use ，它们的步数都与Nassoc成正比。

我不明白步骤数如何与Nmemo-fib成正比。我的观察是：

如果lookup和insert!是常数，那么与nmemo-fib成比例的步数是有意义的。但是实际的步数看起来像n * (nk)其中k是table 中已经存在的键数。

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

标签： schemelispbig-odynamic-programmingsicp

解决方案

看来你是对的。根据经验，它确实以大约二次“复杂性”运行。associninsert!根本不需要；删除它不会改变返回值，只会让它运行得更快。

为了使测试更清晰，我将备忘录更改为不在调用之间共享表格。

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

然后应该变成线性的。

推荐阅读