Serendip

Web Studio

問題4.29

メモ化しない force-it

(define (force-it obj)
  (if (thunk? obj)
      (actual-value (thunk-exp obj) (thunk-env obj))
      obj))

メモ化した force-it

(define (force-it obj)
  (cond ((thunk? obj)
         (let ((result (actual-value
                         (thunk-exp obj)
                         (thunk-env obj))))
              (set-car! obj 'evaluated-thunk)
              (set-car! (cdr obj) result) ; exp をその値で置き換える
              (set-cdr! (cdr obj) '()) ; 不要な env を忘れる
              result))
        ((evaluated-thunk? obj)
         (thunk-value obj))
        (else obj)))

手続き driver-loop の actual-value 部分を timeで計測する。

(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read)))
       (let ((output
               (time (actual-value input the-global-environment))))
            (announce-output output-prompt)
            (user-print output)))
  (driver-loop))

Fibonacci 数を求める手続き fib でメモ化"あり"と"なし"の場合のパフォーマンスの差を調べる。

(define (fib n)
  (define (fib-iter a b count)
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1))))
  (fib-iter 1 0 n))

メモ化"あり"の場合

;;; L-Eval input:
(fib 30)
;(time (actual-value input the-global-environment))
; real   0.002
; user   0.000
; sys    0.000

;;; L-Eval value:
832040

メモ化"なし"の場合

;;; L-Eval input:
(fib 30)
;(time (actual-value input the-global-environment))
; real  15.079
; user  15.070
; sys    0.010

;;; L-Eval value:
832040

その差は歴然としている。

次に、問題4.27 の count と手続き id をメモ化"あり"と"なし"の場合で比較する。

(define count 0)

(define (id x)
  (set! count (+ count 1))
  x)

(define (square x) (* x x))

メモ化"あり"の場合

;;; L-Eval input:
(square (id 10))

;;; L-Eval value:
100

;;; L-Eval input:
count

;;; L-Eval value:
1

メモ化"なし"の場合

;;; L-Eval input:
(square (id 10))

;;; L-Eval value:
100

;;; L-Eval input:
count

;;; L-Eval value:
2

メモ化した場合は square の引数である (id 10) が1回しか評価されないため count の値が 1 となる。

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

posted with amazlet at 08.11.07

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

Amazon.co.jp で詳細を見る