2010年4月29日木曜日

Bjarne 的なるもの

なんとなく first, last だのの algorithm 関数のインターフェースが好きになれなくて、せいぜい vector<T> をベター配列ぐらいでしか使ったことなかったけれど、今頃になって STL で真面目に遊ぶ。 C++0x? Boost? 何それうまいの?

For each 的なるものに ruby とかでブロック (ruby の用語だとイテレータ?) を渡すのに比べて、関数オブジェクトとかはクラスを宣言しなければいけないしめんどくさいなあ的なるものかと思ってたけど、その分、抽象的な処理が何か考える契機にはなるのかな。 ∀x/∃x の関数オブジェクト・ラッパーをさんざ設計してみた後で、それじゃ短絡評価されないじゃんということにやっと気づく連休初日。 なるほど find_if() とか adjacent_find() を使えと。 0x だと無名のラムダ関数的なるものを関数定義中に書けるようになるとか…。 これ以上文法を複雑にしないで。

ファンクショナル (汎関数) はまだしも関数オブジェクトをファンクター (関手) とか呼んでるのがあるのは何か違う気がする。 そういう文脈があるのだろうか。 むしろ for_each() とかの方がファンクター的なるものっぽいのだけれど。 for_each(first, last, f) の代わりに g = for_each(f); g(first, last); とかだともっといいか。 まったく需要なさそうだ。

コンテナの実体の代わりにインデックスをソートしてみるとかに使えそうな関数オブジェクト・ラッパー↓。 長たらしい。 筋は通ってるけど多重継承で同じクラスを継承する極悪っぷりなので、親切なコンパイラのウォーニングは無視する。 なんかこれも別の手段がありそうだ。

#include <functional>
#include <iterator>

// 単項関数ラッパー基底クラス
// 他のラッパー・クラスの基底となり、ラップされる関数オブジェクトを保持する
//  関数オブジェクトの呼び出し  (*this)(-): A → R
// テンプレート引数
//  A   呼び出しと F の引数型               要件 なし
//  R   呼び出しと F の返り値型 (void 可)   要件 なし
//  F   ラップされる関数の型                要件 -(-): F×A → R
//
template<typename A, typename R, typename F>
class  unary_function_wrapper_t  : public std::unary_function<A, R>
    {
    private:
        F  _wrapped_function;   // ラップされる非定数関数: 内部状態を持ち呼び出しで更新するかもしれない
        static R  _constraint_F(F f, A a)  throw ()  { return f(a); }
    public:
        explicit  unary_function_wrapper_t(F wrapped_function = F())  throw ()
            : _wrapped_function(wrapped_function) { R (* c)(F, A) = _constraint_F; }
        F const&  wrapped_function()  const throw ()  { return _wrapped_function; }
        R  operator()(A a)  { return _wrapped_function(a); }
    };

// 配列 (ランダム・アクセス・シーケンス) のインデックスを取って演算を行う
// コンストラクタの引数で A 型シーケンスのポインタまたはイテレータを与え、
// アルゴリズム関数にはその順番を示す I 型インデックスを与える
// 演算はシーケンス上の A 型の値に対して行われるが、
// アルゴリズム関数の操作はインデックスに対して行われる
//  関数オブジェクトの呼び出し  (*this)(-): I → R
// テンプレート引数
//  Aa  配列 (コンテナ) の先頭ポインタ (イテレータ) 要件 -[-]: Aa×I → A
//  R   呼び出しと F の返り値型 (void 可)           要件 なし
//  F   ラップされる関数 (オブジェクト) 型          要件 -(-): F×A → R (基底クラスより)
// 非明示型
//  A   F の引数型                                  要件 なし
//  I   呼び出しの引数型でインデックスとなる型      要件 なし
//
template<typename Aa, typename R, typename F>
class  unary_function_deindexer_t
    : public unary_function_wrapper_t<typename std::iterator_traits<Aa>::value_type, R, F>,
      public std::unary_function<typename std::iterator_traits<Aa>::difference_type, R> // 意図した多重継承
    {
    private:
        typedef typename std::iterator_traits<Aa>::value_type       A;
        typedef typename std::iterator_traits<Aa>::difference_type  I;
        Aa  _values_a;  // A 型配列 (コンテナ) への非定数ポインタ (イテレータ): このクラスの代入を可能にする
        static A  _constraint_Aa(Aa aa, I i)  throw ()  { return aa[i]; }
    public:
        explicit  unary_function_deindexer_t(Aa values_a, F wrapped_function = F())  throw ()
            : unary_function_wrapper_t(wrapped_function), _values_a(values_a)  { A (* c)(Aa, I) = _constraint_Aa; }
        Aa  values_a()  const throw ()  { return _values_a; }
        R  operator()(I i)  { return unary_function_wrapper_t::operator()(_values_a[i]); }
    };

