Exercise3.57
How many additions are performed when we compute the nth Fibonacci number using the definition of fibs based on the add-streams procedure? Show that the number of additions would be exponentially greater if we had implemented (delay <exp>) simply asw (lambda () <exp>), without using the optimization provided by the memo-proc procedure described in section 3.5.1
add-streamプロシージャベースのfibsの定義を使用し、フィボナッチ数を計算したとき、何度加法を実行しているだろうか?memo-procを使用していなければ、指数関数的に増加していることをしめせ。
この問題を解くにあたり、gnuplotを用いて視覚的に指数関数的に増加していることを示してみた。
以下、用いたコードを記す。
注意点として、私個人のこだわりとして、SICPのコードを改変し、Gauche特有の機能を使っている。
具体的にいうと、define-class,define-methodなどである。
これらを用いたことによるメリットは、cons,car,cdrなど、通常リストで用いるプロシージャで遅延リストを扱うことができるという、ただその1点にある。
- 加法の実行回数を得るための具体的手法
- add-streamsで用いる加法を通常の+ではなく、実行後とにnum-additionを1づつ更新してゆくaddプロシージャに変更した。fibを実行後num-additionを参照すれば、何度加法が呼び出されたのかわかる、という仕組みである。
#!/usr/bin/env gosh
(define-syntax delay
(syntax-rules ()
((delay exp ...)
(lambda () exp ...))))
(define (force delayed-object)
(delayed-object))
(define-class <Stream> ()
((head :init-keyword :head)
(tail :init-keyword :tail)))
(define-syntax cons
(syntax-rules ()
((cons a b)
(make <Stream> :head a :tail (delay b)))))
(define-method car ((s <Stream>))
(ref s 'head))
(define-method cdr ((s <Stream>))
(force (ref s 'tail)))
(define-method stream-ref ((s <Stream>)
(n <integer>))
(if (= n 0)
(car s)
(stream-ref (cdr s) (- n 1))))
(define (enumerate-interval low high)
(if (> low high)
'()
(cons low (enumerate-interval (+ low 1) high))))
(define-method map ((proc <procedure>)
(s1 <Stream>)
(s2 <Stream>))
(if (null? (car s1))
'()
(cons
(proc (car s1) (car s2))
(map proc (cdr s1) (cdr s2)))))
;;;;;;;;;;;;;;;;;ここらへんがキモ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define num-addition 0)
(define (add n m)
(begin
(set! num-addition (+ num-addition 1))
(+ n m)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define-method add-stream ((s1 <Stream>)
(s2 <Stream>))
(map add s1 s2))
(define fibs
(cons 0
(cons 1
(add-stream (cdr fibs) fibs))))
(define (how-many-addition n-th)
(let* ((result (stream-ref fibs n-th))
(num-add num-addition))
(set! num-addition 0)
num-add))
(define (print-amount n-th)
(print n-th " " (how-many-addition n-th)))
(use srfi-1)
(define init-commands (list
"unset border" ; 枠を表示しない
"set style data line"
"plot '-'"))
(for-each print init-commands)
(for-each print-amount (iota 20 1))
結果
#ref error :画像を取得できませんでした。しばらく時間を置いてから再度お試しください。
最終更新:2008年08月10日 17:13