パワポに貼る用の数式画像の生成
スライド作成は一時期beamerを使っていたものの面倒になってPowerPointに戻ってきている。Office2007の数式エディタはしょぼいのでdvipngを使う。具体的には次のようなシェルスクリプトとMakefileで複数の数式ファイルを管理。(Officeを2010にする以外にも)もっとマシな方法がある気がする。
#!/bin/bash tmp=`mktemp XXXXX` echo -e "\documentclass{jarticle}\\n\usepackage{amsmath,amssymb}\\n\pagestyle{empty}\\n\\\begin{document}" | cat - $1 > $tmp echo -e "\\n\\\end{document}" >> $tmp platex $tmp out=`echo $1 | sed -e s/\\\..*/\\\.png/` dvipng ./${tmp}.dvi -T tight -o $out -D 300 -bd 1000 rm $tmp ${tmp}.* exit 0
GCJJ2011予選参加
- 参加id：LennMars
- 結果：Aで暗算間違えてLarge突っ込んで時間切れ、合計41点。時間あったのにアホですね……
- 感想：これまでGCJにはOCamlで参加していたのだけどこの手のプログラミングコンテストに関してOCaml(特に32bit環境)は余りにもないということに気付いて1週間前に始めたScalaでやったらえらいやりやすくて感動しました。
ant/Scalaのエラーメッセージをflymakeが正しくパースしてくれない問題
具体的には行数のマッチに失敗して1行目しか赤くしてくれない。これでは使えない(そもそもScalaのコンパイル速度が遅くてロクに使えないことは一旦忘れる)。
そもそもflymakeがエラーメッセージのパースに何を使用しているかというと、正規表現をキー、そのsubexpressionsのうち何番目がファイル名やエラー行数に対応しているかを示すリストを値としたalistである。これはcompilation-error-regexp-alistで定義され、flymake.el中で多少拡張して用いられている(flymake-err-line-patterns)。
今回問題を引き起こしていたのはflymake.el側で定義されたant/Java用の
(" *\\(\\[javac\\]\\)? *\\(\\([a-zA-Z]:\\)?[^:(\t\n]+\\)\:\\([0-9]+\\)\:[ \t\n]*\\(.+\\)" 2 4 nil 5)
であった。Scalaのコンパイルエラーメッセージにコロンが入っている事が原因ぽい。最初の?を削除して上書きし、Scala用のやつを新しく付け足し。ついでにcompilation-error-regexp-alistの先頭の
("\\([a-zA-Z][-a-zA-Z._0-9]+: ?\\)?\\([a-zA-Z]?:?[^:( \n]*[^:( \n0-9][^:( \n]*\\)[:(][ ]*\\([0-9]+\\)\\([) ]\\|:\\(\\([0-9]+:\\)\\|[0-9]*[^:0-9]\\)\\)" 2 3 6)
も一般的過ぎて余計なものにまでマッチするのでコメントアウトした。
DevQuiz2011 スライドパズル
- 結果:3723問
- 言語:OCaml
- ソース:https://github.com/LennMars/DevQuiz2011
- 方針:
- 普通のA*(評価関数はマンハッタン距離 + 2 * Linear Conflict)
- といってもこれで素直に解けるのは4*4の一部までだろう⇒早速完答を諦め、2段階に分けて解くことにする
- 1段階目で正しい位置に持っていきたいピース以外をマスクし、マスクされたピースについては評価関数に加算しないようにしてA*を実行
- 1段階目が終了したらマスクを外してそこから再度A*を実行
- マスクのいい決め方は思いつかなかったので盤面の角に接する直方領域を総当たり的に生成して袋小路を埋める感じにした(平均80パターンくらい)。
- 1つのマスクにつき、訪問済み盤面が一定数を越えたら強制終了(一定数=だいたい1000くらい)
- 勉強だと思って優先度つきキューとそれを実現するための可変長配列もどき(OCamlの配列サイズ制限に対応するため2次元配列で実装)も自前実装した
- 短い解が得られた問題から順に手数制限に突き当たるまで選択して回答とする
- この段階で冗長な手を短縮しようとした努力の結果がshortenディレクトリに入っている
- 3672問→3723問と一応マシになってはいるが……
- 結果:
- 反省:
- 反復深化を使うべきだったかも
- せめてマスク生成をもう少し賢くするとか最大訪問済み盤面数を盤面サイズによって変えるとか……
- 今気付いたんだけどもしかしてこれ劣化双方向探索だった？
Caml trading
Y. Minsky and S. Weeks: Caml trading - experiences with functional programming on Wall Street. JFP 18(4):553-564, 2008.
著者らが所属するJane Streetは自社資金のみでトレーディングを行う会社であり、設立当初はExcelやVBAを使っていたが2005年頃からOCamlをメイン言語として採用している。僅かなバグや数ミリ秒の遅れがパフォーマンスに大きく響く自動取引の世界で、安全性と速度の両立を実現したOCamlの特徴とその活用法とは、というのがストーリー。美点と活用法に関してReadability、Performance、Macrosの3節の後OCamlの欠点について、とバランスよく簡潔に書かれている。順に追っていくと、
- Readabilityについて
あたりの関数型言語への言及に付きもののあれこれに以下のOCamlっぽいトピックが続く。
-
- ラベル付き引数
- 型が同じ引数の混同を避けられる
- 多相バリアント
- 例として、例外を用いることを避けて多相バリアントを用い簡潔かつ扱いやすい形でその関数が「失敗」する可能性を表現する手法が紹介されている
- privateな型, 幽霊型
- privateな型については7.9 private な型、幽霊型についてはOCamlテクニック/ghost - ocaml-nagoyaが参考になる。これらは"Make illegal states unrepresentable"を実現しやすくする。
- ラベル付き引数
- Performanceについて
- コンパイラの特性、GC、C/C++とのインターフェースの3項目に分かれる。GCについてはガベージコレクション、インターフェースについてはC関数をラップしてOCamlに接続する方法 (How to wrap C functions to OCaml)あたりを見てもらうとして、コンパイラの特性について書かれていることは次のような感じ。
- Macrosについて
一方欠点については
- generic printerの欠如
- 既出だが。macroでなんとかなるけどデフォルトであったら便利だよねと書いてある
- オブジェクト指向機能の存在
- いらないよねとの指摘。確かにあまり使わないけど……
- 最適化の不足
- 並列実行不可
- 並列GCがないことによる。Jane Streetとしては作れれば作りたいのだろうけどどれくらい見込みがあるのかは知らない
- ビルドのサポートが乏しく巨大プロジェクトに不向き
- モジュールシステム+findlibだけでは不十分との指摘
- INRIAのチームによる伽藍型の開発
- もちろん彼らは素晴らしい仕事をしているが一方どうしても貧弱な標準ライブラリなどの原因となってしまっているという指摘。これも良し悪しとしかいいようのない感じがするが……
といったところ。他にも優秀な人材が集めやすかっただとか色々書いてあるのだけど省略。12ページですぐ読めるのでOCamlがどんな言語なのか(構文とかではなくもっと全体的な話)を掴みたい人にお勧めしたい。
Big_int.extract_big_intが変
let n = 100 let b = shift_left_big_int unit_big_int n |> pred_big_int (* 111...11 *) let k = 2;; for i = 0 to n - k do let m = (extract_big_int b i k |> int_of_big_int) in if m <> int_exp 2 k - 1 then Printf.printf "%d : %d\n" i m; (* failed *) done
とすると
31 : 1 63 : 1 95 : 1
が出力される(OCaml version 3.12.1, Ubuntu 10.04 32-bit)。
extract_big_intはbig_int型の値を2進数表示したものの指定した桁(上ではi)から指定した長さ(上ではk)bitsを切り出す関数であり、例えば2^n-1からならどこから切り出しても連続した1が出てくるはずなのだがそうなっていない、という話。ちなみに64-bitアーキテクチャでは64桁ごとに失敗する。こういう仕様だと言われたらそれはそれで納得できなくもない気もするが。
PFIサマーインターン2011問題の解法の一例
http://research.preferred.jp/2011/07/intern2011_problem/
を分割統治法で解く。
let find_freq x = let open String in let rec aux x len remain = Printf.printf "%s, %d, %c\n" (sub x 0 len) len remain; match len with | 1 -> get x 0 | 0 -> remain | _ -> let rec pair i len_next = if i = len / 2 then (* problem size halved *) (len_next, if len land 1 = 1 then get x (len - 1) else remain) else match get x (2 * i) with c when c = get x (2 * i + 1) -> set x len_next c; (* constant time operation *) pair (i + 1) (len_next + 1) | _ -> pair (i + 1) len_next in let (len_next, remain_next) = pair 0 0 in aux x len_next remain_next in aux (copy x) (length x) ' ' let x1 = "aabbababa" let x2 = "aabbaabbaabbaabbccddaaabbabaababaaaaabaa" let x3 = "baabbaa" let x4 = "abcaabaca" let x5 = "abcaabaac" let xs = [x1; x2; x3; x4; x5];; List.iter (fun x -> Printf.printf "ans : %c\n\n" (find_freq x)) xs