// 2 項関数ラッパー基底クラス
//  関数オブジェクトの呼び出し  (*this)(-,-): A1×A2 → R
// テンプレート引数
//  A1  呼び出しと F の第 1 引数型          要件 なし
//  A2  呼び出しと F の第 2 引数型          要件 なし
//  R   呼び出しと F の返り値型 (void 可)   要件 なし
//  F   ラップされる関数の型                要件 -(-,-): F×A1×A2 → R
//
template<typename A1, typename A2, typename R, typename F>
class  binary_function_wrapper_t
    : public std::binary_function<A1, A2, R>
    {
    private:
        F  _wrapped_function;
        static R  _constraint_F(F f, A1 a1, A2 a2)  throw ()  { return f(a1, a2); }
    public:
        explicit  binary_function_wrapper_t(F wrapped_function = F())  throw ()
            : _wrapped_function(wrapped_function) { R (* c)(F, A1, A2) = _constraint_F; }
        F const&  wrapped_function()  const throw ()  { return _wrapped_function; }
        R  operator()(A1 a1, A2 a2)  { return _wrapped_function(a1, a2); }
    };

// 配列 (ランダム・アクセス・シーケンス) のインデックスを取って演算を行う
//  関数オブジェクトの呼び出し  (*this)(-,-): I×I → R
// テンプレート引数
//  Aa  配列の先頭ポインタ                      要件 -[-]: Aa×I → A
//  R   呼び出しと F の返り値型 (void 可)       要件 なし
//  F   ラップされる関数 (オブジェクト) 型      要件 -(-): F×A×A → R (基底クラスより)
// 非明示型
//  A   F の引数型                              要件 なし
//  I   呼び出しの引数型でインデックスとなる型  要件 なし
//
template<typename Aa, typename R, typename F>
class  binary_function_deindexer_t
    : public binary_function_wrapper_t<typename std::iterator_traits<Aa>::value_type,
                                       typename std::iterator_traits<Aa>::value_type, R, F>,
      public std::binary_function<typename std::iterator_traits<Aa>::value_type,
                                  typename std::iterator_traits<Aa>::value_type, R> // 意図した多重継承
    {
    private:
        typedef typename std::iterator_traits<Aa>::value_type       A;
        typedef typename std::iterator_traits<Aa>::difference_type  I;
        Aa  _values1_a;
        Aa  _values2_a;
        static A  _constraint_Aa(Aa aa, I i)  throw ()  { return aa[i]; }
    public:
        explicit  binary_function_deindexer_t(Aa values_a, F wrapped_function = F())  throw ()
            : binary_function_wrapper_t(wrapped_function), _values1_a(values_a), _values2_a(values_a)
            { A (* c)(Aa, I) = _constraint_Aa; }
        explicit  binary_function_deindexer_t(Aa values1_a, Aa values2_a, F wrapped_function = F())  throw ()
            : binary_function_wrapper_t(wrapped_function), _values1_a(values1_a), _values2_a(values2_a)
            { A (* c)(Aa, I) = _constraint_Aa; }
        Aa  values1_a()  const throw ()  { return _values1_a; }
        Aa  values2_a()  const throw ()  { return _values2_a; }
        R  operator()(I i1, I i2)  { return binary_function_wrapper_t::operator()(_values1_a[i1], _values2_a[i2]); }
    };

