「最も簡単に fib を高速化する方法」を試してみた。

どうしてこれで速くなるの？

• 最も簡単に fib を高速化する方法 - ドレッシングのような

二つ値を返せば良いんですよ。メモ化なんてしなくていい。

取りあえず Scheme の多値でやってみました。速い。。どうして？

	;; http://d.hatena.ne.jp/mrkn/20100906/easy_faster_fib
	(define (fib-i n)
	(if (or (zero? n)(= n 1))
	(values 1 1)
	(receive (cur prev)
	(fib-i (- n 1))
	(values (+ cur prev) cur))))
	(fib-i 10)
	;; 89
	;; 55
	(time (fib-i 10000))
	;(time (fib-i 10000))
	; real 0.094
	; user 0.047
	; sys 0.047

view raw fib-i.scm hosted with ❤ by GitHub

あとはまぁ、取りあえず参考までに。

メモ化。昨日のメモ化マクロを使ってみました。

• vallog: PAIP: メモ化, memo, memoize, define-memo

	;; memoize
	;; http://valvallow.blogspot.com/2010/09/paip-memo-memoize-define-memo.html
	(define-memo (fib-m n)
	(if (or (zero? n)
	(= n 1))
	1
	(+ (fib-m (- n 1))
	(fib-m (- n 2)))))
	(fib-m 10)
	;; 89
	(time (fib-m 10000))
	;(time (fib-m 10000))
	; real 0.125
	; user 0.125
	; sys 0.000

view raw fib-m.scm hosted with ❤ by GitHub

遅延ストリーム。

• vallog: fib, tail-call-fib, lazy-fib

	;; stream
	;; http://valvallow.blogspot.com/2010/06/fib-tail-call-fib-lazy-fib.html
	(use util.stream)
	(define fib-s (stream-cons 1 (stream-cons 1 (stream-map + fib-s (stream-cdr fib-s)))))
	(stream-ref fib-s 10)
	;; 89
	(time (stream-ref fib-s 10000))
	;(time (stream-ref fib-s 10000))
	; real 0.172
	; user 0.157
	; sys 0.016

view raw fib-s.scm hosted with ❤ by GitHub

末尾再帰。ようはループですわな。

• vallog: fib, tail-call-fib, lazy-fib

	;; tail call
	;; http://valvallow.blogspot.com/2010/06/fib-tail-call-fib-lazy-fib.html
	(define (fib-t n)
	(let rec ((cur 1)(next 2)(n n))
	(if (or (zero? n)
	(= n 1))
	cur
	(rec next (+ cur next)(- n 1)))))
	(fib-t 10)
	;; 89
	(time (fib-t 10000))
	;(time (fib-t 10000))
	; real 0.109
	; user 0.047
	; sys 0.047

view raw fib-t.scm hosted with ❤ by GitHub

普通の再帰。これは 10000 なんてとても試す気になれませんね。。

	;; normal
	(define (fib n)
	(if (or (zero? n)
	(= n 1))
	1
	(+ (fib (- n 1))
	(fib (- n 2)))))
	(fib 10)
	;; 89
	(time (fib 35))
	;(time (fib 35))
	; real 2.094
	; user 2.078
	; sys 0.000
	;; (time (fib 10000))
	;; ...

view raw fib.scm hosted with ❤ by GitHub

fib-i なぞ・・・。

追記

わかりました！というか教えて頂きました。末尾再帰の例と同じような計算の仕方だからですね。
末尾再帰ではないし、末尾再帰のようにその都度計算を行うのではなく再帰を戻りながら最後にまとめて計算する点は違えども、計算量は末尾再帰の例と同じということですよね。
というか、末尾再帰とか多値とかそういう話じゃないわけですね。。なんか、すいません。

• フィボナッチ関数の計算量 - 主題のない日記

ありがとうございました！

• Twitter / SaitoAtsushi: @valvallow フィボナッチ関数の計算量につい ...

追記2

• Twitter / SaitoAtsushi: @valvallow フィボナッチ数の計算は行列のべ ...

爆速過ぎﾜﾛﾀ

	(define (fib-l n)
	(let rec ((a 1)(b 1)(p 0)(q 1)(count n))
	(cond ((= count 0) b)
	((even? count)
	(rec a
	b
	(+ (* p p) (* q q))
	(+ (* 2 p q) (* q q))
	(/ count 2)))
	(else (rec (+ (* b q) (* a q) (* a p))
	(+ (* b p) (* a q))
	p
	q
	(- count 1))))))
	(time (fib-l 10000))
	;(time (fib-l 10000))
	; real 0.000
	; user 0.000
	; sys 0.000
	(time (fib-l 100000))
	;(time (fib-l 100000))
	; real 0.203
	; user 0.203
	; sys 0.000

view raw fib-l.scm hosted with ❤ by GitHub

• SICP 問題 1.19 （逐次平方変換を利用したFibonacci数を求める末尾再帰処理） - awacio.log