tarai(x, y, z) :=
y if x <= y
tarai(tarai(x-1, y, z),
tarai(y-1, z, x),
tarai(z-1, x, y)) otherwise
eagerに評価すると、不要な枝の先の先まで計算してしまって大いなる無駄となる。 lazy evaluationの利点が光る一品である。
参考：
引数が小さいとインタプリタの起動時間なんだか計算時間なんだかわからないので、 初期値を192, 96, 0くらいにして評価してみる。
あおきさんとこから。
main :: IO ()
main = print (tarai 192 96 0)
tarai :: Int -> Int -> Int -> Int
tarai x y z
| x <= y = y
| otherwise = tarai (tarai (x-1) y z)
(tarai (y-1) z x)
(tarai (z-1) x y)
% time runhugs tarai.hs 192 0.810u 0.020s 0:00.85 97.6% 0+0k 0+0io 264pf+0w
同じく、あおきさんとこから。クロージャ使って遅延評価
def tarai( x, y, z )
if x.call <= y.call
then y.call
else tarai(lambda { tarai(lambda{x.call-1}, y, z) },
lambda { tarai(lambda{y.call-1}, z, x) },
lambda { tarai(lambda{z.call-1}, x, y) })
end
end
puts tarai(lambda{192}, lambda{96}, lambda{0})
% time ruby tarai.rb 192 120.980u 1.660s 2:03.09 99.6% 0+0k 0+0io 221pf+0w
考えてみたら、単にlambda使うだけだと、計算オーダーはまだ lazyな評価と同程度までは下がらない気がする。 例えばxに注目すると、x.callの度に xの計算に必要なクロージャの木がばーっと評価される。 eagerな評価に比べたらzの枝の評価は刈り込まれているけれども、 このクロージャの重複評価はばかにならない。
一方、本当の遅延評価では、xの値は必要になった時に一度だけ計算される はずだ。こうすれば多少は遅延評価の動作に近付く。
def tarai( x, y, z )
xval = x.call
yval = y.call
if xval <= yval
then yval
else tarai(lambda { tarai(lambda{xval-1}, y, z) },
lambda { tarai(lambda{yval-1}, z, x) },
lambda { tarai(lambda{z.call-1}, x, y) })
end
end
% time ruby tarai.rb 192 34.380u 0.430s 0:35.59 97.8% 0+0k 0+0io 221pf+0w
実はこれでもまだ完全に遅延評価と等価ではなくて、 引数として渡されたクロージャが何度も繰り返し呼ばれてしまうから、 まだかなり無駄なことをやっていることになる。
ほんとに遅延評価と同等の計算量にするには、メモワイズでしか 対抗できないかも。
(define (tarai x y z)
(if (<= (x) (y))
(y)
(tarai (lambda () (tarai (lambda () (- (x) 1)) y z))
(lambda () (tarai (lambda () (- (y) 1)) z x))
(lambda () (tarai (lambda () (- (z) 1)) x y)))))
(print (tarai (lambda () 192) (lambda () 96) (lambda () 0)))
% time gosh tarai-clo.scm 192 2.350u 0.040s 0:02.40 99.5% 0+0k 0+0io 282pf+0w
(define (tarai x y z)
(if (<= (force x) (force y))
(force y)
(tarai (delay (tarai (- (force x) 1) y z))
(delay (tarai (- (force y) 1) z x))
(delay (tarai (- (force z) 1) x y)))))
(print (tarai 192 96 0))
% time gosh tarai-delay.scm 192 0.270u 0.010s 0:00.30 93.3% 0+0k 0+0io 282pf+0w
となる。Delay/force版は完全な遅延評価になっている。 やはりクロージャでは計算量が遅延評価ほど減らせないことがわかる。
ちなみにGaucheにはないのだけど、implicit forceという機能を備えている Scheme処理系では、プリミティブにpromiseが渡されると処理系が勝手に forceしてくれるので、上のプログラムはこう書ける、はず。
;;; Gaucheでは動かない
(define (tarai x y z)
(if (<= x y)
(force y)
(tarai (delay (tarai (- x 1) y z))
(delay (tarai (- y 1) z x))
(delay (tarai (- z 1) x y)))))
やっぱりimplicit forceつけようかなあ。
クロージャが何度も呼ばれる、というのは、クロージャ自身にカウンタをつけて 表示してみればわかる。
(define lambda-counter 0)
(define-syntax count-lambda
(syntax-rules ()
((_ formals . body)
(let ((cnt 1)
(id lambda-counter))
(inc! lambda-counter)
(lambda formals
(when (> cnt 1)
(format #t "closure#~a ~atimes body=~s?n" id cnt (car 'body)))
(inc! cnt)
(let () . body))))
))
(define (tarai x y z)
(if (<= (x) (y))
(y)
(tarai (count-lambda () (tarai (count-lambda () (- (x) 1)) y z))
(count-lambda () (tarai (count-lambda () (- (y) 1)) z x))
(count-lambda () (tarai (count-lambda () (- (z) 1)) x y)))))
これで、例えば
(tarai (count-lambda () 12) (count-lambda () 6) (count-lambda () 0))
と呼び出してみると、同じ計算を何度も何度もしていることがわかる。
ちょっと変形して、関数内では一度しかクロージャを評価しないようにしてみると：
(define (tarai* x y z)
(let ((x0 (x)) (y0 (y)))
(if (<= x0 y0)
y0
(tarai* (count-lambda () (tarai* (count-lambda () (- x0 1)) y z))
(count-lambda () (tarai* (count-lambda () (- y0 1)) z x))
(count-lambda () (tarai* (count-lambda () (- (z) 1)) x y))))))
確かにこれでもクロージャは何度も呼ばれるのだが、 クロージャのボディは定数時間で済む処理なので、 計算量のオーダーとしては遅延評価と同等になる、でいいのかな。
memoise しても、z を strict に評価することになるので、遅延評価ほどは速くなりません。 やっぱり、Gauche に lazy をいれる鹿 :-) nobsun(2003/04/20 17:29:51 PDT)
Ruby 版には x と y が残っているので、lambda{xval} と lambda{yval} に置き換えた。(藤井)
def tarai( x, y, z )
xval = x.call
yval = y.call
if xval <= yval
then yval
else tarai(lambda { tarai(lambda{xval-1}, lambda{yval}, z) },
lambda { tarai(lambda{yval-1}, z, lambda{xval}) },
lambda { tarai(lambda{z.call-1}, lambda{xval}, lambda{y}) })
end
end
Tags: たらいまわし関数, 竹内関数, Haskell, Ruby