// 配列 (ランダム・アクセス・シーケンス) のインデックスを取って比較演算を行う
//  関数オブジェクトの呼び出し  (*this)(-,-): I×I → bool
// テンプレート引数
//  Aa  配列 (コンテナ) の先頭ポインタ (イテレータ) 要件 -[-]: Aa×I → A (基底クラスより)
//  F   ラップされる関数 (オブジェクト) 型          要件 -(-): F×A×A → bool (基底クラスより)
// 非明示型
//  A   F の引数型                                  要件 なし
//  I   呼び出しの引数型でインデックスとなる型      要件 なし
//
template<typename Aa, typename F>
class  comparator_deindexer_t
    : public binary_function_deindexer_t<Aa, bool, F>
    {
    public:
        explicit  comparator_deindexer_t(Aa values_a, F wrapped_comparator = F())  throw ()
            : binary_function_deindexer_t(values_a, wrapped_comparator) {}
        explicit  comparator_deindexer_t(Aa values1_a, Aa values2_a, F wrapped_comparator = F())  throw ()
            : binary_function_deindexer_t(values1_a, values2_a, wrapped_comparator) {}
    };

どういうときに使えそうかというと、例えば、うららかな春の陽気にさそわれて、ふと大量の数ベクトルを大きさの順にソートしたくなったとしよう。 ソートしたいのはベクトルなんだけど、比べたいのはその大きさ。 比較関数で比較の度にいちいち大きさを計算するのはばかばかしい。 そこで、大きさをあらかじめ計算した vector<double> を用意しておいて、0,1,2,...,n−1 に初期化したインデックス vector<size_t> も用意しておいて、比較関数は大きさの vector を参照させて、ソートはインデックスの vector に対して行う。 よくある手法だ (おそらく)。 STL でやると、大きさの代わりに絶対値の 2 乗をとる関数オブジェクトと、0,1,2,... を作るための関数オブジェクト、ついでに出力用関数オブジェクトを用意して:

#include <iostream>
#include <numeric>
#include <cstdlib>

template<typename Ka>
struct  sqabs_t  : public std::unary_function<Ka, typename Ka::value_type>
    {
        typedef typename Ka::value_type K;
        K  operator()(Ka const& ka)  { return std::inner_product(ka.begin(), ka.end(), ka.begin(), K()); }
    };

template<typename K, typename I = size_t>
class  counter_t  : public std::unary_function<K, I>
    {
    private:
        I  _count;
        static I  _constraint_I(I i)  throw ()  { return i ++; }
    public:
        explicit  counter_t(I initial_count = I())  throw ()  : _count(initial_count) { I (* c)(I) = _constraint_I; }
        I  count()  const throw ()  { return _count; }
        I  operator()(K const&)  throw ()  { return _count ++; }
    };

template<typename Ka>
struct  writer_t  : public std::unary_function<Ka, void>
    {
        typedef typename Ka::value_type K;
        void  operator()(Ka const& ka)  const
            {
                std::cout << "( ";
                std::copy(ka.begin(), ka.end(), std::ostream_iterator<K>(std::cout, " "));
                std::cout << ")\n";
            }
    };

そして、本体はこんな風になる:

#include <vector>

typedef double           Kt;
typedef std::vector<Kt>  Kat;
typedef std::vector<Kat> Kaat;
typedef size_t           It;
typedef std::vector<It>  Iat;

// ベクトルが入ったベクトルがあるとしよう
Kaat kaa;
for (size_t i = 0; i < 10; i ++) {
    Kat ka;
    ka.push_back(rand()); ka.push_back(rand()); ka.push_back(rand());
    kaa.push_back(ka);
}

