OCaml と関数型プログラミングに慣れてきたでしょうか。ここでは コードをより高速にするために注意すべき点を幾つか挙げます。
私は末尾再帰じゃない再帰関数は極力 使用・作成しないようにしています。 でないと扱うデータがかなり大きいので、結局どこかで stack overflow を起してしまうからです。
まず再帰的な関数とは何だったかと言うと、 関数の中で、自分自身を呼び出しているような関数の事でした。末尾再帰な 関数呼び出しとはその中でも、自分自身を呼び出した結果がそのまま、関数の返り値に なるような再帰の仕方の事でした。
末尾再帰の何が嬉しいのでしょうか？末尾再帰で無い場合は、 自分自身を呼び出した後で、その結果が得られるまで、どこに 戻ってくるか等を覚えておき、結果を得られた後でなんらかの演算を行なって 最終的な結果を返す、と言う事が行なわれています。 しかし、末尾再帰な関数呼び出しの場合は自分自身を呼び出した結果がそのま ま最終的な結果になるので、戻ってくる必要が無く、場所等を覚えておく必要も無い、 と言う事にあります。 関数呼び出しは普通、どこに戻って来るかを覚えておくために stack を消費しますが、末尾再帰的な関数はコンパイラがそれを自動的に ループ (ジャンプ) に変換してくれるため、stack を消費しなくなります。
とても便利ですが気をつけないと 場合によってはかなり遅くなってしまうような、注意すべき関数を紹介します。
(@): 'a list -> 'a list -> 'a list)l1 @ l2 は List.append l1 l2と等価で、
二つのリスト l1 と l2 をつなぎあわせます。
でも、この関数を使うのは極力避けましょう (^^;。
理由は、末尾再帰でないので、長いリストに対して適用すると
stack overflow をおこしてしまうと言う事です。
これと似た関数: List.rev_append がありますが、できれば
こっちを使うようにしましょう。List.rev_append l1 l2 は
は、最初のリスト l1 を逆順にしたものが、二番目のリスト
l2 の前にくっついたような形になります。
List.append との違いは、末尾再帰な実装になった代償として、
リスト内の順番が変化してしまうと言う事です。
どちらの関数も基本的には l2 は変更せずに、その先頭に
l1 の要素を一つずつくっつける、と言う操作になるため、
l1の長さに比例する時間がかかる事になります。
と言う事で、二つのリストの、短かい方を最初の引数に持ってくるよう
に注意しましょう。
これは、次の文字列の結合と似たような理屈で、ループの中等で使う
場合に特に重要になってきます。
メイリングリストに流れましたが、
がんばれば末尾再帰な append が書けるらしいです。
OCaml に組込まれる日は来るのだろうか。
(^): string -> string -> string)
s1 ^ s2 で、文字列 s1 と s2
を結合して、新しい文字列を作る事ができます。
# "foo" ^ "bar";;
- : string = "foobar"OCaml でのメモリの確保はそれなりに速いそうですが いずれにせよ避けたほうが高速になるのは言うまでも無いでしょう。
例えば
Array.map g (Array.map f lst)lst の要素を二回変換したい時、
最初の fで変換した (Array.map f lst)
で新しく生成された array はもうガベコレ
されるのを待つだけです。と言うわけで、
Array.map (fun x -> g (f x)) lstlet f x =
let arr = [|0;1;2|] in
...のように書いた場合、この 配列 arr は関数 f
が呼ばれる度に生成されてしまいます。
配列ではなく、immutable なデータ構造を用いているのであれば、arr が以降
どこにあらわれようとも同じ値になるので、コンパイラが自動的に置き換える
事もできるのですが、
配列は mutable で、後で値が変えられてしまっている可能性がある
ために、最適化できません。毎回メモリ確保して欲しく無い場合は手動で
以下のように書換えましょう。
let arr = [|0;1;2|];;
let f x =
...# let f (x,y) = ... (* 定義 1 *)
# let f x y = ... (* 定義 2 *)
のどっちが良いのでしょう。前者は下手すると必要の無い tuple を生成してしまい、 後者は(関数の部分適用が無い場合)、下手すると必要の無い closure を作ってしまいます。 OCaml の byte code コンパイラは定義2 の方が最適化がかかり、効率が良いそうです。 native code コンパイラの場合はどちらも最適化されるようです。 というわけで迷ったら curry 化した方にしましょう。