世界の隅の開発室

 

◎  スポンサーサイト 

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

◎  ABOUT 

【2014.3.13更新】

当ブログはJavaScript動作環境下での閲覧を推奨しています。

現役高専生の運営する開発ブログです。
開発ブログと言いながら、基本的には勉強の成果を報告する場所になるかと思います。

ある程度記事も充実したら、目録も作る予定ですのでよろしくお願いします。


開発環境 VisualStudio C++/C#、Xcode5.0
使用言語 C/C++、C#、Objective-C、JAVA(予定)
使用フレームワーク cocos2d-x



更新状況はこちらで Twitter
ソースコード等は Github

世界の隅の開発室(旧:萌ちょいブログ)

管理人 Riya@crescent



免責事項
このブログ内で公開されているソースコード、また解説などは私が作成したものですが
私自身未熟ですので、解釈ミス、ソースコードの重大な欠陥などが存在する場合があります。
このブログにおける解説・ソースコードは、その安定性、正確性や想定する全てのプラットフォームに対しての動作を保証するものでは無く
それらの指摘をして下さる方をお待ちしているのと同時に、発生し得る損害に対しては基本的に責任を負いかねます。
スポンサーサイト

◎  勉強会 資料公開 


ANCTPCCで週に一度行っている勉強会において、私が講義用に作成したプレゼン資料を公開します。
このページへのリンクはフリーです。
各資料への直リンクはご遠慮ください。

【第一回】
競技プログラマになろう!

【第二回】
貪欲法

【第三回】
ヒープ

【第四回】
ダイクストラ法

【第五回】
コンパイル時計算 実践:B-Spline曲線

【第六回】
再帰-Recursive-

【第七回】
オブジェクト指向概論

【第八回】
楽しいクソゲーのつくりかた

【第九回】
三次元描画処理概論
OpenGL ESによるiPhoneアプリ開発


【第十回】
よく分かるポインタ


3/14開催
旭川ふわっふわ勉強会

cocos2d-xでゲームプログラミング!

◎  割と汎用的なstd::tuple活用モジュールの例をいくつか 

std::tupleってなんぞ

無限個の型を持つデータ構造のいわゆるタプル(そのまま)
動的型付けにはとてもよく見られるデータ構造だが、静的型付けのC++でタプルを扱うのはとても面倒くさい。

再帰的に展開したり、メタなことしたり、そんなことにいちいち補助関数を作っていては時間と労力の無駄である。

特にライブラリアンみたいな人には、汎用的にタプルを扱う技術が必須になる、と思う。

というわけで、私がノリと勢いで作った汎用的なタプル専用の補助関数を紹介してみる。
正直どっかで想定しないコピーなどが発生してそうだけれど、まあ、こういう風にやると割とジェネリックになるよ、くらいに留めて読んでほしい。

サンプルのために用意した関数オブジェクトチルドレンと、テンプレート関数オブジェクトを紹介する。


