リストのユニーク
sbcl(1.0.28)で文字列のリストのユニークな要素を取ろうとすると、やけに遅い。
リストの要素数は30万くらいなのだが、しばらく待ってもレスポンスがない。
> (length *word-list*) ; *word-list*は文字列のリスト --> 320000 ; この数は適当 > (time (remove-duplicates *word-list* :test #'string=)) ;; CPU使用率はほぼ100%で、数分待っても応答が返ってこない。
どうやら原因は、重複テスト関数にstring=を渡していたことらしく、それをequal関数に置き換えたら、速度は劇的に早くなった。
> (time (length (remove-duplicates *word-list* :test #'equal))) Evaluation took: 0.095 seconds of real time ; 0.1秒くらい 0.092006 seconds of total run time (0.092006 user, 0.000000 system) [ Run times consist of 0.024 seconds GC time, and 0.069 seconds non-GC time. ] 96.84% CPU 301,395,109 processor cycles 10,666,304 bytes consed --> 300000
equal関数に比べてstring=関数が遅いということもないはず*1なのに、何でこんなに速度差が出るのか不思議だったので、sbclのソースコードを調べてみた。
結果、どうやらsbclはユニークな要素を取るために、test引数がeql系の関数の場合にはハッシュテーブルを使用して、そうではない場合はmember関数を使用して、重複チェックを行っているらしいことが判明した。 ※ 前者は一回の重複チェックにO(1)、後者はO(N)の処理が必要
下記は、その部分のコードを簡略化して示したもの。
;; sbclのリストユニーク関数の簡略化版 ;; あくまでも説明用のコードなので、正しい本来のコードを知りたい人は、sbcl-1.0.29/src/code/seq.lispのlist-remove-duplicates*関数を参照のこと (defun list-remove-duplicates (list &key (key #'identity) (test #'eql)) ;; ハッシュテーブルが使用可能かどうかを調べ、可能なら作成する (let ((hash (and (eq key #'identity) ; key関数は、identityのみ可 (or (eql test #'eql) ; test関数は、make-hash-tableに渡せるもののみ可 (eql test #'eq) (eql test #'equal) (eql test #'equalp)) (make-hash-table :test test)))) ; ハッシュテーブル作成 ;; ハッシュテーブルが使用可能かどうかで分岐 ;; どちらも見た目上は、それほど違いはないが、重複チェック関数の性能が大幅に異なる (if hash ;; ハッシュを使って重複チェック (loop FOR elem IN list ; (length list)回のループ UNLESS (gethash elem hash) ; O(1) COLLECT (setf (gethash elem hash) elem)) ; ユニークな要素を集める ;; member関数を使って重複チェック (loop FOR (elem . rest) ON list ; (length list)回のループ UNLESS (member (funcall key elem) rest :test test :key key) ; O(length rest) COLLECT elem)))) ; ユニークな要素を集める
testにstring=関数を渡した場合は、member関数が使われることになるので、それで遅かったようだ。
多分これだとequal関数を渡した場合に比べ、おおざっぱに云って十数万倍程度の要素比較が必要とされていたはず。
string=関数の場合は代替のequal関数があるから良いが、リストの要素数が多くて且つ少し変わった関数(or lambda式)を重複テストで使いたい場合は、とてもじゃないがremove-duplicates関数は使えなさそう。
ソート済みのリストのユニーク
ちなみに、remove-duplicates関数のtest引数にequal関数を渡せば速くなると気づいたのは偶然で、最初はこの問題を解決するために、下のようなソート済みリストからユニークな要素を取得する関数を自作して、ソート関数と組み合わせて使っていた。
この方法だと、比較関数を用意する必要はあるが、どんな重複テスト関数を使ってもだいたいO(N log N)のオーダー*2でユニークなリストを求めることができるので、性能的には安定している。
;; ソート済みのリストからユニークな要素を集めたリストを取得する ※ 最適化はなし (defun list-unique (list &key (test #'eql) (key #'identity)) (flet ((eql? (a b) (funcall test (funcall key a) (funcall key b)))) (when list (cons (car list) (loop FOR prev IN list FOR cur IN (cdr list) UNLESS (eql? prev cur) COLLECT cur))))) ;; 例 > (time (progn (list-unique (sort *word-list* #'string<) :test #'string=) 'done)) Evaluation took: 0.671 seconds of real time ; remove-duplicatesにequalを渡した場合よりは遅いが、そこそこ高速 0.668042 seconds of total run time (0.668042 user, 0.000000 system) 99.55% CPU 2,128,937,194 processor cycles 2,609,152 bytes consed --> DONE
