飯吹いた

オレオレマージソートの一部

  let rec merge_two ls1 ls2 ret =
    match ls1, ls2 with
      | x1 :: xs1, x2 :: xs2 ->
	  if (comp x1 x2) then
	    merge_two xs1 ls2 (x1 :: ret)
	  else
	    merge_two ls1 xs2 (x2 :: ret)
      | ls1, [] -> rev_append ls1 ret
      |	[], ls2 -> rev_append ls2 ret in
  let rec merge_two_rev ls1 ls2 ret =
    match ls1, ls2 with
      | x1 :: xs1, x2 :: xs2 ->
	  if (comp x2 x1) then
	    merge_two_rev xs1 ls2 (x1 :: ret)
	  else
	    merge_two_rev ls1 xs2 (x2 :: ret)
      | ls1, [] -> rev_append ls1 ret
      |	[], ls2 -> rev_append ls2 ret in

標準ライブラリの(マージ)ソートの一部

  let rec rev_merge l1 l2 accu =
    match l1, l2 with
    | [], l2 -> rev_append l2 accu
    | l1, [] -> rev_append l1 accu
    | h1::t1, h2::t2 ->
        if cmp h1 h2 <= 0
        then rev_merge t1 l2 (h1::accu)
        else rev_merge l1 t2 (h2::accu)
  in
  let rec rev_merge_rev l1 l2 accu =
    match l1, l2 with
    | [], l2 -> rev_append l2 accu
    | l1, [] -> rev_append l1 accu
    | h1::t1, h2::t2 ->
        if cmp h1 h2 > 0
        then rev_merge_rev t1 l2 (h1::accu)
        else rev_merge_rev l1 t2 (h2::accu)
  in

なんかまる写ししたみたいだ。

ちょっとだけ最適化

OCamlでひきつづきソーティング。camloptに-pオプションをつけるとgprofでネイティブコードのプロファイリングができるので試してみたら、全体の40%の時間がGC関係のコードに使われていた。リストをガンガン組み換えていく作業が、かなりのゴミを発生させている模様。こういう関数型的なメモリをじゃぶじゃぶ使ってゴミ捨て、みたいなのはやっぱり富豪的で、大量のデータのソーティングには不利に働く。

関数呼出し1回あたりメモリのアロケーションを少しでも減らせばそれなりに高速化できそうな気がする。

引き続き最適化

String.compare と = だとString.compareのほうが遅いので、同じ値が多い場合は = で比較してからcompareするようにしたら早くなるかな、と思ってコードを書く。すると早くなった!しかし、よくコードを見ていると意図しているアルゴリズムとは別のアルゴリズムを間違って実装していた。そこで意図しているアルゴリズムに改めて書き直したら遅くなった(´_`;) 間違ったほうの実装でどうして早くなるのかが全く謎。

OCamlの罠

ソフトウェアの授業の課題のソーティングプログラムをOCamlで書き始めてから、度重なるStack overflowに悩むこと1週間。ファイル読み込み時のstack overflowは普通に末尾再帰に書き直してうまくいったけど、2つのリストをマージする関数に2,000,000要素くらいのリストを渡すとどうやってもstack overflowになってしまう。末尾再帰の書き方を変えてもダメ。なんなんだー!と思ってocamloptでネイティブコンパイルしてobjdumpして自分自身をcallしていないか探すが見つからず。ふとcamlList__appendに目が停まる。というのも、"OCaml 末尾再帰"でググったときに"...するとなんとかして末尾再帰なappendが書ける..."みたいな文章を目にしていたから。これはもしや、と思ってOCamlのマニュアル読んだら案の定appendは末尾再帰じゃなかった\(^O^)/結果返すときにappend使ってるから確実にstack overflowするようになってます本当に(ry

List.rev_append使ったら普通にStack overflowの問題解決。大きなデータのソーティングみたいなある種の極限状態では、組み込み関数を疑うことも重要ってことか。要はRead the F**king Manualということですね。