末尾再帰による最適化の効果
Schemeで簡単なべき乗関数を書いて、末尾再帰の効果を実感してみる。Schemeの処理系にはGaucheを使う。
Schemeとは？末尾再帰とは？
Schemeは関数型プログラミング言語LISPの方言の一つ。
末尾再帰は、関数末尾での再帰呼び出しの事。最適化により単純なループに展開できるため実行速度が上がる。
詳細はWikipediaで。
Scheme
末尾再帰
方法
以下の2種類の関数をそれぞれ5回実行して、その平均処理時間を比較する。
(define (pow x n) (if (= n 0) 1 (* x (pow x (- n 1)))))
- 末尾再帰でのべき乗関数pow-t
(define (pow-t x n) (letrec ((iter (lambda (m p) (if (= m 0) p (iter (- m 1) (* p x)))))) (iter n 1)))
結果
それぞれの関数で3^100000を計算させ、処理時間をtimeコマンドで測る。これを5回行い、その平均処理時間を次の表にまとめた。
| 平均処理時間（秒） | |
|---|---|
| pow（通常の再帰） | 7.72 |
| pow-t（末尾再帰） | 6.20 |
末尾再帰の方が1.5秒ほど平均処理時間が短い結果となった。性能は約1.2倍になった事がわかる。確かに末尾再帰の効果はあった。面白かった。
余談 - 大きな数値をdisplay関数で表示する事とか
最初は計算結果をdisplay関数で出力してた。その場合、末尾再帰のプログラムは8.46秒かかっていた。
つまりdisplay関数でで2.2秒ほどかかっている事になる。原因は、数値の内部表現(多倍長整数)から10進表記への変換だろう。0.7倍程度にまで落ち込むとは…。
あと、このプログラムは実行可能なGaucheスクリプトとして作った。そこで便利な様にコマンドライン引数を解析する関数を作った。Gauche勉強中だもんで、ここが一番楽しかった。かなり拙いスクリプトだろうけど晒しておこう。
#!/usr/bin/env gosh ; 通常の再帰のべき乗 (define (pow x n) (if (= n 0) 1 (* x (pow x (- n 1))))) ; 末尾再帰のべき乗 (define (pow-t x n) (letrec ((iter (lambda (m p) (if (= m 0) p (iter (- m 1) (* p x)))))) (iter n 1))) ; べき乗の底xおよび指数nを取得 ; コマンドライン引数リストを渡すと、xとnを多値で返す。xおよびnに妥当な数字が無ければ#fとする。 (define (get-x-n args) (let loop ((ls args)) (if (null? ls) #f (let ((x (string->number (car ls)))) (if x (values x (get-x-n (cdr ls))) (get-x-n (cdr ls))))))) ; コマンドライン引数からオプションの文字を取得(ハイフンと1文字で表されるあれ) ; コマンドライン引数リストを渡すと、最初に見つかったオプション"-?"の文字?のを返す。 (define (get-sw args) (let sw-parse ((ls args)) (if (null? ls) #f (let ((sw (car ls))) (if (char=? #\- (string-ref sw 0)) (string-ref sw 1) (sw-parse (cdr ls))))))) ; main関数 (define (main args) (receive (x n) (get-x-n args) (if (and x n) ((let ((sw (get-sw args))) (cond ((eq? #f sw) pow) ((char=? #\t sw) pow-t) (else pow))) x n))))
