emacs lispで高速なremove-dupsを書く

次世代auto-complete.elを読んでみる - http://rubikitch.com/に移転しました

id:IMAKADOさんによるとdelete-dupsは要素数が多いと遅いので、本当に高速化したい場合はハッシュテーブルを使ったほうがいいかと。anything.elではそうしている。

簡単なベンチマーク書いてみました。
emacs lispのベンチマークの書き方って、benchmark-run-compiled 関数を使う方法で正しいのでしょうか？

(require 'cl) ; remove-duplicates, loop, push
;; 巨大なストリングのリストを作る
(setq my-big-los
      (loop for sym being the symbols
            collect (symbol-name sym)))

(length my-big-los) ;=> 31337 (自分の環境では)

(defun my-fast-remove-dups (los)
  (let ((hash (make-hash-table :test 'equal))
        (ret nil))
    (loop for s in los
          do (puthash s nil hash))
    (maphash (lambda (k v) (push k ret)) hash)
    ret))


;;; ベンチマーク  core2duo, memory 2G
;; 非破壊的
(benchmark-run-compiled 1 (my-fast-remove-dups my-big-los)) ;=> (0.230121 2 0.15066300000000155)

(benchmark-run-compiled 1 (remove-duplicates my-big-los :test 'equal)) ; お、終わらない...

;; 破壊的!!
(benchmark-run-compiled 1 (delete-dups my-big-los)) ;=> (14.987222 0 0.0)

delete-dupsが遅い理由は、それ自体がemacs lispで書かれているのが原因っぽいです。
subr.elで定義されています。

ボトルネックになりそうな部分は、cで実装されている関数*1や、loop等のコンパイル時に組み込み関数に展開されるマクロを使用するのが良さそうだと思っています。

再帰で書いたほうがグレイトなコードになる場合もありますが、emacs lispには末尾再帰の最適化がないのと単純に関数呼び出しのコストが高いという理由から、書きたくても書けない場面もありそうですしね・・・。

いきなりだけど、僕はemacs lisp大好きですね、schemeやcommon lispと比べるといただけない部分もあるかもしれませんが、lispだし、良いデバッガーあるし、実行環境で書いてるから直ぐに試せるし、何といってもemacsを拡張することができますし!!

*1:fns.cで定義されている関数