Hash-table benchmark

built-in hash-table 版(ht), elisp で実装した hash-table 版(ht-el), オリジナル、の比較を行う。
オリジナルの skk-search-jisyo は、検索以外に処理を行っているので、公平になるように機能を削った版(mod)を作成した。

ht は単純なハッシュテーブルなので、O(1)、ただし若干のハッシュ値のコリジョンがある。ht-el は elisp で遅く、かつ、ht と全く同じコリジョンがある。mod は、バッファー内に読み込まれたソート済みの辞書に対して、バイナリサーチを行い、選択範囲が10000以下になるとリニアサーチに切り替わる。イメージとしては goto-char で真ん中に飛び、見出し語と検索文字を比較して、その大小によって繰り返し goto-char でジャンプ。選択幅が 10000(カスタマイズ可能)以下になったら search-forward で検索。
あまり差が出ない可能性が非常に高いが、期待としては、検索速度に関して ht > ht-el > mod となって欲しい。

まずはサンプルデータを用意し、速度を計測。その後丁寧にプロファイリングしてみる、という順序で試す。あとはこの速度について、定量的に何か言えるように考えてみる。できればグラフが書けるといい。

サンプルデータを考えるのはなかなか難しいなあ。ヒットしないデータを沢山含めると、 mod に不利（おそらく。バッファー内の検索がものすごく速いとかなければ）。しかし skk を長年使っている印象では、かなりの頻度でヒットしているので、ランダムに選択したひらがなをサンプルデータにする、というのはあまりにインチキと思える。またデータの数、種類も大事。mod は検索後、前の状態が次の検索に影響を与えるだろうか？

速度の計測というか経過時間の計測には、 benchmark という elisp を用いることにする。(require 'benchmark) の後、(benchmark-elapse form) とするとformを評価したあとに経過時間を表示する、らしい。

ht-el は、改良の余地がある。SKK ラージ辞書は静的なので、完全ハッシュ関数と言われるすべての見出しについてユニークな値が振れるような関数が選べる可能性があり、そうすると比較が減るので速くなる（理解がかなりあやしいが）。
さらに、b-tree など他のデータ構造を使ってより高速な elisp もありうる。ただし、SKK 辞書はそれほどレコード数が大きくないので、どんな方法でも差がほとんど出ない可能性もある。

いづれにせよ、適切なサンプルデータがうまく選べないと話が進まない。