2015-10-17-01-STL書籍の掲載コードをCL-STLで書いてみよう-11 - project-enigma

2015-10-17-01-STL書籍の掲載コードをCL-STLで書いてみよう-11

>> Site top >> weblog >> 月別アーカイブ >> 2015年10月のlog >> 2015-10-17-01-STL書籍の掲載コードをCL-STLで書いてみよう-11

最終更新日付:2015/10/17 06:34:41


STL書籍の掲載コードをCL-STLで書いてみよう-11

2015 年 10 月 17 日

さてさて、前回のおつり拾い。Effective STL の第31項、「ソートの選択肢を知っておこう」の残りの話を。

といっても、まぁそれほど書きたいコードも残っていないので、計算コストの話を曖昧に書いていこう。Effective STL では、「大まかに言って、多くの作業を行なうアルゴリズムにはそれだけ時間がかかる」と書いている。当たり前と言えば当たり前の話だな。そして、時間と空間のコストが少ない順として以下が提示されている。

  1. partition
  2. stable_partition
  3. nth_element
  4. partial_sort
  5. sort
  6. stable_sort

 

そんなわけで、昨日のコードをベースに、time を使った計測をやってこの項はおしまいにしようと思う。それぞれのコードは大体10回程度実行して、一番良い数字を選んでいる。上記のリストを少ない順でいこう。まずは partition から。

(progn
  (shuffle-widgets)
  (time (stl:partition (stl:begin *widgets*) (stl:end *widgets*)
                       (lambda (obj)
                         (< 80 (widget-quality obj))))))

;Evaluation took:
;  0.000 seconds of real time
;  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;  100.00% CPU
;  79,992 processor cycles
;  0 bytes consed

 

とりあえず、これが基準だ。これに対して、stable-partition はどうだろう。おやおや、6倍のコストがかかるのか‥‥‥

(progn
   (shuffle-widgets)
   (time (stl:stable-partition (stl:begin *widgets*) (stl:end *widgets*)
                               (lambda (obj)
                                  (< 80 (widget-quality obj))))))

;Evaluation took:
;  0.000 seconds of real time
;  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;  100.00% CPU
;  498,636 processor cycles
;  0 bytes consed

 

さて、ここから先は quality-compare を使うことになるのだけれど、今回は以下のように宣言をつけておくことにしよう。

(locally (declare (optimize speed))
  (defun quality-compare (widget1 widget2)
    (declare (type widget widget1 widget2))
    (< (the fixnum (widget-quality widget2))
       (the fixnum (widget-quality widget1)))))

 

では、nth-element 行ってみよう。こちらの方がずっと計算量が少ないようだ。

(progn
  (shuffle-widgets)
  (time (stl:nth-element (stl:begin *widgets*)
                         (_+ (stl:begin *widgets*) 20) (stl:end *widgets*) #'quality-compare)))

;Evaluation took:
;  0.000 seconds of real time
;  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;  100.00% CPU
;  222,852 processor cycles
;  0 bytes consed

 

んでは、partial-sort だ。これでもまだ stable_paritition より速い。

(progn
  (shuffle-widgets)
  (time (stl:partial-sort (stl:begin *widgets*)
                          (_+ (stl:begin *widgets*) 20) (stl:end *widgets*) #'quality-compare)))

;Evaluation took:
;  0.000 seconds of real time
;  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;  100.00% CPU
;  311,569 processor cycles
;  0 bytes consed

 

じゃあ sort 。これが stable_paritition と同じくらいということになった。

(progn
  (shuffle-widgets)
  (time (stl:sort (stl:begin *widgets*) (stl:end *widgets*) #'quality-compare)))

;Evaluation took:
;  0.000 seconds of real time
;  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;  100.00% CPU
;  557,388 processor cycles
;  0 bytes consed

 

最後に stable-sort 。これは文句なしに重い。本当に必要のない局面で使おうとは思わないだろう。

(progn
  (shuffle-widgets)
  (time (stl:stable-sort (stl:begin *widgets*) (stl:end *widgets*) #'quality-compare)))

;Evaluation took:
;  0.000 seconds of real time
;  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;  100.00% CPU
;  1,919,376 processor cycles
;  0 bytes consed

 

ひとまずのところ、stable-partition を除けばおおむね予想(期待?)した結果が出たと思う。stable-partition については、ひょっとしたらまだ実装に改良の余地があるのかもしれない。現在取り組んでいる連想コンテナの刷新が完了してら見てみようかな。

 

このシリーズのこれまでのエントリ

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.