« クラスの生成と廃棄を考える 其の5 | トップページ | 配置new(placement new)を使ってみた 其の1 »

2009年8月26日 (水)

疑似乱数を調べていたら、Strategy(ストラテジ)パターンがでてきた

最近、読んだ本のなかに、疑似乱数生成法に『XorShift法』というものが紹介されていました。この『XorShift法』は、Xorとシフト演算のみで疑似乱数を生成するため、処理が軽いという特徴があります。また、周期やランダム性をとっても、十分実用レベルだそうです。疑似乱数といえば、質と速度には定評のある『メルセンヌツイスター法』が有名ですが、これと比較して、処理速度がどのくらいなのか調べてみました。あと、おまけで、標準関数のrand()も。

Opteron 1.8GHz + Visual Studio 2008上で1000万回生成の処理時間(100回計測して、その平均をとっています)を計測した結果、以下のようになりました。

方法処理時間(ms)
XorShift98.57
メルセンヌツイスター203.47
標準関数rand()483.59

ということで、XorShift法が一番速いという結果になりました。ゲームプログラミングなど速度が重視されるようなものに、最適ではないでしょうか。

さて、処理時間を調べるため、プログラムをごりごり書いていたら、デザインパターンのStrategyパターンが出てきましたので、紹介いたします。Strategyパターンは、アルゴリズムの交換を可能にするものです。アルゴリズムを交換する、いったいどういうことでしょうか。

それでは、まず、計測に使ったプログラムの一部を示します。

    random_xor rand_xor;    /* XorShift */
    random_std rand_std;    /* 標準 */
    random_mt  rand_mt;      /* メルセンヌツイスター */
    random* rand_array[] = { &rand_xor, &rand_std, &rand_mt };
    for( int i=0; i<3; i++ ) {
        random* rand = rand_array[i];
        /* ----- 計測 ----- */
        for( int n=0; n<100; n++ ) {
            for( int nn=0; nn<10000000; nn++ ) {
                rand->generate();
            }
        }
    }

random_xor、random_std、random_mtはそれぞれ、XorShift法疑似乱数生成クラス、標準関数疑似乱数生成クラス、メルセンヌツイスター法疑似乱数生成クラスです。6行目のところでクラスを交換して、各方法の疑似乱数を生成しています。

つまり、このプログラムでは、疑似乱数生成アルゴリズムの交換を行っています。このようにアルゴリズムの交換を可能にする仕掛けをStrategyパターンと呼びます。

では、Strategyパターンを取り入れた、疑似乱数クラスはどうなっているのでしょうか。下記にヘッダー部を示します。

/* ----- 基底クラス ----- */
class random {
public:
    random() {}
    virtual ~random() {}
public:
    virtual int generate( void ) = 0;
};  /* class */

/* ----- XorShift法クラス ----- */
class random_xor : public random {
public:
    random_xor( void );
    virtual ~random_xor();
public:
    virtual int generate( void );
};  /* class */

/* ----- 標準関数クラス ----- */
class random_std : public random {
public:
    random_std();
    virtual ~random_std();
public:
    virtual int generate( void );
};  /* class */

/* ----- メルセンヌツイスター法クラス ----- */
class random_mt : public random {
public:
    random_mt();
    virtual ~random_mt();
public:
    virtual int generate( void );
};

まず、基底クラスにて入れ替えを可能にするメンバ関数(上記のソースでは、generate()関数が該当します)を定義します。あとは、基底クラスを派生してクラスを生成し、メンバ関数を実装すれば完了です。なんだか、ポリモーフィズムやらで知らず知らずの内に使っているようなパターンですね。

今回はここまで!

|

« クラスの生成と廃棄を考える 其の5 | トップページ | 配置new(placement new)を使ってみた 其の1 »

プログラミング」カテゴリの記事

C++」カテゴリの記事

デザインパターン」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: 疑似乱数を調べていたら、Strategy(ストラテジ)パターンがでてきた:

« クラスの生成と廃棄を考える 其の5 | トップページ | 配置new(placement new)を使ってみた 其の1 »