Hatena::ブログ(Diary)

[・ _ゝ・]日記を書くはやみずさん このページをアンテナに追加

インフォメーション

公開書架

読み終わったり、近いうちに読む予定がない本をいくつか。読みたい人には貸します。
神は沈黙せず〈上〉 神は沈黙せず〈下〉 Binary Hacks ―ハッカー秘伝のテクニック100選 Ruby on Rails入門―優しいRailsの育て方 The Art of Computer Programming Volume1 Fundamental Algorithms Third Edition 日本語版 プログラミングRuby 第2版 言語編 ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門 はじめて読む486―32ビットコンピュータをやさしく語る Subversion実践入門〓達人プログラマに学ぶバージョン管理 ハッカーと画家 コンピュータ時代の創造者たち

計算論の展開をSchemeで → インデックスページ
いっぱい本を読みたい→ 読書マラソン
ついったー → Twitter / hayamizu

2007-06-13

[] Lisp脳の弊害

OCaml関数に渡す引数をスペースで区切るので、関数引数関数戻り値を渡すときは、そいつを括弧で囲んでやらなきゃいけない。 funa (funb "hogehoge");; みたいに。

括弧あったりなかったり考えるのがめんどい→全部括弧つければいいんじゃね?→それ何てLisp

 破壊的変更?ボコボコにあqswでfrgtyふじこlp
    ∧_∧    ∧_∧
;;;;;、(;ω(:;(⊂=⊂(・ω・ )
    (っΣ⊂≡⊂=≡ ι)
   ./   )ババババ(   λ
   ( / ̄∪     ∪ ̄\)

2007-06-10

[] 引き続き最適化

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

[] 飯吹いた

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

  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回あたりメモリのアロケーションを少しでも減らせばそれなりに高速化できそうな気がする。

2007-06-09

[] 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ということですね。

2007-05-31

[] OCaml習作: マージソート

できた。

arrayでデータを受け取ってlistで返すという謎仕様なのは、データの列を分割するのはarrayのほうが簡単で、分割してソートした結果を組み立てていくのはlistのほうが簡単だったから。

open Array
open List

let rec mysort comp arr =
  match arr with
      [||] -> []
    | [|x|] -> [x]
    | [|x; y|] -> if (comp x y) then [x; y] else [y; x]
    | arr -> 
	let len = Array.length arr in
	let head = mysort comp (sub arr 0 (len / 2)) in
	let tail = mysort comp (sub arr (len / 2) (len - (len / 2))) in
	let rec merge_result ret ls1 ls2 =
	  match ls1, ls2 with
	      [], ls2 -> append (rev ret) ls2
	    | ls1, [] -> append (rev ret) ls1
	    | e1 :: es1, e2 :: es2 ->
		if (comp e1 e2) then
		  merge_result (e1 :: ret) es1 ls2
		else
		  merge_result (e2 :: ret) ls1 es2
	in
	  merge_result [] head tail;;

2007-05-30

[] OCamlをちょっとだけかじる

Schemeで好き勝手なことやってると、型推論みたいな制限がとても窮屈に感じる。多相型とか使えるようになれば違うのかな。