ブログトップ 記事一覧 ログイン 無料ブログ開設

おびなたん☆

1981 | 11 |
2004 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 11 | 12 |
2010 | 01 | 02 | 03 | 05 | 12 |
2011 | 02 | 03 | 05 | 07 |
2012 | 02 |
2013 | 02 | 04 | 05 | 06 |
2014 | 01 | 02 |
2015 | 12 |

May 12, 2006. Fri

[]コンパイラを使うチキン野郎

Schemeのコンパイラがあったので使ってみた。名前がなんとも憎らしい。

とりあえずベンチマークということで、たらい回し関数

;; tak.scm
(define (tak x y z)
  (if (<= x y) y
    (tak (tak (- x 1) y z)
         (tak (- y 1) z x)
         (tak (- z 1) x y))))

(tak 13 5 0)

これをインタプリタGauche)とコンパイラそれぞれで実行。

% time gosh tak.scm
19.050u 0.069s 0:20.49 93.2%    0+0k 0+4io 0pf+0w
% csc -O3 tak.scm
% time ./tak
16.663u 0.503s 0:18.30 93.7%    0+0k 0+2io 0pf+0w

あまり差がでないことに驚き。インタプリタの開始、終了のオーバーヘッドだってそれなりにあるだろうに。

ついでにC言語でもやってみる

/* tak.c */
int tak(int x, int y, int z) {
    return (x <= y)? y:
        tak(tak(x - 1, y, z),
            tak(y - 1, z, y),
            tak(z - 1, y, z));
}

int main() { return tak(13,5,0); }
% gcc -O3 tak.c
% ./a.out
Segmentation fault
0.011u 0.041s 0:00.36 13.8%     0+0k 0+0io 0pf+0w

Segmetation fault(たぶんスタックオーバーフロー)で即死。そういえば Mac OS X はスタックサイズが8192KBで固定だった。あとでFreeBSD上でやってみるか。

で、ここですごいのは、C言語で書かれたほぼプリミティブな要素しかないプログラムでさえスタックが溢れるほどの再帰の深さなのに、Schemeで書いた方はちゃんと完了しているということ。コンパイル後も遅延評価をはじめとした動的最適化がちゃんと行えているということか。そう考えると、むしろインタプリタの優秀さが目立ってくる。計算量は偉大なのだ。

"Chicken"という名には「インタプリタでも十分なのにわざわざコンパイラ使うやつはチキン野郎だ」といった意味も含まれているのかもしれない*1

追記(含訂正)

C言語版で、3つ目のtak関数呼び出しのパラメータの渡し方がおかしかった。なんとも初歩的な恥ずかしいミスである。

実行してみるとすんなりと終わった。ちうことで、上述の件は過大評価か。とりあえず、Schemeでコンパイラを使う奴がチキンなのは変わりなさそう。動的最適化の能力を得るにはもっと大きな数値をパラメータに与えてみないと結論は出ないかもしれないが、そこまで計算機をぶんまわす余裕は無し。

[]松井の怪我

ショック、松井秀喜外野手が試合中のプレーで左手首骨折で退場、日米通算での連続試合出場が1768で止まってしまった。これまで幾度かあった欠場の危機さえも驚異的な回復力、野球に対するモチベーションの高さで乗り越えてきただけに、こんな形で記録が途切れてしまったのは非常に残念。

左手首なので、完治してもバッティングにどれほど影響がでるか。いずれにせよ長期戦線離脱は間違いないわけで、一日も早く復帰してくることを願ってやまない。

*1FAQには名前の由来っぽいものは見当たらなかった