AutoJudgクラス

昨日の夜はかなり寝付けなかった。
最近よく昼寝してるのだが、夜寝れないのは非効率的かもー。

んなことはどうでもよくて、夜中にベッドの中でもんもんとしながらローマ字変換をもっと高速化できないかなと考えつつ、二分探索（バイナリサーチ）を思い出した。

簡単に説明すると
『1 3 4 ・・・25・・・46 47 50 52 55・・・98 99 100』
とデータが並んでいるときに、「39」がその中に入っているかどうか調べる場合。
真ん中のデータを「50」とすると、「39」と比較して「50」より大きいか小さいかを調べる。
小さければ「1」から「50」の中に入っていることがわかるので、次に1と50の真ん中の25と比較して大きいか小さいか調べる。
25より大きいので25と50の中にあることがわかる。
・・・というように調べていくのがバイナリサーチである。
調べる対象がどんどん半分になっていくのが分かると思う。

N個のソートされたデータから、あるデータを探すときに順番に探していけば必ずN時間かかってしまうが、二分探索を使うとlog(N)時間で探せるという優れもの。
ローマ字変換表は既にソート済みのものを使うので、ソートには時間がかからず単純にlog(N)時間で探せる。今回の場合にマッチしたアルゴリズムである。
こんな説明するまでもなく、「当たり前」なんだろうけど・・・（汗）

で、早速適用。せっかくだからC標準関数のbsearch()を使うことにする。
「っ」が入ると変換に時間がかかるので、４０文字の文字列（オール「っ」の場合とオール「あ」の場合）に全体のローマ字変換を１００回繰り返した場合のタイムを測定。

適用前

オール「っ」：２７６５ミリ秒
オール「あ」：　６６０ミリ秒
１０個「っ」：１１５５ミリ秒

適用後

オール「っ」：　　７５ミリ秒
オール「あ」：　　３８ミリ秒
１０個「っ」：　　４６ミリ秒

Σ(゜Д゜)スゴッ
およそ２０〜３０倍の高速化。
探す対象が１５０個程度だから、Log150 = 7.2
うむうむ。ほぼ計算どおりだ（当たり前）

計算量において最悪の場合がオール「っ」のときだから、もうどんな場合でも４０文字なら0.001秒以下でローマ字変換できることになった。めでたしめでたし♪