SICP問題3.27

メモ化(memoization)またはテーブル化(tabulation)の問題。
ちょっと手抜きだけど(memo-fib 3)の計算を解析する環境の図。
後でちゃんと直すかも。

memo-fibがn番目のFibonacchi数をnに比例したステップ数で計算で出来るのは、(n-1)項, (n-2)項の計算結果をtableに格納しており、再帰によって計算をし直す必要がないから。
memo-fibを単に(memoize fib)と定義した場合は、各項の計算結果を覚えているわけでなく、以前の(memoize fib)の計算結果を覚えているだけになるため、再帰的にfibが呼び出されて計算が行われるのでnに比例したステップ数で計算出来ない。
以下実験。

1.2.2節のFibonacci数を計算する指数的プロセス

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else
         (display "in fib [")
         (display n)
         (display "]")
         (newline)
         (+ (fib (- n 1))
            (fib (- n 2))))))

教科書で定義されている一次元の表の表現

(define (lookup key table)
  (let ((record (assoc key (cdr table))))
    (if record
        (cdr record)
        #f)))
(define (assoc key records)
  (cond ((null? records) #f)
        ((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)
(define (make-table)
  (list '*table*))

教科書で定義されているメモ化手続き

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

教科書で定義されているFibonacchi数計算のメモ化版にデバッグ用の命令を追加したもの

(define memo-fib
  (memoize (lambda (n)
             (cond ((= n 0) 0)
                   ((= n 1) 1)
                   (else 
                    (display "in fib [")
                    (display n)
                    (display "]")
                    (newline)
                    (+ (memo-fib (- n 1))
                            (memo-fib (- n 2)))))))) 

(memoize fib)版

(define memo-fib2 
        (memoize fib))

実験結果

(memo-fib 5)
; in fib [5]
; in fib [4]
; in fib [3]
; in fib [2]
; 5
(memo-fib 5)
; 5
(memo-fib2 5)
; 5in fib [5]
; in fib [4]
; in fib [3]
; in fib [2]
; in fib [2]
; in fib [3]
; in fib [2]
; 5
(memo-fib2 5)
; 5
(memo-fib 4)
; 3
(memo-fib2 4)
; in fib [4]
; in fib [3]
; in fib [2]
; in fib [2]
; 3

ということで、(memoize fib)の方は計算結果のみ覚えていることが分かる。