Y-Combinator
(define Y (lambda (f) ((lambda (proc) (f (lambda (x y z) ((proc proc) x y z)))) (lambda (proc) (f (lambda (x y z) ((proc proc) x y z))))))) (define Ytarai (lambda (f) (lambda (x y z) (if (<= x y) y (f (f (- x 1) y z) (f (- y 1) z x) (f (- z 1) x y)))))) (define tarai (lambda (x y z) (if (<= x y) y (tarai (tarai (- x 1) y z) (tarai (- y 1) z x) (tarai (- z 1) x y)))))
を実行してみる。環境はPenM上のcolinuxという遅々なもの。
| ＼ | (tarai 12 6 0) | ((Y Ytarai) 12 6 0) | Ytarai/tarai |
|---|---|---|---|
| stalin | 0.08 sec | 0.13 sec | 1.7 |
| gosh | 2.59 sec | 35.9 sec | 14 |
Ytarai/taraiの値に注目。Y-Combinatorの中まで解析していない(と思う)goshは14倍もの時間がかかっているが、中まで解析している(と思う)stalinは1.7倍の時間しかかかっていない。
〆。
14倍はちょっと辛いが、1.7倍くらいならハードウェアで埋められる。メモ化や何やらの都合を考えると常用してもよいかもしれないな。
