フィボナッチ数列
デバッグとチューニングのお話の前に、おさらいを兼ねてフィボナッチ数列の第n項:fib(n)を求めるサンプルを書いてみましょうか。フィボナッチ数列:0,1,1,2,3,5,8...の第n項:fib(n)は、以下のように再帰的に定義されます。
fib(0) = 0 fib(1) = 1 fib(n) = fib(n-1) + fib(n-2) if n > 1
この定義に忠実にCnCで実装します。上記の定義をそのままstep内で求め、得られた結果をn番目のitemに出力するとしましょう。step内の処理は：
switch ( n ) {
case 0: itemのn番目に 0 をputする
case 1: itemのn番目に 1 をputする
default:
itemのn-1番目をgetする
itemのn-2番目をgetする
ふたつを加えてitemのn番目にputする
}
となります。このstepを0,1,...nで着火すればitemのn番目にfib(n)が求まります。
CnCのチュートリアルには、こんなコードが示されていました。
list01
// 実害のない warning を抑止する
#define _CRT_SECURE_NO_DEPRECATE
#include <cnc/cnc.h>
#include <cnc/debug.h> // デバッグのために追加
// フィボナッチ数 に十分な大きさの型
typedef unsigned long long fib_type;
// forward declaration
struct fib_context;
// フィボナッチ数を求める step
struct fib_step {
// declaration of execute method goes here
int execute( const int & tag, fib_context & c ) const;
};
// コンテキスト: tag/step/itemの集合およびそれらの依存関係を束ねる
struct fib_context : public CnC::context< fib_context > {
CnC::step_collection< fib_step > m_steps;
CnC::item_collection< int, fib_type > m_fibs;
CnC::tag_collection< int > m_tags;
// コンストラクタ
fib_context();
};
fib_context::fib_context()
: CnC::context< fib_context >(),
m_steps( *this ),
m_fibs( *this ),
m_tags( *this ) {
m_tags.prescribes( m_steps, *this ); // m_tags は m_step に指示する
m_steps.consumes( m_fibs ); // m_steps は m_fibs を消費する
m_steps.produces( m_fibs ); // m_steps は m_fibs を生産する
}
// フィボナッチ数列の第tag項を求める
int fib_step::execute( const int & tag, fib_context & ctxt ) const {
switch ( tag ) {
case 0 : // fib(0) = 0
ctxt.m_fibs.put( tag, 0 ); break;
case 1 : // fib(1) = 1
ctxt.m_fibs.put( tag, 1 ); break;
default : // fib(n) = fib(n-1) + fib(n-2)
// 前の二つを手に入れて
fib_type f_1; ctxt.m_fibs.get( tag - 1, f_1 );
fib_type f_2; ctxt.m_fibs.get( tag - 2, f_2 );
// 加えたものが結果となる
ctxt.m_fibs.put( tag, f_1 + f_2 );
}
return CnC::CNC_Success;
}
int main( int argc, char* argv[] ) {
int n = 42;
// eval command line args
if ( argc < 2 ) {
std::cerr << "usage: " << argv[0] << " n\nUsing default value " << n << std::endl;
} else {
n = atol( argv[1] );
}
// コンテキストを生成し
fib_context ctxt;
// tagをputして
for( int i = 0; i <= n; ++i ) ctxt.m_tags.put( i );
// 終了を待ち
ctxt.wait();
// 結果を取得して
fib_type res2;
ctxt.m_fibs.get( n, res2 );
// 出力する
std::cout << "fib (" << n << "): " << res2 << std::endl;
return 0;
}
