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

≪ 2015-12-08-01-STL書籍の掲載コードをCL-STLで書いてみよう-22

2015-12-11-01-非順序連想コンテナとコンストラクタオーバーロード ≫

vectorとdequeとfindとlower-bound

2015 年 12 月 09 日

前回書いた内容から、ソート済みのランダムアクセスコンテナに対する find と lower-bound の比較、および配列に対する内部的な最適化の効果が気になってきた。今回はこのへんをなんとなく。

そんなわけで、今回は stl:vector と stl:deque を使う。stl:vector は内部的には配列を使っていて、アルゴリズム側でも可能な限りの最適化をしている。一方で、stl:deque はアルゴリズム側での最適化はしていない。これがどの程度パフォーマンスの差として現れてくるか。これを find と lower-bound を使って試してみよう。ついでなので、連想コンテナの同名メソッドも参考としてやってみよう。

まずは３種類のコンテナに対して 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 向けアルゴリズムが遅いというオチかもしれないが。

このページにコメントする