scheme再帰と反復の効率テスト

テスト環境Petite Chez Scheme Version 8.4 Copyright(c)1985-2011 Cadence Research Systems
再帰バージョン

(define fib-0 (lambda (x)
	(cond ((= x 0) 0)
		((= x 1) 1)
		(else (+ (fib-0 (- x 2)) (fib-0 (- x 1)))))))

反復バージョン

(define fib-1 (lambda (n)
	(let ((i 1) (v0 1) (v1 0))
		(define func (lambda ()
			(let ((t 0))
				(cond ((= n 0) 0)
					((= n 1) 1)
					(else
						(if (< i n)
							(begin
								(set! t (+ v1 v0))
								(set! v1 v0)
								(set! v0 t)
								(set! i (+ i 1))
								(func))
							v0))))))
		(func))))

効率をテストしてみると、やはり少し驚きました.
>(time(fib-0 38))再帰バージョンは38までしかテストされず、時間がかかりました(time(fib-0 38))no collections 5157 ms elapsed cpu time 5149 ms elapsed real time 0 bytes allocated 3908169>(time(fib-1 38))テストの下で反復版本の38をテストしました.早すぎます.時間(time(fib-1 38))no collections 0 ms elapsed cpu time 0 ms elapsed real time 416 bytes allocated 3908169を知らない
> (time (fib-1 38000))
(time (fib-1 38000))     8 collections     78 ms elapsed cpu time, including 15 ms collecting     73 ms elapsed real time, including 29 ms collecting     66908400 bytes allocated, including 67848240 bytes reclaimed
結果が大きすぎて、ここに貼らなくなりました.割り当てられたバイト数を除いて、時間のみを見て、反復バージョンと再帰バージョンには万倍の差があります.
もう1つの例を見ると、n<3 f(n)=n n>=3 f(n)=f(n-1)+2 f(n-2)+3 f(n-3)
再帰バージョン

(define f0 (lambda (n)
	(cond ((< n 3) n)
		(else
			(+ (f0 (- n 1)) (* 2 (f0 (- n 2))) (* 3 (f0 (- n 3))))))))

反復バージョン

(define f1 (lambda (n)
	(let ((i 2)(v0 2)(v1 1)(v2 0))
		(define func (lambda ()
			(let ((t 0))
				(cond ((< n 3) n)
					(else
						(if (< i n)
							(begin
								(set! t (+ v0 (* 2 v1) (* 3 v2)))
								(set! v2 v1)
								(set! v1 v0)
								(set! v0 t)
								(set! i (+ i 1))
								(func))
							v0))))))
		(func))))

>(time(f 0 33))時間が長くなりました
(time (f0 33))
    224 collections
    14828 ms elapsed cpu time, including 15 ms collecting
    14863 ms elapsed real time, including 21 ms collecting
    1886422784 bytes allocated, including 1886521072 bytes reclaimed
821337484081
>(time(f 1 33))反復が速すぎて時間の消費が見えず、リソースの消費も少ない
(time (f1 33))
    no collections
    0 ms elapsed cpu time
    0 ms elapsed real time
    4496 bytes allocated
821337484081
>(time(f 1 33000))1000倍拡大してから見る
(time (f1 33000))
    40 collections
    235 ms elapsed cpu time, including 16 ms collecting
    238 ms elapsed real time, including 5 ms collecting
    345982400 bytes allocated, including 344358960 bytes reclaimed
差が少なくても万倍級の差です.