理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

問題3-27 (3.3.3 Representing Tables)

いわゆるメモ化.
フィボナッチ数列の計算でメモ化使うと,時間計算量がO(n)でできるという話.
プログラムは以下の通りで,計算結果をテーブルに蓄積しておいて,

  • もし既に計算済みの計算結果がテーブルにあれば,それを即座に答えとして返す
  • 計算済みの計算結果がテーブルになければ,計算してその結果をテーブルに蓄積する

という形になっている.

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

environment diagram を書けというのはあまりにもメンドい,かつ煩雑になるので省略する.
なぜO(n)になるかは,F(0),F(1),F(2),F(3)はそれぞれ一度計算すれば,以後逐一計算する必要がなくなるため.
ホントは厳密に証明すべきなんだけど,いまじかんない.