Serendip

Web Studio

問題3.27

(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)
                             (display "x : ")
                             (display x)
                             (newline)
                             (display "table : ")
                             (display table)
                             (newline)
                             result))))))

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

実行結果

1度実行した memo-fib の値はテーブルに記録されるので、再帰呼び出しの内の一方はテーブルの参照で済む。

(memo-fib 3)
gosh> x : 1
table : (*table* (1 . 1))
x : 0
table : (*table* (0 . 0) (1 . 1))
x : 2
table : (*table* (2 . 1) (0 . 0) (1 . 1))
x : 3
table : (*table* (3 . 2) (2 . 1) (0 . 0) (1 . 1))
2
(memo-fib 6)
gosh> x : 4
table : (*table* (4 . 3) (3 . 2) (2 . 1) (0 . 0) (1 . 1))
x : 5
table : (*table* (5 . 5) (4 . 3) (3 . 2) (2 . 1) (0 . 0) (1 . 1))
x : 6
table : (*table* (6 . 8) (5 . 5) (4 . 3) (3 . 2) (2 . 1) (0 . 0) (1 . 1))
8
(memo-fib 3)
gosh> 2

fib が再帰的に呼び出されるので、テーブルが作られずメモ化されない。

(define memo-fib2 fib)
(memo-fib2 3)
gosh> 2
(memo-fib2 6)
gosh> 8
(memo-fib2 3)
gosh> 2

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る