//------

// 各ベクトルの絶対値の 2 乗のベクトルを用意する
Kat aa;  std::transform(kaa.begin(), kaa.end(), back_inserter(aa), sqabs_t<Kat>());

// インデックスを入れるベクトルを用意する
Iat ia; std::transform(aa.begin(), aa.end(), back_inserter(ia), counter_t<Kt, It>());

// そしてソートする。比較は aa に対して行われ、ソートは ia に対して行う
std::sort(ia.begin(), ia.end(), comparator_deindexer_t<Kat::const_iterator, std::less<Kt> >(aa.begin()));

//------

// ソートされてるかチェック
Iat::iterator p = std::adjacent_find(ia.begin(), ia.end(), comparator_deindexer_t<Kat::const_iterator, std::greater<Kt> >(aa.begin()));
std::cout << ((p == ia.end())? "good job!" : "fiasco!") << std::endl;
// ソート順にもとのベクトルを出力。ia を順に参照し、kaa を出力する
std::for_each(ia.begin(), ia.end(), unary_function_deindexer_t<Kaat::const_iterator, void, writer_t<Kat> >(kaa.begin()));

good job!
( -0.188818 -0.44084 0.137486 )
( 0.364483 0.511704 0.443831 )
( -0.0494095 -0.75396 -0.264382 )
( -0.688894 0.00784326 0.464034 )
( -0.644215 0.634388 -0.0494705 )
( 0.643361 0.164098 -0.617298 )
( 0.810236 0.385784 -0.393902 )
( 0.366375 -0.693533 0.754509 )
( -0.146886 -0.859249 0.933226 )
( -0.705008 0.899167 -0.716849 )

ふふふ、二度と読みたくないコードがまた完成した。 Bjarne 的なのか、Stepanov 的なのか、単にわたし的なのか。

2010年4月22日木曜日

とうふの角

25 度だろうが 7 度だろうが春、つぼみつけすぎのクレマチス。

* * *

コーナー・キューブ、つまり 3 次元空間で x ≥ 0, y ≥ 0, z ≥ 0 みたいな無限に巨大なとうふの 1 つの角を想像する。 この角のあたりを斜めに包丁でスパッと切ると、切り方によっていろんな三角錐ができあがる。 その切片はいろんな形の、すべての、ただし鋭角な三角形。 鈍角はどこにいったのだろう。 切り口が鈍角になるには直方体じゃなく平たくつぶれたとうふじゃないとだめそうだ。 そんなものもはやとうふではない。

飽くまで直方体の無限に大きなとうふがプリズムみたいに透明だとして、切片と真っ直ぐ垂直に向き合うなら、向こう側の 3 つの辺と角が透けて見えるはずだ。 別に切片を下にしてまな板を真上から覗き込んでもいいのだけれど。 そうして見たときの、この角の位置は平面三角形でいうところの「垂心」になっている。 つまり角から切片に垂直に下ろした足もやっぱり垂心なのだ。 透けて見える辺は三角形の頂点から下ろした垂線のはずだ。 なかなか面白いと思ったが、とうふが直方体であることを考えると別にそんなに不思議じゃない。 ちなみに、三角形の「重」心は向こう側の 3 つの辺を共有する直方体の対角線と三角形が交わる点。 これも不思議じゃない。

今度は切片に垂直ではなくとうふの直方体の角の方から [(x, x, x) から] 切片の三角形の射影を眺めると、とうふの角は「フェルマー点」だ。 外心やオイラー線はわかるようでわからない。

さてこうなると鈍角三角形も見つけたい。 鈍角三角形だと垂心が三角形の外にある。 とうふの四面体をどんな風にみたらとうふの角が外にある三角形がありうるだろうかと考えてたら、あったよ鈍角三角形。 透けて見える面に隠れていた。 かくしてみそ汁には三角のとうふが浮くのであった。