Exercise 3.57における実験について

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 :画像を取得できませんでした。しばらく時間を置いてから再度お試しください。

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2008年08月10日 17:13
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。