青木日記

■ たらいまわしべんち

http://sheepman.parfait.ne.jp/20030418.html#p05

あ、sheepman さんのところに派生してる。

うーむ、おかしいなあ。 家だと lambda 使って遅延評価しても Hugs のほうが速いです。 GHC でコンパイルするとさらに激速。

~/c/test/haskell % cat lazy-tarai.rb
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{48}, lambda{24}, lambda{0})
　
~/c/test/haskell % cat tarai.hs
module Main where
　
main :: IO ()
main = do
          print (tarai 48 24 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)
　
　
~/c/test/haskell % time ruby lazy-tarai.rb
48
ruby lazy-tarai.rb  0.44s user 0.00s system 104% cpu 0.419 total
　
~/c/test/haskell % time runhugs tarai.hs
48
runhugs tarai.hs  0.07s user 0.00s system 148% cpu 0.047 total
　
~/c/test/haskell % ghc -O -o tarai tarai.hs
~/c/test/haskell % time ./tarai
48
./tarai  0.00s user 0.00s system 0% cpu 0.000 total

つーか、GHC は速すぎだなあ。 定数畳み込みされてるのかと思ったんですが、 引数を大きくすると実行時間も増えていくところからすると ちゃんと計算しているようです。

3/22 の原先生の返り値をキャッシュするバージョンでも、 引数を (96,48,0) にすると Hugs に負けます。

~/c/test/haskell % time ruby memo-tarai.rb
96
ruby memo-tarai.rb  0.40s user 0.00s system 101% cpu 0.394 total
　
~/c/test/haskell % time runhugs tarai.hs
96
runhugs tarai.hs  0.10s user 0.00s system 107% cpu 0.093 total

ようするに、こないだのでは引数が小さすぎると。

■ ruby-dev summary

改めて見ると今週はすごい流量が少ないな。 _vsnprintf の話は結局結論が出てないっぽいし、 bigdecimal 関係だけか。まあこういう週もあるやね。