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

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

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

最終更新日付:2015/12/03 00:00:19


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

2015 年 12 月 03 日

なんか面倒になってしまったので、Effective STL のファンクタの残りはやらないことにした。その先に行こう。「第43項:独自に作成したループよりアルゴリズムの呼び出しを優先して使おう」だ。この項はけっこう長いので、数回に分けることになるかもしれない。

さて、登場するのはお馴染み Widget クラス。今回はこんなのから話が始まる。

class Widget {
public:
    //...
    void redraw() const;
    //...
};

 

で、これを格納した list のシーケンス内の全オブジェクトを再描画する場合、以下のようにする方法がある、と。

list<Widget> lw;
//...
for( list<Widget>::iterator i = lw.begin(); i != lw.end(); ++i ) {
    i->redraw();
}

 

一方で、以下のようにもできるよね、と。

for_each( lw.begin(), lw.end(), mem_fun_ref( &Widget::redraw ) );

 

ここまでをちょっと CL-STL で書いてみよう。まず、widget クラスと redraw メソッドを作っておく。

(defclass widget () ())
(defgeneric redraw (obj))
(defmethod  redraw ((obj widget))
  (format t "widget::radraw invoked.~%"))

 

で、list のインスタンスを作成して要素を適当に。

(defparameter lw (new stl:list))
(dotimes (i 5)
  (stl:push-back lw (make-instance 'widget)))

 

そして、2種類の方法(つまり明示的ループと for-each アルゴリズム)でシーケンスの全要素を再描画‥‥‥と。まぁ、後者の方が明らかに簡潔でいいよね。

;; explicit loop
(do ((i (stl:begin lw) (_++ i)))
    ((_== i (stl:end lw)) nil)
  (redraw (_* i)))

;; using algorithm
(stl:for-each (stl:begin lw) (stl:end lw) (stl:mem-fun-ref #'redraw))

 

ちなみに、C++11 以降で考えるのであれば、以下のようにも書ける。実質これが一番簡単なんだが。

(stl:for (obj lw)
  (redraw obj))

 

ここで一応の注意をしておくと、stl:for-each の呼び出しで使用している stl:mem-fun-ref には、実質なんの意味もない。STL ではこれはメンバ関数をファンクタに変換するためのアダプタだが、CL-STL では全てが関数のかたちに集約されているから、意味をなさないのだ。それでも CL-STL に用意されているのは、表記レベルでの互換性のため。変な理由だね。

では続きをやっていこう。Effective STL では、ループの自作よりもアルゴリズム呼び出しの方が優れている、と書いている。その理由として3つが挙げられている。

‥‥‥まぁ個人的には反論の余地はないのだけれど、それで終わってしまってはちょっと寂しいので、とにかく説明を簡単にでも見ていこう。効率に関しては、例えば前述の以下のコードにおいて、lw.end() の呼び出しをループの度にやるのは無駄だと書かれている。

for( list<Widget>::iterator i = lw.begin(); i! != lw.end(); ++i ) {
    i->redraw();
}

 

これに対して for_each を呼び出すやり方ではたしかに1回だ。まぁそうだよね。こういった小さな効率の違いの他、アルゴリズムでは「(時に非常に)高度な実装」が使われているからという理由、および、「ライブラリの実装詳細に関する知識を利用した最適化」の存在も理由として挙げられている。これについては、STL の実装を読み解きながら CL-STL を作っている立場から言わせてもらおう。これは事実だ。特にアルゴリズムは、正直自分の頭では考え出せないと認めざるをえない実装が沢山あって勉強になった。本当だってば。

では次に正確さの話に移ろう。例として、「配列の要素を反復して、41 を足しつつ deque の先頭に入れていく」というお題が挙げられている。最初に、明示的ループで先頭に insert していくコードが提示される。

size_t fillArray( double* pArray, size_t arraySize );
double data[maxNumDoubles];

deque<double> d;
//...
size_t numDoubles = fillArray( data, maxNumDoubles );
for( size_t i = 0; i < numDoubles; ++i ) {
    d.insert( d.begin(), data[i] + 41 );
}

 

問題は、結果が配列のシーケンスとは逆順になってしまうという点だ。こいつを CL-STL でも書いておこう。実際に結果を見られるようにしたので、ちょっとコードは長い。

(let* ((data #(1.1 2.2 3.3 4.4 5.5))
       (num-doubles 5)
       (d    (new stl:deque #{0 1 2})))
  (do ((i 0 (1+ i)))
      ((not (< i num-doubles)) nil)
    (stl:insert d (stl:begin d) (+ 41 (aref data i))))
  (stl:for (v d)
    (print v)))

;=> 46.5 
;   45.4 
;   44.3 
;   43.2 
;   42.1 
;   0 
;   1 
;   2 

 

で、これを改善しようとして「未定義の動作」をさせてしまうコードが提示されているのだが、それは(面倒なので)ここでは取りあげない。それを解決したコードとしてさらに提示されているのが以下だ。

deque<double>::iterator insertLocation = d.begin();
for( size_t i = 0; i < numDoubles; ++i ) {
    isnertLocation = d.insert( isnertLocation, data[i] + 41 );
    ++insertLocation;
}

 

えぇと、挿入先の反復子を保持ししつつ insert をコールしたらその結果を受け取ってさらにインクリメントという、まぁ率直にいって面倒なことをやっている。しかし、反復子無効化の規則を考えればこれが正しい。まったく正しい。これも CL-STL で書いておこう。

;; 
(let* ((data        #(1.1 2.2 3.3 4.4 5.5))
       (num-doubles 5)
       (d           (new stl:deque #{0 1 2}))
       (ins-pos     (stl:begin d)))
  (do ((i 0 (1+ i)))
      ((not (< i num-doubles)) nil)
    (setf ins-pos (stl:insert d ins-pos (+ 41 (aref data i))))
    (_++ ins-pos))
  (stl:for (v d)
    (print v)))

;=> 42.1 
;   43.2 
;   44.3 
;   45.4 
;   46.5 
;   0 
;   1 
;   2 

 

‥‥‥で、これを一発でエレガントにやってくれるのが transform というわけだ。以下のコードが提示されている。

transform( data, data + numDoubles,
           inserter( d, d.begin() ), bind2nd( plus<double>(), 41 ) );

 

これを CL-STL で書くと以下のようになる。配列のポインタ取得を簡単に書くため、CL-OPERATOR の with-operators マクロを使用している。

(with-operators
    (stl:transform &data[0] &data[num-doubles]
                   (stl:inserter d (stl:begin d)) (stl:bind2nd #'+ 41)))

 

おっと、stl:bind2nd は deprecated だった。stl:bind を使おう。ちゃんと動作するコードにすると、以下のようになる。

(let* ((data        #(1.1 2.2 3.3 4.4 5.5))
       (num-doubles 5)
       (d           (new stl:deque #{0 1 2})))
  (with-operators
      (stl:transform &data[0] &data[num-doubles]
                     (stl:inserter d (stl:begin d)) (stl:bind #'+ :1 41)))
  (stl:for (v d)
    (print v)))

;=> 42.1 
;   43.2 
;   44.3 
;   45.4 
;   46.5 
;   0 
;   1 
;   2 

 

この例について、Effective STL はこう書いている。「この例は、正しく作成することが難しい多くの種類のループを代表している。反復子が間違って操作されないか、または使い終わる前に無効化されていないか、常に注意しなければならないためである。」

それほど複雑なことをしていなければ、通常は「反復子が無効化されるタイミング」を跨いで反復子を保持したりはしないものだ。だが、ちょっと凝ったことをするとそこからはみだしてしまう。そんなとき、普段から迂闊なコーディングをしていると無効化された反復子を使って未定義の(要するにクラッシュの)世界に飛び込むことになる。だからいつだって気に留めておく必要があるのだ。

さて、こんなところだろうか。数回に分けるかもと書いたものの、ひとまず1回で終わらせることができたようだ。Effective STL のコードを CL-STL で書いてみるというシリーズもあと数回で終わりそうな感じ。次は何をやろうかな‥‥‥いや、ちゃんと終わるまではそれを考えるのはやめよう。

 

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

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


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