プログラミングGauche p.226 ストリームによるフィボナッチ数列の速さ

ストリームは遅延評価されるリスト。遅延評価も興味あるけど、この本「プログラミングGauche」では、索引を見る限り、ここでしか遅延評価の話は出てこないようだ。

さて、ストリームによるフィボナッチ数列が出てきた。フィボナッチ数列のN番目の数を得る計算について、他の手法との計算速度の比較をしてみる。まずはそれぞれの手法の定義から。

1. 
   この本に載っていたストリームによるフィボナッチ数列の定義。

   (define fib (stream-cons 0 (stream-cons 1 (stream-map + fib (stream-cdr fib)))))
   



2. 
   フィボナッチ数列のN番目の数を得る素朴な手続きの定義。

   (define (fib-n n)
     (cond [(<= n 1) n]
           [else (+ (fib-n (- n 1)) (fib-n (- n 2)))]))
   



3. 
   フィボナッチ数列のN番目の数を得る素朴な手続きの定義。ただし末尾再帰。

   (define (fib-t n)
     (letrec ((iter (lambda (i x y)
                      (cond [(= i n) x]
                            [else (iter (+ i 1) y (+ x y))]))))
       (iter 0 0 1)))
   

この3つをtimeマクロで比較する。2.の手法は遅すぎるので序数Nを、小さめの35とした。他の手法の序数Nは90000とする。（速度差が顕著になるようにわざとこういう値をとった）
CPUはCore2Duo E7400。

gosh> ;(time (stream-ref fib 90000))
; real   7.395
; user   0.445
; sys    2.320
#f
gosh> ;(time (fib-n 35))
; real   2.126
; user   2.109
; sys    0.000
#f
gosh> ;(time (fib-t 90000))
; real   2.735
; user   0.883
; sys    0.250
#f

圧倒的だな、末尾再帰は。計算速度だけ見れば末尾再帰は最良なのかも。
ここには載せてないけど、他の序数でも試してみた。ストリーム版も序数が小さいうちは、末尾再帰版とほぼ同じ速さだった。けど、序数を大きくすると急に遅くなった。
実行時間中の、userとsysの分配にも結構な違いが現れてる。ストリーム版はuserが小さくて、sysが大きい。遅延評価はシステムコールに使う時間が長いのかな。