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 01:00:00
STL書籍の掲載コードをCL-STLで書いてみよう-11
2015 年 10 月 17 日
さてさて、前回のおつり拾い。Effective STL の第31項、「ソートの選択肢を知っておこう」の残りの話を。
といっても、まぁそれほど書きたいコードも残っていないので、計算コストの話を曖昧に書いていこう。Effective STL では、「大まかに言って、多くの作業を行なうアルゴリズムにはそれだけ時間がかかる」と書いている。当たり前と言えば当たり前の話だな。そして、時間と空間のコストが少ない順として以下が提示されている。
- partition
- stable_partition
- nth_element
- partial_sort
- sort
- 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 はどうだろう。おやおや、６倍のコストがかかるのか‥‥‥
(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 については、ひょっとしたらまだ実装に改良の余地があるのかもしれない。現在取り組んでいる連想コンテナの刷新が完了してら見てみようかな。
このシリーズのこれまでのエントリ
- 2015-09-19 - 第47項：書き込み専用コードの作成は避けよう
- 2015-09-20 - 第9項：消去オプションは注意して選択しよう
- 2015-09-22 - 第9項：消去オプションは注意して選択しよう - 2
- 2015-09-28 - 第9項：消去オプションは注意して選択しよう - 3
- 2015-09-30 - 第14項：reserve を使って不必要な割り当てを避けよう
- 2015-10-01 - 第17項：余分な容量を取り除くには「swap技法」を使おう
- 2015-10-09 - 第27項：コンテナのconst_iteratorをiteratorに変換するには、distanceとadvanceを使おう
- 2015-10-12 - 第５項：単一要素メンバ関数より範囲メンバ関数を使おう
- 2015-10-14 - 第30項：出力先範囲の大きさを確認しよう
- 2015-10-16 - 第31項：ソートの選択肢を知っておこう
- 2015-10-17 - 第31項：ソートの選択肢を知っておこう - 2
コメント
このページのタグ
Page tag : STLとその移植
Page tag : Common Lisp
Copyright(C) 2005-2020 project-enigma.
Generated by CL-PREFAB.
