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

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

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

最終更新日付:2015/11/03 22:54:14


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

2015 年 11 月 03 日

今回はアルゴリズムの話の最後。結構大物だ。第37項、「範囲に関する要約情報を取得するには、accumulateまたはfor_eachを使おう」をやってみよう。今回は、初めてファンクタクラスを作成する。次回以降はファンクタの話になるので、一足先にうんざりして頂けることと思う(何言ってる)。

さて、書籍では、最初に accumulate が紹介される。明示的な指定がなければ、operator+ で範囲を要約するものだ。それを要約と呼ぶものかな、という気はするけれど、そもそも accumulate というのは本来「蓄積する」という意味なので、そちらの方にマッチしているな。

list<double> ld;
//...
double sum = accumulate( ld.begin(), ld.end(), 0.0 );

 

とりあえず、ごちゃごちゃ言わずに CL-STL で書いてみることにしよう。以下のようになる。ちなみに、CL-STL ではデフォルトで #'operator_+ が使用される。

* (let ((ld (new stl:list #{1.2 3.4 5.6 7.8 9.0})))
    (stl:accumulate (stl:begin ld) (stl:end ld) 0.0))

;=> 27.0

 

続いて、要約のための関数を明示的に指定する話に移る。書籍では、関数 stringLengthSum が提示され、これを使ってシーケンスに含まれる文字列の長さの総和を求めている。

string::size_type stringLengthSum( string::size_type sumSoFar, const string& s ) {
    return sumSoFar + s.size();
}

set<string> ss;
//...
string::size_type lengthSum = accumulate( ss.begin(), ss.end(), 0, stringLengthSum );

 

これも CL-STL で書いてみよう。これもまぁ同じように書ける。

(defun string-length-sum (sum-so-far s)
  (+ sum-so-far (length s)))

(let ((ss (new stl:set #{"foo" "bar" "foobar" "quux" "gbh"} #'string<)))
  (stl:accumulate (stl:begin ss) (stl:end ss) 0 #'string-length-sum))

;=> 19

 

とはいえアレだ。わざわざ関数を明示的に作成するまでもない。ラムダ式で片付く話だ。以下のように。

(let ((ss (new stl:set #{"foo" "bar" "foobar" "quux" "gbh"} #'string<)))
  (stl:accumulate (stl:begin ss) (stl:end ss) 0
                  (lambda (acc s)
                    (+ acc (length s)))))

;=> 19

 

さぁ,ここから面倒な話になる。シーケンスの要素が「点」を表すオブジェクトで、シーケンスに含まれる点の座標の平均を求めるんだそうだ。そのためのファンクタクラス PointAverage を後回しにすれば、まずはこうなるそうだ。

struct Point {
    Point( double initX, double initY ) : x( initX ), y( initY ) {}
    double x, y;
};

list<Point> lp;
//...
Point avg = accumulate( lp.begin(), lp.end(),
                        Point( 0, 0 ), PointAverage() );

 

そして、クラス PointAverage はこうなんだそうだ。

class PointAverage : public std::binary_function<Point, Point, Point> {
public:
    PointAverage() : xSum( 0 ), ySum( 0 ), numPoints( 0 ) {}
    const Point operator()( const Point& avgSoFar, const Point& p ) {
        ++numPoints;
        xSum += p.x;
        ySum += p.y;
        return Point( xSum / numPoints, ySum / numPoints );
    }
private:
    size_t numPoints;
    double xSum;
    double ySum;
};

 

‥‥‥で、これを同じように CL-STL で書いてみましょうということなんだけれど、正直めんどい。特に、ファンクタを正直にクラスとして実装するのがめんどい。でもある程度はちゃんと書こうと決めたのだから頑張ることにしよう。

まずは構造体として point を作成する。その作成を簡単にするための関数 new-point も用意しておこう。

(defstruct point x y)
(defun new-point (x y) (make-point :x x :y y))

 

で、呼び出す度にそれまでの point の平均を算出して返すファンクタ、point-average を作成しよう。まずは stl:functor から派生したクラスを作成する。

(defclass point-average (stl:functor)
  ((num-points :initform 0 :accessor pt-avg-num-points)
   (x-sum      :initform 0 :accessor pt-avg-x-sum)
   (y-sum      :initform 0 :accessor pt-avg-y-sum)))

 

で、このクラス point-average のためのコンストラクタやメソッドを作成するわけだ。CL-OPERATOR の new でコンストラクトできるようにするために、declare-constructordefine-constructor を使用する。そして、これまた CL-OPERATOR の operator_clone を実装する。

(declare-constructor point-average (0))

(define-constructor point-average ()
  (let ((obj (make-instance 'point-average)))
    (setf (stl::__functor-closure obj)
          (lambda (avg-so-far p)
            (declare (ignore avg-so-far))
            (incf (pt-avg-num-points obj))
            (incf (pt-avg-x-sum obj) (point-x p))
            (incf (pt-avg-y-sum obj) (point-y p))
            (new-point (/ (pt-avg-x-sum obj) (pt-avg-num-points obj))
                       (/ (pt-avg-y-sum obj) (pt-avg-num-points obj)))))
    obj))

(defmethod operator_clone ((obj point-average))
  obj)

 

本当は operator_clone の実装はもっと面倒臭い。後日説明する理由により「ファンクタを値渡し」可能にするためのコードが必要なのだ。だが今回は本筋から外れるため単純なかたちにしておいた。

一方、クラスの define-constructor がなんだか面倒臭い感じになっていると感じる方が多いだろう(まだ読んでくれていればだけど)。今回は細かい説明はしないので、「なんだかめんどい」ということがわかって頂ければ十分。これでもって point のシーケンスの平均を取るべく、accumulate を呼んでみよう。以下のようになる。

(let ((lp (new stl:list #{(new-point 1 5)
                          (new-point 2 6)
                          (new-point 3 7)
                          (new-point 4 8)})))
  (stl:accumulate (stl:begin lp) (stl:end lp)
                  (new-point 0 0) (new point-average)))

;=> #S(POINT :X 5/2 :Y 13/2)

 

ふぅ、上手く動いているようだ。ただし、書籍によれば前述の C++ コードは標準の要求から外れているため、厳密には「未定義の領域にある」のだそうだ。理由は、accumulate に渡すファンクタは独自の状態や副作用を持つことが禁じられているかららしい。そこはもう「へぇ‥‥‥」というほかない。そこで続いて提示されるのが、これまた定かでない理由によりそのような制約がない for_each を使う方法だ。

struct Point {
    Point( double initX, double initY ) : x( initX ), y( initY ) {}
    double x, y;
};

class PointAverage : public std::unary_function<Point, void> {
public:
    PointAverage() : xSum( 0 ), ySum( 0 ), numPoints( 0 ) {}
    void operator()( const Point& p ) {
        ++numPoints;
        xSum += p.x;
        ySum += p.y;
    }
    Point result() const {
        return Point( xSum / numPoints, ySum / numPoints );
    }
private:
    size_t numPoints;
    double xSum;
    double ySum;
};

list<Point> lp;
//...
Point avg = for_each( lp.begin(), lp.end(),PointAverage() ).result();

 

先程と異なる点は、PointAverageunary_function 派生になったこと、それによって operator() のパラメータが単独になったこと。そして内部的に蓄積される平均値を取得するための result メソッドが追加されたことだ。

輪をかけて面倒臭いが、ここはひとつ頑張ろう。先程の point-average のコンストラクタを変更する。というか、差分で提示するとワケがわからなくなるかもしれないので、それ以外も再提示する。

(defstruct point x y)
(defun new-point (x y) (make-point :x x :y y))

(defclass point-average (stl:functor)
  ((num-points :initform 0 :accessor pt-avg-num-points)
   (x-sum      :initform 0 :accessor pt-avg-x-sum)
   (y-sum      :initform 0 :accessor pt-avg-y-sum)))

(define-constructor point-average ()
  (let ((obj (make-instance 'point-average)))
    (setf (stl::__functor-closure obj)
          (lambda (p)
            (incf (pt-avg-num-points obj))
            (incf (pt-avg-x-sum obj) (point-x p))
            (incf (pt-avg-y-sum obj) (point-y p))
            nil))
    obj))

(defmethod operator_clone ((obj point-average))
  obj)

(defun result (pt-avg)
  (new-point (/ (pt-avg-x-sum pt-avg) (pt-avg-num-points pt-avg))
             (/ (pt-avg-y-sum pt-avg) (pt-avg-num-points pt-avg))))

 

CL-STL 側のコードは 0x11 前提なので、binary-function やら unary-function やらが登場しないが、それ以外は基本的には同じコードだ。実行してみよう。

(let ((lp (new stl:list #{(new-point 1 5)
                          (new-point 2 6)
                          (new-point 3 7)
                          (new-point 4 8)})))
  (result (stl:for-each (stl:begin lp) (stl:end lp) (new point-average))))

;=> #S(POINT :X 5/2 :Y 13/2)

 

ふぅ‥‥‥一応ご注文通りということになる。とはいえ、これだけでは話は終わらない。実際問題として、この例に関して言えば点を構造体、ファンクタをクラスとして実装する理由はないからだ。よほどの理由がない限り、おそらく点はコンスセルで十分だし、ファンクタはラムダ式で十分だろう。そのコードを示したいと思ったのだが、残念ながら今日は力尽きた。続きはまた次回にしたいと思う。

 

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

 

コメント

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

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


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