blogこの広告は、90日以上更新していないブログに表示しています。2015-12-22OCamlの末尾再帰についてこの記事はMLアドベントカレンダー22日目の記事です。プロローグautotakerはHaskellのList.sortが遅いので嘆いていた。あまりに遅いので簡単なコードを書いて実験することにした。1.063198s30万個の整数列をソートするのに900msもかかるのだ。比較のためにC++でもソートしてみた。22msreal0m0.151suser0m0.133ssys0m0.010sC++のstd::sortは爆速でわずか22msでソートが完了した。なんとHaskellのList.sortの40倍以上の速さである。これはいくらなんでも速すぎる。sortに毛が生えたようなアルゴリズムで実装されているらしい。アルゴリズムが違うならまあ仕方ない。ところで、標準ライブラリのソートにマージソートが採用されていてよくHaskellと比較される関数型言語があるではないか。OCamlコンパイラはGHCに比べてそれほどアグレッシブな最適化をするわけでもないし、さすがにOCamlよりは速いだろうと予想してコードを書いてみた。OCamlのソートのバグ?さて、ここまでが長い前振りで、ここから今回の本題に入ろう。次のようなOCamlのコードを書いて実験してみた。0.14416sreal0m0.874suser0m0.393ssys0m0.470s全体の実行時間が遅いのは主に入出力のせいなので気にしないこととして、OCamlのList.sortは144msであり、Haskellの6倍以上速い。これは意外な結果だったが、念のため出力があっているかを確認したときに興味深いことがわかった。-21472339237d31なんと正しくソートできていないではないか!この短く単純なコードのどこに私はバグを仕込んでしまったのだろう。入力を正しく読めているか確認した。0.14787sどうやらバグはread_intsにあるらしい。accこのコードを書いた時の私の気持ちはこうだ。入力はデカイので末尾再帰にする必要がある。アキュムレータ引数を用意しよう。read_intのドキュメントにはファイルの末尾に達したら、End_of_file例外が投げられるとかいてある。tryで包んで例外を捉えよう。例外の名前打ち込むの面倒だし、使い捨てのコードだから_でマッチさせてもいいよね!3つ目が私の怠慢であることは認めるが、上の二つは正しそうに思えないだろうか。私は自身の怠慢を認め、期待する例外の名前を正しく書くことにした。Stack_overflow!!!!!読者の中にはもう気づいた人もいるだろうが、実はこのread_intsは末尾再帰になっていないのだ。いうと、read_intsにはread_ints(v::acc)を呼び出したあとに例外処理のコードがあるので、例外をキャッチした時にどのハンドラに渡すかを保存するためにスタックが必要になるためだ。末尾再帰にするためには例外をoption型に変換してやらないといけない。accこのコードは多少不恰好だが、定数サイズのスタックしか消費しない。test300000.ansこうしてバグは修正された。後日談というか、今回のオチこうしてOCamlコードのバグは直ったわけだが、実験の結果、OCamlのList.sortは184msであり、やはりHaskellのList.sortがクソ遅いのはアルゴリズムのせいではなく、実装が悪いのだと考えられる。競技Haskellerとしてこんな状況は許されないのでメモリ効率が悪いListの代わりにVectorを使ってマージソートを実装した。0.367043sこのように198msと、OCamlと大差ない時間になった。17:09OCamlの末尾再帰についてTweet広告を非表示にする関連記事2016-05-30MacにZ3をインストールした。新しいMacを手に入れたので環境構築を行っている。Writeup月別アーカイブはてなブログをはじめよう!autotakerさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。