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)の方は計算結果のみ覚えていることが分かる。