2015-10-16-01-STL書籍の掲載コードをCL-STLで書いてみよう-10
>> Site top >> weblog >> 月別アーカイブ >> 2015年10月のlog >> 2015-10-16-01-STL書籍の掲載コードをCL-STLで書いてみよう-10
最終更新日付:2015/10/16 01:00:00
STL書籍の掲載コードをCL-STLで書いてみよう-10
2015 年 10 月 16 日
今回は自分でも始める前からおっかなびっくり、Effective STL の第31項、「ソートの選択肢を知っておこう」から。
この項は、要約すれば「なんでもかんでも全ソートするんじゃねーよ」という話に尽きる。最初に Widget なるクラスがあるものとして、そのクォリティを比較する関数が提示される。
bool qualityCompare( const Widget& lhs, const Widget& rhs ) { // lhs の品質が rhs の品質より高いかどうかを返す }
で、Widget のシーケンスからクォリティ順で上位20個だけが知りたいなら、sort でなく partial_sort でしょという話から始まるわけだ。
std::partial_sort( widgets.begin(), widgets.begin() + 20, widgets.end(), qualityCompare);
今回はそれなりに興が乗ったので、ちょっとしっかりやってみようかと思う。まずはクラス widget を定義しよう。問題のクォリティは整数メンバとして持たせて、他に何もないのは寂しいので愚直に name という文字列メンバを追加する。
(defclass widget () ((quality :type :integer :initform 0 :initarg :quality :accessor widget-quality) (name :type :string :initform "" :initarg :name :accessor widget-name)))
とはいえ、いちいち名前を考えるのも面倒臭い。そこで、create-widget 関数を定義し、クォリティ値だけからインスタンスを生成するようにした。名前はクォリティ値を format 関数で文字列化するだけだ。本当に文字列化するのではつまらないので、~r で書式化。
(defun create-widget (quality) (make-instance 'widget :quality quality :name (format nil "~r" quality)))
さて、widget のシーケンスは何度も使うことになるので、*widgets*という名前で大域に置いてしまうことにした。defparameter した上で、[0, 100) のクォリティ値でシーケンスを生成する。
(defparameter *widgets* (new stl:vector 100 nil)) (stl:generate (stl:begin *widgets*) (stl:end *widgets*) (let ((idx 0)) (lambda () (create-widget (incf idx)))))
これをダンプする関数と、シャッフルする関数を定義しておこう。
(defun dump-widgets (&optional (stream t)) (stl:for (obj *widgets*) (format stream "~A : ~A~%" (widget-quality obj) (widget-name obj)))) (defun shuffle-widgets () (stl:random-shuffle (stl:begin *widgets*) (stl:end *widgets*)))
これで準備完了だ。まずは2つの widget のクォリティ値を比較する関数を。
(defun quality-compare (widget1 widget2) (< (widget-quality widget2) (widget-quality widget1)))
これがあれば、冒頭の STL コードの partial_sort 呼び出しは CL-STL で以下のように書ける。
(stl:partial-sort (stl:begin *widgets*) (_+ (stl:begin *widgets*) 20) (stl:end *widgets*) #'quality-compare)
では、実際に動かしてみよう。このページ上では端折っているが、ちゃんと20番目までが降順でソートされている。ちなみに、20番目とは「81 : eighty-one」という行だ。
(progn (shuffle-widgets) (stl:partial-sort (stl:begin *widgets*) (_+ (stl:begin *widgets*) 20) (stl:end *widgets*) #'quality-compare) (dump-widgets)) => 100 : one hundred 99 : ninety-nine 98 : ninety-eight 97 : ninety-seven 96 : ninety-six : : 85 : eighty-five 84 : eighty-four 83 : eighty-three 82 : eighty-two 81 : eighty-one 6 : six 11 : eleven 17 : seventeen : : 53 : fifty-three 69 : sixty-nine 35 : thirty-five NIL
Effective STL では、この後他の選択肢に話が移る。まずは nth_element だ。説明は面倒なので省くが、実行結果は以下の通り。たしかに、20番目の「81 : eighty-one」より上にはより上位が、それより下には下位のオブジェクトしかない。
(progn (shuffle-widgets) (stl:nth-element (stl:begin *widgets*) (_+ (stl:begin *widgets*) 20) (stl:end *widgets*) #'quality-compare) (dump-widgets)) => 84 : eighty-four 87 : eighty-seven 92 : ninety-two 90 : ninety 97 : ninety-seven : : 89 : eighty-nine 93 : ninety-three 83 : eighty-three 82 : eighty-two 81 : eighty-one 80 : eighty 79 : seventy-nine 58 : fifty-eight : : 11 : eleven 26 : twenty-six 35 : thirty-five NIL
さらに別の選択肢として、ソートではないが partition に触れられている。これは条件を満たす要素と満たさない要素で分割するものだ。Effective STL では hasAcceptableQuality 関数というのを導入しているが、ここではラムダ式で片付けている。ちなみに、partition が返したのは「16 : sixteen」の要素を指す反復子だった(はず)。
(progn (shuffle-widgets) (stl:partition (stl:begin *widgets*) (stl:end *widgets*) (lambda (obj) (< 80 (widget-quality obj)))) (dump-widgets)) => 86 : eighty-six 90 : ninety 81 : eighty-one 98 : ninety-eight 91 : ninety-one : : 100 : one hundred 88 : eighty-eight 93 : ninety-three 96 : ninety-six 99 : ninety-nine 16 : sixteen 20 : twenty 46 : forty-six 27 : twenty-seven : : 19 : nineteen 60 : sixty NIL
‥‥‥今回はここまでにしておこう。第31項「ソートの選択肢を知っておこう」としてはまだやりたいことはあるのだけれど、続きは明日以降ということで。
このシリーズのこれまでのエントリ
- 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 - 第5項:単一要素メンバ関数より範囲メンバ関数を使おう
- 2015-10-14 - 第30項:出力先範囲の大きさを確認しよう
- 2015-10-16 - 第31項:ソートの選択肢を知っておこう
コメント
このページのタグ
Page tag : STLとその移植
Page tag : Common Lisp
Copyright(C) 2005-2021 project-enigma.
Generated by CL-PREFAB.