Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

たらい回し関数

Haskell Ruby Gauche

「たらいを回すならHaskell」を読みました。たらい回し関数(竹内関数)を，Perl, Ruby, Python, C言語, Haskellで作って，実行速度を比較しています。言語によって，これほど性能差があるというのは驚きでした。Haskellがこんなに早いのは，遅延評価という仕掛けがあるからのようです。

いろいろな言語で作られているのですが，Scheme(Gauche)だったらどうなんだろうと思い，作ってみました。また，自分のPCで速度比較を行ってみたかったので，Haskell, Ruby版も実験してみました。

tarai.scm(Gauche版)

#!/usr/bin/env gosh

(define (tarai x y z)
  (if (<= x y)
      y
      (tarai (tarai (- x 1) y z)
             (tarai (- y 1) z x)
             (tarai (- z 1) x y))))

(define (main args)
  (print (tarai 100 50 0))
  0)

実行してみたのですが，結果が帰ってくるまでに相当時間がかかるので，Ctrl+c。
以前，『プログラミングGauche』を読んだときに，Gaucheにもutil.streamライブラリで遅延評価を実現しているということを覚えていたので，何とか，遅延評価を使って高速化できないかと試行錯誤したのですが，作ることができず，よくよく調べてみると，dankogaiさんが「λ萌え - たらいを後回し」で解説されていました(感謝)。lambdaでくくる方法は難しくて理解できなかったのですが，組み込みのforceとdelayを使う方法は何とか理解できたような気がします。

tarai_lazy.scm(Gauche版 -- 遅延評価)

#!/usr/bin/env gosh

(define (ltarai x y z)
  (if (<= (force x) (force y))
      (force y)
      (ltarai (delay (ltarai (delay (- (force x) 1)) y z))
              (delay (ltarai (delay (- (force y) 1)) z x))
              (delay (ltarai (delay (- (force z) 1)) x y)))))

(define (tarai x y z)
  (ltarai (delay x)
          (delay y)
          (delay z)))
  
(define (main args)
  (print (tarai 100 50 0))
  0)

tarai.hs(Haskell版)

main = print (tarai 100 50 0)

tarai :: Int -> Int -> Int -> Int
tarai x y z = if x <= y then y
                        else tarai (tarai (x-1) y z)
                                   (tarai (y-1) z x)
                                   (tarai (z-1) x y)

tarai.rb(Ruby版)

#!/usr/bin/env ruby

def tarai(x, y, z)
  if x <= y
    y
  else
    tarai(tarai(x-1, y, z),
          tarai(y-1, z, x),
          tarai(z-1, x, y))
  end
end

puts tarai(100, 50, 0)

tarai_memo.rb(Ruby版 -- メモ化)

たらい回し関数を高速化するには，遅延評価の他に「メモ化」という手法があるそうです。以下は，ハッシュを使って，一度計算した結果を覚えておき，次の呼び出しで活用します。

#!/usr/bin/env ruby

$tak = {}
def tarai(x, y, z)
  $tak[x]    ||= {}
  $tak[x][y] ||= {}
  return $tak[x][y][z] if $tak[x][y].member?(z)
  $tak[x][y][z] =
  if x <= y
    y
  else
    tarai(tarai(x-1, y, z),
          tarai(y-1, z, x),
          tarai(z-1, x, y))
  end
end

puts tarai(100, 50, 0)

実行結果

MacBook(Mac OS X, 2.4GHz Intel Core 2 Duo, 2GBメモリ)で試してみました。

遅すぎて計測できず…。

  • tarai_lazy.scm(Gauche版 -- 遅延評価)

$ time ./tarai_lazy.scm
100

real 0m0.023s
user 0m0.018s
sys 0m0.005s

$ time runhaskell tarai.hs
100

real 0m0.132s
user 0m0.098s
sys 0m0.030s

ghcでコンパイルすると…，

$ ghc tarai.hs -o tarai_haskell
$ time ./tarai_haskell
100

real 0m0.004s
user 0m0.001s
sys 0m0.003s

遅すぎて計測できず…。

  • tarai_memo.rb(Ruby版 -- メモ化)

$ time ./tarai_memo.rb
100

real 0m0.090s
user 0m0.083s
sys 0m0.005s

まとめ

実行速度は以下の順でした。

  1. Haskell(コンパイル版) … 0.004s
  2. Gauche(遅延評価) … 0.023s
  3. Ruby(メモ化) … 0.090s
  4. Haskell(インタプリタ) … 0.132s
  5. RubyとGaucheの普通の再帰は遅すぎたので，途中でCtrl+c

感想

Haskellの特長の一つに遅延評価というのがあげられるそうです。そのため，Haskellでは高速に実行できました。Scheme(Gauche), Ruby版でも，メモ化という手法を用いることにより，相当な高速化が図れることが分かりました。今回，Haskellを勉強しようということがきっかけとなって，たらい回し関数(竹内関数)の存在を知り，遅延評価，メモ化という手法に興味を持つことができました。いろんな言語を勉強することの重要性を実感しました。

関連