「お気楽 OCaml プログラミング入門」に色んな言語のたらいまわし関数の結果が掲載されていて、OCamlがCよりも速い驚異的な数値を叩き出していました。
Haskell がありませんでしたので比較してみました。
- C
#include <stdio.h> int tak(int x, int y, int z){ if (x <= y){ return z; }else{ tak(tak((x - 1),y,z), tak((y - 1),z,x), tak((z - 1),x,y)); } } int main(void){ printf("%d\n",tak(18,9,0)); }
C は最適化により数値がかなり変わります。
$ time ./ctak 9 real 0m0.133s user 0m0.128s sys 0m0.004s $ gcc -O3 tak.c -o c03tak $ time ./c03tak 9 real 0m0.056s user 0m0.052s sys 0m0.004s
Haskell は正格評価をにすると1.6倍くらい速くなりました。
- 非正格
module Main where tak :: Int -> Int -> Int -> Int tak x y z = if x <= y then z else tak (tak (x - 1) y z) (tak (y - 1) z x) (tak (z - 1) x y) main :: IO() main = putStr $ show (tak 18 9 0) {- $ time ./htak 9 real 0m1.264s user 0m1.260s sys 0m0.004s $ ghc -O2 tak.hs -o htakO2 $ time ./htakO2 9 real 0m0.635s user 0m0.636s sys 0m0.000s -}
- 正格評価
module Main where tak :: Int -> Int -> Int -> Int tak x y z = if x <= y then z else takx `seq` taky `seq` takz `seq` tak takx taky takz where takx = newx `seq` (tak newx y z) taky = newy `seq` (tak newy z x) takz = newz `seq` (tak newz x y) newx = (x - 1) newy = (y - 1) newz = (z - 1) main :: IO() main = putStr $ show (tak 18 9 0) {- $ time ./htak2 9 real 0m0.767s user 0m0.760s sys 0m0.004s $ ghc -O2 htak2.hs -o htak2O2 $ time ./htak2O2 9 real 0m0.134s user 0m0.128s sys 0m0.004s -}
let rec tak x y z = if x <= y then z else tak (tak (x - 1) y z) (tak (y - 1) z x) (tak (z - 1) x y) let () = print_int (tak 18 9 0); (* $ ocamlc tak.ml -o octak # 最適化 # ocamlc.opt tak.ml -o camlc.opt.tak としても変わらない。 $ time ./octak 9 real 0m2.115s user 0m2.108s sys 0m0.004s $ ocamlopt tak.ml -o opttak # デフォルトではスピードに対して最適化している。 # ocamlopt.opt tak.ml -o ocamlopt.opt.tak としても変わらない。 $ time ./opttak 9 real 0m0.080s user 0m0.076s sys 0m0.004s *)
(define (tak x y z) (if (<= x y ) z (tak (tak (- x 1) y z) (tak (- y 1) z x) (tak (- z 1) x y)))) (print (tak 18 9 0))
$ gosh -V Gauche scheme interpreter, version 0.8.13 [utf-8,pthreads] $ time gosh tak.scm 9 real 0m1.668s user 0m1.660s sys 0m0.008s
def tak (x, y, z) if x <= y then z else tak(tak( (x - 1), y, z), tak( (y - 1), z, x), tak((z - 1), x, y)) end end print tak(18, 9, 0)
$ ruby1.9.1 -v ruby 1.9.1p378 (2010-01-10 revision 26273) [i486-linux] $ time ruby1.9.1 tak.rb 9 real 0m3.377s user 0m3.376s sys 0m0.004s $ ruby -v ruby 1.8.7 (2010-01-10 patchlevel 249) [i486-linux] $ time ruby tak.rb 9 real 0m25.074s user 0m21.201s sys 0m3.872s
| real | user | sys | |
|---|---|---|---|
| GCC 4.4.3(-O3) | 0m0.056s | 0m0.052s | 0m0.004s |
| ocamlopt 3.11.2 | 0m0.080s | 0m0.076s | 0m0.004s |
| GCC 4.4.3 | 0m0.133s | 0m0.128s | 0m0.004s |
| GHC6.12.1(正格・-O2) | 0m0.134s | 0m0.128s | 0m0.004s |
| GHC 6.12.1(-O2) | 0m0.635s | 0m0.636s | 0m0.000s |
| GHC6.12.1(正格) | 0m0.767s | 0m0.760s | 0m0.004s |
| GHC 6.12.1 | 0m1.264s | 0m1.260s | 0m0.004s |
| Gauche 0.8.13 | 0m1.668s | 0m1.660s | 0m0.008s |
| ocamlc 3.11.2 | 0m2.115s | 0m2.108s | 0m0.004s |
| ruby1.9.1 | 0m3.377s | 0m3.376s | 0m0.004s |
| ruby 1.8.7 | 0m25.074s | 0m21.201s | 0m3.872s |
- 最適化の有無、正格評価、非正格評価でかなり数値が変化するのがわかりました。
- 竹内関数(wikipedia):ここで用いられているのはジョン・マッカーシーが記憶違いで紹介したのが広まったバージョンのようです。
