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*)))

　

これで準備完了だ。まずは２つの 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 - 第５項：単一要素メンバ関数より範囲メンバ関数を使おう
• 2015-10-14 - 第30項：出力先範囲の大きさを確認しよう
• 2015-10-16 - 第31項：ソートの選択肢を知っておこう

　

コメント

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

　

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

　

　

---

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