SICP 問題 4.29
メモ化しないとはるかに遅くなるプログラムの例として
再帰でフィボナッチ数列の第n項を求める手続きを定義する.
(define (fib n) (let iter ((a 0) (b 1) (count n)) (if (= count 0) a (iter b (+ a b) (- count 1))))) ;; メモ化する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))) ;; メモ化しないforce-it (define (force-it obj) (if (thunk? obj) (actual-value (thunk-exp obj) (thunk-env obj)) obj)) ;; driver-loopにtimeマクロを仕込む (define (driver-loop) (prompt-for-input input-prompt) (let ((input (read))) (let ((output (time (actual-value input the-global-environment)))) ;;ここにtimeマクロ (announce-output output-prompt) (user-print output))) (driver-loop))
メモ化する場合
;;; M-Eval input: (fib 30) ;(time (actual-value input the-global-environment)) ; real 0.001 ; user 0.000 ; sys 0.000 ;;; M-Eval value: 832040
メモ化しない場合
;;; M-Eval input: (fib 30) ;(time (actual-value input the-global-environment)) ; real 6.559 ; user 6.540 ; sys 0.000 ;;; M-Eval value: 832040
(define (square x) (* x x)) (define (id x) (set! count (+ count 1)) x)
メモ化する場合
;;; M-Eval input: (square (id 10)) ;;; M-Eval value: 100 ;;; M-Eval input: count ;;; M-Eval value: 1
メモ化しない場合
;;; M-Eval input: (square (id 10)) ;;; M-Eval value: 100 ;;; M-Eval input: count ;;; M-Eval value: 2
メモ化すると(* x x)を評価する時に初めのxは(thunk (id 10))となっているのでこれをforce-itしてcountを+1して10を返し,
xの束縛を(evaluated-thunk 10)に変える.
次のxをforce-itするとそのまま10が返る.