struct A{
public:
A(int init):value(init){}
int value;
void print(){ std::cout << \"I am A, value is \" << value << std::endl; }
};

struct B{
public:
B(int init):value(init){}
int value;
void print(){ std::cout << \"I am B, value is \" << value << std::endl; }
};

struct C{
public:
C(int init):value(init){}
int value;
void print(){ std::cout << \"I am C, value is \" << value << std::endl; }
};

struct f{
template<typename T>
int operator()(T& object,int result, int n){
object.value = (object.value * n)+result;
object.print();
return object.value;
}

template<typename T>
int operator()(T& object,int n){
object.value *= n;
object.print();
return object.value;
}

};

なんか自己紹介とvalueをプリントするだけの関数オブジェクトだ。

フリー関数は、valueをn倍、またresultも受け取った場合は加算したりするものだ。ついでに型情報を自己紹介する。

さて、こいつら関数オブジェクトは同じprintメソッドを持っている。
オブジェクト同士に言語的の関係性はないが、インターフェースが共通のためダックタイピングを利用することができる。

タプルとかはそういうのが得意らしい。仕方ないので使いづらいこいつを一つ腕試ししてやろう。

前方展開

タプルのサイズをNとして
タプルの0~N-1の要素を取り出し、逐次関数にぶん投げる補助関数。


template<size_t index, size_t end, bool isEnd = index == end>
struct forwardExecute;

template<size_t index, size_t end>
struct forwardExecute<index, end, false>
{
template<typename Tuple, typename F, typename... Args>
static void Execute(Tuple&& tuple, F&& f, Args&&... args)
{
f(std::get<index>(tuple),std::forward<Args>(args)...);
forwardExecute<index+1,end>::Execute(
std::forward<Tuple>(tuple),
std::forward<F>(f),
std::forward<Args>(args)...
);

}
};

template<size_t index, size_t end>
struct forwardExecute<index, end, true>
{
template<typename Tuple, class F, typename... Args>
static void Execute(Tuple&& tuple, F&& f, Args&&... args)
{
//end
}
};

template< std::size_t begin, std::size_t end,typename Tuple, typename F,typename... Args>
void forwardExecuteApply(Tuple&& tuple, F&& f, Args&&... args)
{
forwardExecute<begin, end>::Execute(
std::forward<Tuple>(tuple),
std::forward<F>(f),
std::forward<Args>(args)...
);
}


割とよくあるイディオムだとは思う。
データ構造から関数から引数までテンプレートなため、まぁ汎用的と言える。

使ってる技術はC++11ではメジャーなものだ。
1. 可変長引数テンプレート
2. ムーブセマンティクス

この辺りはたぶんここで説明するより、C++erたちのブログを見た方が早い。

使ってみる。


int main(){
A a(1);
B b(2);
C c(3);

auto tuple = std::make_tuple(a,b,c);

forwardExecuteApply<0,3>(tuple,f(),2);

return 0;
}


実行結果

I am A, value is 2
I am B, value is 4
I am C, value is 6

全部に引数の2がかけられて、forwardに展開されている。

二分展開


template<size_t begin, size_t end, bool isEnd = begin + 1 == end>
struct partExecute;

template<size_t begin, size_t end>
struct partExecute<begin, end, true>
{
template<typename Tuple, typename F, typename... Args>
static void Execute(Tuple && tuple, F&& f, Args&&... args)
{
f(std::get<begin>(tuple),std::forward<Args>(args)...);
}
};

template<size_t begin, size_t end>
struct partExecute<begin, end, false>
{
template<typename Tuple, typename F, typename... Args>
static void Execute(Tuple&& tuple, F&& f, Args&&... args)
{
partExecute<begin, (begin + end) / 2>::Execute
(std::forward<Tuple>(tuple), std::forward<F>(f), std::forward<Args>(args)...);

partExecute<(begin + end) / 2, end>::Execute
(std::forward<Tuple>(tuple), std::forward<F>(f), std::forward<Args>(args)...);
}
};

template<std::size_t begin, std::size_t end,typename Tuple, typename F, typename... Args>
void partExecuteApply(Tuple&& tuple, F&& f, Args&&... args)
{
partExecute<begin, end>::Execute(
std::forward<Tuple>(tuple),
std::forward<F>(f),
std::forward<Args>(args)...
);
}

プログラム停止性問題?
なんかそんな感じの問題が証明されているように、コンパイラはコンパイルが終わることを立証することができないため、コンパイル時再帰に制限をかけている。
C++11では16とか32とかそこらへんだった気がするが、そんなちっこい値だと非常に困るので、二分再帰してやることにする。
こうするとlog2(N)しか再帰しなくなるので、よほど大きくなければだいたい処理できる。

二分再帰をしているところを、適当に並列化すれば速度も向上させることができる。
ただし、それには並列化の条件を満たしている必要がある。

前方展開と特に変わったことはしてない。

実行してみる。


int main(){
A a(1);
B b(2);
C c(3);

auto tuple = std::make_tuple(a,b,c);

partExecuteApply<0,3>(tuple,f(),2);

return 0;
}


実行結果

I am A, value is 2
I am B, value is 4
I am C, value is 6

再帰展開


/* recursive and propagate return value. */
template<std::size_t index>
struct propagationTuple{
template<class Tuple, class F, class R,typename... Args>
static auto Execute(Tuple&& tuple,
F&& f,
R&& result,
Args&&... args){
return propagationTuple<index-1>::Execute(std::forward<Tuple>(tuple),
std::forward<F>(f),
std::forward<F>(f)(std::get<index>(tuple),
std::forward<Args>(args)...,
std::forward<R>(result)
),
std::forward<Args>(args)...
);
}
};

template<>
struct propagationTuple<0>{
template<class Tuple,class F, class R,typename... Args>
static auto Execute(Tuple&& tuple,
F&& f,
R&& result,
Args&&... args)
{
return std::forward<F>(f)(std::get<0>(tuple),std::forward<Args>(args)...,std::forward<R>(result));
}
};

template<std::size_t index,class Tuple, class F, typename... Args>
auto propagationTupleApply(Tuple&& tuple,F&& f, Args&&... args){
return propagationTuple<index-1>::Execute(std::forward<Tuple>(tuple),
std::forward<F>(f),
std::forward<F>(f)(std::get<index>(tuple),std::forward<Args>(args)...),
std::forward<Args>(args)...
);
}


使った技術
1. expression型推論(decltype)
2. 関数返り値推論
3. タプルのサイズとったりとか参照外したりみたいなメタ関数

_tがついてるメタ関数はテンプレートエイリアスによって::typeが省略されたものだ。
C++14から追加されている。最the高。

はぁ、私はただ後方展開しつつ、計算結果を伝播していくモジュールを作りたかっただけなのにどうしてこうなった...

ま、まぁこういうコードは大概ブラックボックス化するし、多少はね?

実行してみる。


int main(){

A a(1);
B b(2);
C c(3);

auto tuple = std::make_tuple(a,b,c);

std::cout << backPropagationApply(tuple,f(),2) << std::endl;

return 0;
}

実行結果

I am C, value is 6
I am B, value is 10
I am A, value is 12
12

n倍されかつ、結果が後方伝播し加算されている。
A*2 + B*2 + C*2といった感じ。

まぁ、それっぽく動いてるんじゃなかろうか。

ここまではあくまで実装のサンプルで、これらが万能ということでは決してない。
つまり総合的に何が言いたいかというと、テンプレート特殊化と可変長引数テンプレートあたりをうまく使えば、ジェネリックなタプル活用コードか書けるってこと。

このクソコードを見て吐き気を催してしまった方は是非添削をお願いしたいものだ。
自分自身リファクタリングとインデントを放り投げるくらい面倒になった。反省。

◎  静的ポリモーフィズムの安全で簡単な実装 -動的から静的にしてパフォーマンス向上- 

動的ポリモーフィズムの確認



C++はオブジェクト指向言語です。
当然、オブジェクト指向の要素「ポリモーフィズム」を、言語仕様としてサポートしています。

C++では一般にポリモーフィズムは「動的ポリモーフィズム」を指し、実行時に基底クラスから派生クラスへと振る舞いを変化させます。


#include<iostream>

class Base{
public:
virtual void print(){ std::cout << \"Base\" << std::endl; }
virtual ~Base()=default;
};

class Super : public Base{
public:
void print() override{ std::cout << \"Super\" << std::endl; }
};

int main(){
Base* array[2] = {new Base,new Super} ;
array[0]->print();
array[1]->print();
delete array[0]; delete array[1];
return 0;
}


このプログラムを実行すると
Base
Super
と出力されます。

Baseポインタで管理されているインスタンスですが、片方の実体はその継承クラスSuperであるため、virtualで定義された仮想関数の機能によりSuperのprint()が実行されます。

このように、Base*ポインタとして扱われているインスタンスが、実際の仮想関数呼び出し時に本来の姿を取り戻すこの性質を動的ポリモーフィズムと呼びます。
動的ポリモーフィズムのデメリット

このように、とても強力な動的ポリモーフィズムですが、欠点も多くあります。

代表的なものとして、スタックの圧迫、関数呼び出しのオーバーヘッドの増加、インライン展開が不可能、などが挙げられます。

というのも、C++がこの動的ポリモーフィズムを実装するために使っているvtableが原因なのです。
これは仮想関数のポインタ解決を行うためのテーブルで、各インスタンスはそのテーブルを保持し、そのテーブルから仮想関数の呼び出しをする機構になっています。

各インスタンスが関数ポインタテーブルを持つことでスタックを圧迫し、
関数ポインタテーブルで関数を間接参照することでオーバーヘッドが生じ、
終いの果てには実行時まで呼び出す関数が分からないためにインライン展開ができなくなる、というパフォーマンスに関する多くのディスアドバンテージを抱えてしまいます。

これを解決するために、多くのC++ユーザは動的ではない静的なポリモーフィズムでの実装を推奨しています。
つまり、コンパイル時に呼び出す関数を解決するのです。

まぁ、テンプレートを使うんですけど。
静的ポリモーフィズムの実装

継承ではなくテンプレートを使うだけです。


#include<iostream>

class myclass1{
public:
void print(){ std::cout << \"myclass1\" << std::endl; }
};

class myclass2{
public:
void print(){ std::cout << \"myclass2\" << std::endl; }
};

template<class T>
class Printer{
T obj;
public:
void print(){
obj.print();
}
};

int main(){
Printer<myclass1> a;
Printer<myclass2> b;

a.print();
b.print();

return 0;
}


非常に簡単ですが、色々と問題があります。

まず、動的ならばできるはずの、一つの配列で複数の種類のインスタンスを管理することができません。
テンプレートはクラスを自動で展開しているだけなので、Printer<myclass1>とPrinter<myclass2>は完全に別のクラスですから。

また、このままだとテンプレート引数は何を渡していいのか分かりません。
こういった場合変なクラスを渡してしまい読み辛いエラーが返ってきたりします。

継承をうまく使って「インターフェースの共通化」を行い、ついでにちょこっとメタなことをして「変なクラスを弾く」ようにしてみましょう。


#include<iostream>

template<class T>
class _Printer; //prototype

template<class T>
class Interface; //prototype

template<bool is_base,class T>
struct Dummy;

template<class T>
struct Dummy<true,T>{ // T is extends Interface<T>
using type = _Printer<T>;
};

template<class T>
using Printer = typename Dummy<std::is_base_of<Interface<T>,T>::value,T>::type;

template<class T>
class Interface{
public:
void print(){ static_cast<T &>(this)->print(); }
};

class myclass1 : Interface<myclass1>{
public:
void print(){ std::cout << \"myclass1\" << std::endl; }
};

class myclass2 : Interface<myclass2>{
public:
void print(){ std::cout << \"myclass2\" << std::endl; }
};

class myclass3{
void print(){ std::cout << \"myclass3\" << std::endl; }
};

template<class T>
class _Printer{
T _obj;
public:
void print(){ _obj.print(); };
};

int main(){

Printer<myclass1> a;
Printer<myclass2> b;

//Printer<myclass3> c; //compile error

a.print();
b.print();

return 0;
}


Interfaceクラスを継承する際、動的で良いのなら純粋仮想関数を定義するところですが
ここでは、テンプレート引数でキャストしたthisポインタに定義したいインターフェース呼び出しをしています。

これによりインターフェースクラスとしての性質を持つことができます。

このインターフェースクラスのテンプレート引数は、継承したクラス自身の型で、コードを見れば分かりますが

class myclass1 : Interface<myclass1>{
///

のように宣言します。

そして、myclass1と2を静的ポリモーフィズムで扱うことができます。

また、myclass3のようなインターフェースは同一でもInterfaceクラスを継承していない不正なクラスを弾くために、メタ関数とstd::is_base_ofを使っています。

テンプレートエイリアスをかけてDummyメタ関数をクッションするようにし、テンプレート引数Tの型がInterfaceを継承しているかどうかを検査します。

もしstd::is_base_ofの結果がtrueならば、特殊化テンプレート最優先の規則に従い、trueで特殊化されたDUMMYが展開されます。
逆に、falseだった場合(継承していない場合)、未定義のテンプレートクラスを展開しようとするため、エラーを吐きます。

Dummyが無事展開されれば、Dummyは隠蔽した_Printerクラスをtypedefし、無事テンプレートエイリアスのPrinterは目的のクラスのシンボルとなります。

こんな感じでしょうか。

全体的に、テンプレートに理解があればそんなに難しくはないと思いますが、一方その恩恵はかなり大きいので、もし動的から静的へ置換可能である場合には是非試してみると良いと思います。

残念ながら、動的ポリモーフィズムの特徴の一つ、基底ポインタで複数の派生クラスインスタンスを扱うのと同じことを、静的に行う方法は分かりませんでした。

多分無理かな? わかりません、C++は奥が深いですからね。

では。


back to TOP

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。