Scheme:たらいまわしべんち

Scheme:たらいまわしべんち


たらいまわし関数

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くらいにして評価してみる。

Haskell (hugs December 2001版)

あおきさんとこから。

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

Ruby (1.8.0-preview2)

同じく、あおきさんとこから。クロージャ使って遅延評価

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

実はこれでもまだ完全に遅延評価と等価ではなくて、 引数として渡されたクロージャが何度も繰り返し呼ばれてしまうから、 まだかなり無駄なことをやっていることになる。

ほんとに遅延評価と同等の計算量にするには、メモワイズでしか 対抗できないかも。

Gauche (0.6.8)

クロージャ版

(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

delay/force版

(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)

zだけ遅延評価させるという技(裏技)?

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


Last modified : 2014/05/12 16:41:53 UTC