新春芸はたらいまわし？

新年明けてからも、common lispで遊び倒すとか、なにしてるんでしょうか。*1
taraiまわしなどですよね。

lisp と c と haskell でたらい回ししてみた。ただの練習です。

common lisp(型指定なし)

ただし、型を指定していない。型を指定していないから、関数呼び出し時に型チェックを行っているはず。つまり型を指定したら早くなるはずなので、後でしてみよう。

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

;; Driver
(tarai 20 10 5)
(quit)

これをeclでコンパイルして、

(compile-file "tarai.lisp" :system^p t) ;;-> #P"/path/to/tarai.o" NIL NIL

OPTIMIZE letevs: Safety=2 Space=0 Speed=3 Debug=0で、tarai.cが作成されているようです。で、こんな外部コマンドだそうです。

/usr/bin/gcc-4.2 -I. -I/opt/local/include/ -I/opt/local/include -pipe -O2 -arch x86_64 -fPIC -fno-common -Ddarwin -O2 -w -c tarai.c -o tarai.o 

さらに実行ファイル作成と。

(c:build-program "tarai.lisp.x" :lisp-files '("tarai.o")) ; -> #P"tarai.lisp"

あれれ、#P"tarai.lisp.x"のはずが、#P"tarai.lisp"になってソースコードが上書きされてしまいました！！

pure c

これはただの cで普通に書くと型を指定することになる。

#include <stdio.h>
int tarai (int x, int y, int z){
	int res;
	if (x <= y){
		res=y;
	}
	else{
       		res=tarai(tarai((x-1), y, z), 
		          tarai((y-1), z, x), 
	                  tarai((z-1), x, y));
	}
	return(res);
}
/* Driver */
int main(void){
	int res;
	res = tarai (20, 10, 5);
        printf("%d", res);
	return(0);
	}

コンパイラは、gccとclangでそれぞれ最速をしてみる。

haskell

宇宙人語といわれるhaskellは遅延評価のためアホみたいに早いという。

-- Driver
main = print (tarai 20 10 5)

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)

score

とりあえず表にしてみた。全部timeで出している。
Macは 10.6.8/2Ghz Intel Core 2 Duoである。

term	lisp(ecl)	c(apple gcc)	c(clang最速)	c(gcc最速)	haskell
real	1m21.615s	0m39.786s	0m15.805s	0m15.140s	0m0.099s
user	1m21.172s	0m89.315s	0m15.705s	0m14.721s	0m0.001s
sys	0m 0.086s	0m 0.036s	0m 0.012s	0m 0.005s	0m0.004s

><

*1:はやくも年賀状から戦線離脱ですよ！