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

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

最終更新日付：2015/12/17 21:52:04

≪ 2015-12-11-01-非順序連想コンテナとコンストラクタオーバーロード

2015-12-21-01-STL書籍の掲載コードをCL-STLで書いてみよう-24 ≫

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

2015 年 12 月 17 日

気がついたらもう10日も放置しているこのシリーズ。そろそろ Effective STL の話は終わりにしたいので頑張るとしよう（その後何をやるか決めてないのだけど）。今回はタイトルが長いな。「第45項：count、find、binary_search、lower_bound、upper_bound、およびequal_rangeの違いを理解しよう」から。

さて、第45項の趣旨はと言えば、ソート済み（あるいはそうでない）シーケンスや連想コンテナにおいて、どのような局面でどの検索系アルゴリズム（または同名のメソッド）を使用するべきか、というものだ。この項は長いので、とりあえず流していこう。

まず、ソートしていないシーケンスで指定した値を数える場合。これは count アルゴリズム一択だ。線型時間がかかる。

list<Widget> lw;
Widget w;
//...
if( std::count( lw.begin(), lw.end(), w ) ) {
    //...
} else {
    //...
}

で、これが CL-STL だと以下のようになる。あ、そうそう。Widget は面倒なので、CL-STL のコードサンプルでは全て整数値を使う。うん、面倒。

(let ((lw (new stl:list #{0 1 2 3 4 5 6 7 8 9}))
      (w  6))
  (if (< 0 (stl:count (stl:begin lw) (stl:end lw) w))
      :found
      :not-found))

;=> :FOUND

次、カウントするのではなく、最初に見つかった要素の位置を知りたい場合。ソートされていないシーケンスの場合は find アルゴリズムを使うしかない。これも線型時間。そしてこれは反復子を返すので、見つかったかどうかの判定には end 反復子の結果と比較しなければならない。

if( std::find( lw.begin(), lw.end(), w ) != lw.end() ) {
    //...
} else {
    //...
}

CL-STL だと以下。

(let ((lw (new stl:list #{4 0 10 8 6 2}))
      (w  5))
  (if (_/= (stl:find (stl:begin lw) (stl:end lw) w) (stl:end lw))
      :found
      :not-found))

;=> :NOT-FOUND

ただし、通常は見つかった場合にその反復子で何かしたいはずなので、以下のようになるよ、という話。そりゃそうだよね。

list<Widget>::iterator i = std::find( lw.begin(), lw.end(), w );
if( i != lw.end() ) {
    //...
} else {
    //...
}

CL-STL なら以下のように。

(let ((lw (new stl:list #{0 2 4 6 8 10}))
      (w  8))
  (let ((i (stl:find (stl:begin lw) (stl:end lw) w)))
    (if (_/= i (stl:end lw))
        i
        :not-found)))

;=> #<CL-STL:LIST-ITERATOR {1005463F23}>

では次にソート済みのランダムアクセスコンテナにいこう。二分探索で要素の有無だけを調べられれば良いなら、binary_search アルゴリズムの出番だ。こいつは真偽値を返すだけ。

vector<Widget> vw;
//...
std::sort( vw.begin(), vw.end() );
Widget w;
//...
if( std::binary_search( vw.begin(), vw.end(), w ) ) {
    //...
} else {
    //...
}

CL-STL ならこんな感じ。ここからはランダムなシーケンスを生成してソートしてから動かすように書いているため、実行するたびに結果が違う。

(let ((vw (new stl:vector 100)))
  (stl:generate (stl:begin vw) (stl:end vw) (lambda () (random 100)))
  (stl:sort (stl:begin vw) (stl:end vw))
  (let ((w 13))
    (if (stl:binary-search (stl:begin vw) (stl:end vw) w)
        :found
        :not-found)))

;=> :NOT-FOUND

二分探索で見つかった場合にその要素を指す反復子が必要なら、lower_bound を使う必要がある。

vector<Widget>::iterator i = lower_bound( vw.begin(), vw.end(), w );
if( i != vw.end() && *i == w ) {
    //...
} else {
    //...
}

lower_bound は常に反復子を返すから、end 反復子以外が返された場合でも値のチェックが必要だ。慣れるまでは頭に入り難いかもしれないが、lower_bound がやることは「指定された値よりも小さくない最小の要素を返す」ということだ。ちなみに、upper_bound は「指定された値よりも大きい最小の要素を返す」。

それはさておき、CL-STL ならこう。

(let ((vw (new stl:vector 100)))
  (stl:generate (stl:begin vw) (stl:end vw) (lambda () (random 100)))
  (stl:sort (stl:begin vw) (stl:end vw))
  (let* ((w 13)
         (i (stl:lower-bound (stl:begin vw) (stl:end vw) w)))
    (if (and (_/= i (stl:end vw)) (_== (_* i) w))
        i
        :not-found)))

;=> #<CL-STL:VECTOR-ITERATOR {1005FA0D93}>

ちなみに、lower-bound は「等価」を基準にして検索している一方、上記の if では「等値」で復帰値のチェックをしている、これは問題になる場合があるよ、という話が書籍にはあるが、これは割愛。

で、割愛された上記の話題に関連して「等価な要素の数を調べる効果的な方法」として挙げられているのが、equal_range を使う方法。これは要するに lower_bound と upper_bound の併わせ技だ。

vector<Widget> w;
//...
std::sort( vw.begin(), vw.end() );
typedef vector<Widget>::iterator VWIter;
typedef pair<VWiter,VWiter> VWIterPair;
VWIterPair p = std::equal_range( vw.begin(), vw.end(), w );
if( p.first != p.second ) {
    //...
} else {
    //...
}

CL-STL ならこう。まぁなんというか、ちゃんと動く。

(let ((vw (new stl:vector #{0 1 2 3 4 1 2 3 4 2 3 4 3 4 4})))
  (stl:sort (stl:begin vw) (stl:end vw))
  (let* ((w 3)
         (p (stl:equal-range (stl:begin vw) (stl:end vw) w)))
    (if (_/= (stl:first p) (stl:second p))
        (stl:distance (stl:first p) (stl:second p))
        :not-found)))

;=> 4

あ—、なんていうか、疲れてしまった。今回はここまでにしよう。この第45項でさらに書くことがあるかどうかは改めて確認して、あれば次回は続きをやるということで。

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

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

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

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

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

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

コメント

このページのタグ

project-enigma

メニュー

更新履歴

2017/07/08

2017/07/04

2017/06/29

2017/06/07

2017/05/09

2017/05/08

2017/03/27

2017/03/26

2017/03/14

2017/03/13

2017/02/22

2017/02/18

2017/02/15

2017/02/13

2017/01/28