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

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 08:21:03


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項「ソートの選択肢を知っておこう」としてはまだやりたいことはあるのだけれど、続きは明日以降ということで。

 

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

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


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