hash-table benchmark
5165 件のサンプルデータ(すべてヒットする)でまずはテストしてみた。
mod,ht はほぼ同等、あるいは mod(つまりオリジナルと同等)が若干速い?。いづれにしろ微妙な差なので、繰り返し実行するなり、サンプルを増やすなりしないといけないと分かった。ht-el はやはり若干遅い。あまり嬉しくない結果だ。
5000 件でどのテストも 0.4から1.5sec 内に処理が終わる。差はつきにくいなぁ。
もっと大きなデータで試すか、辞書データで精緻に調べるか。
elp による elisp のプロファイル
emacs についている elp というツールを使って、プロファイルを取ってみた。
こんな結果になった。若干ばらつきがあるが、ht > mod > ht-el となっている。ハッシュテーブルが速い、というより、skk のバイナリサーチが速い、というべきか?あるいはバッファ内での検索が速いというべきか?
Function Name Call Count Elapsed Time Average Time ===================== ========== ============ ============ my-gethash 103300 23.195215000 0.0002245422 skk-search-jisyo-test 103300 19.909423000 0.0001927340 gethash 103300 12.046009000 0.0001166118 Function Name Call Count Elapsed Time Average Time ===================== ========== ============ ============ my-gethash 103300 27.835620000 0.0002694638 skk-search-jisyo-test 103300 25.684847999 0.0002486432 gethash 103300 15.115295000 0.0001463242
ここでアルゴリズムとデータ構造の力で、elisp で作った何かがハッシュテーブル版より速くできると嬉しいんだが、可能性はあるだろうか?
失敗
ここで ht-el を見ていたら my-gethash の愚かなミスに気づいた。ハッシュテーブルの要素の alist を二回検索してた‥。いくら assoc が速くてもどう考えても無駄すぎ。
(defun my-gethash (key table &optional dflt) (let ((hash (my-sxhash table key))) (let ((lst (aref table hash))) (let ((hit (assoc key lst))) (if hit (cdr hit) dflt))))) ;; (defun my-gethash (key table &optional dflt) ;; (let ((hash (my-sxhash table key))) ;; (let ((lst (aref table hash))) ;; (if (assoc key lst) ;; (cdr (assoc key lst)) ;; dflt))))
もうちょっと慎重にテストしなくちゃいけないが、どうやら elisp によるハッシュテーブルと(ht-el)とバッファー内のバイナリ+シーケンシャルな検索(mod)が逆転するかも。
Function Name Call Count Elapsed Time Average Time ===================== ========== ============ ============ skk-search-jisyo-test 103300 24.806983999 0.0002401450 my-gethash 103300 16.909666999 0.0001636947 gethash 103300 13.035140000 0.0001261872