SICP問題4.29

SICP

メモ化しないと、メモ化するよりはるかに遅く走ると思われるプログラムを示す問題。

メモ化した場合としない場合の速度差が出るものと言えば、階乗かfibonacciかなぁ。
ということで問題4.24の時と同様にtimeマクロを組み込み、fibを定義して実行時間を見る
まず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))

fib の定義

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

メモ化していないバージョンでの実行結果

;;; L-Eval input:
(fib 10)
;(time (actual-value input the-global-environment))
; real   0.016
; user   0.015
; sys    0.000

;;; L-Eval value:
55

メモ化しているバージョンでの実行結果

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

;;; L-Eval value:
55

これ位だと時間が出てこない位、違う。

もう一つの問題。
問題4.27で定義したid手続きを使用した次の対話を考える。countは0から始まる：

(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:
2         ;; ← 応答

メモ化しているバージョン

(define (square x)
  (* x x))
;;; L-Eval input:
(square (id 10))
;;; L-Eval value:
100       ;; ← 応答
;;; L-Eval input:
count
;;; L-Eval value:
1         ;; ← 応答

問題4.27でも触れたが、以下の理由により上記のような違いが出る。
sqaure を実行する際に本体の (* x x)は

(* (thunk (id 10)) (thunk (id 10)))

に展開される。*は基本手続きなので遅延評価はされない。
メモ化していない版では

  1. 一つ目の (thunk (id 10)) で(id 10)が実行され count が +1 されて 10を返す。
  2. 二つ目の (thunk (id 10))も一つ目と同様に (id 10)もが実行され count が +1 されて 10を返す。

よって count は 2 になる。
メモ化している版では

  1. 一つ目の (thunk (id 10)) で(id 10)が実行され count が +1 されて 10を返す。この時(thunk (id 10))は evaluated-thunk になる。
  2. 二つ目の (thunk (id 10)) は evaluated-thunk の値 10 を返すのみで、count を +1する処理は動かない。

よって count は 1 になる。