2015-12-09-01-vectorとdequeとfindとlower-bound
>> Site top >> weblog >> 月別アーカイブ >> 2015年12月のlog >> 2015-12-09-01-vectorとdequeとfindとlower-bound
最終更新日付:2015/12/09 01:00:00
vectorとdequeとfindとlower-bound
2015 年 12 月 09 日
前回書いた内容から、ソート済みのランダムアクセスコンテナに対する find と lower-bound の比較、および配列に対する内部的な最適化の効果が気になってきた。今回はこのへんをなんとなく。
そんなわけで、今回は stl:vector と stl:deque を使う。stl:vector は内部的には配列を使っていて、アルゴリズム側でも可能な限りの最適化をしている。一方で、stl:deque はアルゴリズム側での最適化はしていない。これがどの程度パフォーマンスの差として現れてくるか。これを find と lower-bound を使って試してみよう。ついでなので、連想コンテナの同名メソッドも参考としてやってみよう。
まずは3種類のコンテナに対して 100万要素のオブジェクトを作成する。ソート済みシーケンスは、stl:iota で簡単に。連想コンテナはそういうわけにはいかないので 100万回 insert するよ。
(defparameter *vector* (new stl:vector 1000000)) (defparameter *deque* (new stl:deque 1000000)) (defparameter *set* (new stl:set #'<)) (stl:iota (stl:begin *vector*) (stl:end *vector*) 0) (stl:iota (stl:begin *deque*) (stl:end *deque*) 0) (dotimes (n 1000000) (stl:insert *set* n))
でもって、今回は検索値は #'random でもって 100 個用意し、全ての組み合わせで同じモノを使用する。以下のような感じ。
(let* ((cnt 100) (chk (new stl:vector cnt))) (stl:generate (stl:begin chk) (stl:end chk) (lambda () (random 1000000))) (let ((i1 (stl:begin *vector*)) (i2 (stl:end *vector*))) (time (stl:for (v chk) (stl:find i1 i2 v))) (time (stl:for (v chk) (stl:lower-bound i1 i2 v #'<)))) (let ((i1 (stl:begin *deque*)) (i2 (stl:end *deque*))) (time (stl:for (v chk) (stl:find i1 i2 v))) (time (stl:for (v chk) (stl:lower-bound i1 i2 v #'<)))) (time (stl:for (v chk) (stl:find *set* v))) (time (stl:for (v chk) (stl:lower-bound *set* v))))
とりあえずは出力をそのまま。
;Evaluation took: ; 1.139 seconds of real time ; 1.138807 seconds of total run time (1.138807 user, 0.000000 system) ; 100.00% CPU ; 2,701,556,671 processor cycles ; 32,768 bytes consed ; ;Evaluation took: ; 0.000 seconds of real time ; 0.000000 seconds of total run time (0.000000 user, 0.000000 system) ; 100.00% CPU ; 354,969 processor cycles ; 32,752 bytes consed ; ;Evaluation took: ; 10.436 seconds of real time ; 10.436467 seconds of total run time (10.436467 user, 0.000000 system) ; 100.00% CPU ; 24,987,847,929 processor cycles ; 0 bytes consed ; ;Evaluation took: ; 0.000 seconds of real time ; 0.000000 seconds of total run time (0.000000 user, 0.000000 system) ; 100.00% CPU ; 3,679,875 processor cycles ; 65,536 bytes consed ; ;Evaluation took: ; 0.000 seconds of real time ; 0.000000 seconds of total run time (0.000000 user, 0.000000 system) ; 100.00% CPU ; 833,895 processor cycles ; 32,752 bytes consed ; ;Evaluation took: ; 0.000 seconds of real time ; 0.000000 seconds of total run time (0.000000 user, 0.000000 system) ; 100.00% CPU ; 330,918 processor cycles ; 32,768 bytes consed
で、processor cycles の部分を表にしてみよう。
find | lower-bound | |
---|---|---|
vector | 2701556671 | 354969 |
deque | 24987847929 | 3679875 |
set | 833895 | 330918 |
これじゃ良くわからない気がするので、stl:vector × stl:find の組み合わせを基準にして再度。こんな感じ。
find | lower-bound | |
---|---|---|
vector | 1.0000000 | 0.0001314 |
deque | 9.2494258 | 0.0013621 |
set | 0.0003087 | 0.0001225 |
ご覧の通りで、stl:vector 対 stl:deque に関して言えばやはり stl:vector に対する最適化の圧勝。そして find と lower-bound もほとんど勝負になっていない。まぁ、そりゃそうだよね。
それよりも気になるのは、連想コンテナが思ったほどには遅くないことだ。Effective STL なんかでも、連想コンテナよりソート済み vector の方が速いことが多いとしている。だが CL-STL に関して言えば、少なくとも CL-STL の lower-bound に関して言えば、stl:set の方が速い。いや、vector 向けアルゴリズムが遅いというオチかもしれないが。
コメント
このページのタグ
Page tag : STLとその移植
Page tag : Common Lisp
Copyright(C) 2005-2019 project-enigma.
Generated by CL-PREFAB.