C++でC風ライブラリを作る（疑似乱数編）
高木です。おはようございます。
ここのところずっと<stdlib.h>で宣言されている関数の焼き直しを行っています。
当面はこの流れを続けていきたいと思いますので、今回もその方針でいきます。
今回作るのは疑似乱数を生成する関数です。
Cの標準ライブラリにはrand関数というのがあります。
また、疑似乱数の種を設定するためのsrand関数もあります。
処理系によりますが、rand関数は線形合同法というごく単純なアルゴリズムを使っているケースが多く、決して性能がよいとはいえません。
高性能な疑似乱数生成のアルゴリズムといえばメルセンヌツイスタということになりますね。
ただ、メルセンヌツイスタは計量とはいえませんので、ちょっと乱数を使いたい、あるいは大量の乱数を発生させたい場合には負荷が大きすぎるかもしれません。
そこで、ちょうどよい疑似乱数生成アルゴリズムとして、今回はXorshiftを採用することにします。
Cのrand関数の不便なところは、内部状態を参照することができないことです。
カプセル化の観点からすれば、内部状態を参照できない方がよいという考えもあるのですが、状態を保存、再開できないのは大きなデメリットになります。
そこで、今回は内部状態を関数の外で管理する設計に変更したいと思います。
ただし、Cのrand関数同様、内部状態を意識しなくても使えるようにもします。
それでは実際のコードを紹介していくことにします。
まずは内部状態を定義する構造体からです。
1 2 3 4 5 6 7 8 9 10 | namespace cloverfield { struct rand_state_t { std::uint_least32_t x = 123456789; std::uint_least32_t y = 362436069; std::uint_least32_t z = 521288629; std::uint_least32_t w = 88675123; }; } |
32ビットの整数値を4つ用いて128ビットの内部状態を保持します。
仮の初期値も与えておきます。
randおよびsrand関数にはrand_state_t型へのポインタを明示的に渡すようにしたいと考えていますが、省略した場合にはデフォルトのオブジェクトを使用できるようにします。
通常であれば、内部結合のオブジェクトを用意して使用することになるのですが、極力ヘッダファイルをインクルードできるようにしたいので、今回は別の方法を採用します。
つまり、ヘッダファイルの中でデ内部状態を表すデフォルトのオブジェクトを定義してしまいます。
といっても、単一定義規則に反するような定義はできません。
C++14であればインライン変数が使えるのですが、今回のライブラリではC++11を使っていますので、それも無理です。
結局、次のように関数内で静的にrand_state_t型のオブジェクトを定義して、そのポインタを返すインライン関数を用意することにしました。
1 2 3 4 5 6 7 8 9 10 11 | namespace cloverfield { namespace detail { inline rand_state_t* default_rand_state() { static rand_state_t state; return &state; } } } |
ここまで来れば、あとはXorshiftのアルゴリズムを実装するだけです。
1 2 3 4 5 6 7 8 9 10 11 12 | namespace cloverfield { inline std::uint_least32_t rand(rand_state_t* state = detail::default_rand_state()) { auto t = (state->x ^ (state->x << 11)); state->x = state->y; state->y = state->z; state->z = state->w; state->w = (state->w ^ (state->w >> 19)) ^ (t ^ (t >> 8)); return state->w; } } |
疑似乱数の種はrand_state_t型のオブジェクトに直接設定してもよいのですが、4つも値があって面倒ですので、srand関数も用意しておきましょう。
1 2 3 4 5 6 7 8 9 10 | namespace cloverfield { inline void srand(std::uint_least32_t seed, rand_state_t* state = detail::default_rand_state()) { state->x = 1812433253u * (seed ^ (seed >> 30)); state->y = 1812433253u * (state->x ^ (state->x >> 30)) + 1; state->z = 1812433253u * (state->y ^ (state->y >> 30)) + 2; state->w = 1812433253u * (state->z ^ (state->z >> 30)) + 3; } } |
ここでちょっとした疑問が湧いてくるかもしれませんね。
今回の実装ではマルチスレッドに何ら配慮していません。
要するにスレッドセーフになっていないのです。
スレッドセーフにすること自体は難しくありませんが、極力軽量な疑似乱数生成関数を作りたいという趣旨に反します。
また、スレッドセーフにするにしても、大きく分けて方法が2つあります。
ひとつは排他制御を行う方法であり、もうひとつはスレッドローカルストレージを使う方法です。
それぞれに一長一短があるので、どちらかに決めてしまうのもよくありません。
そういうことで、マルチスレッド対応はクライアントコード側で好きに行う方針を採用することにしました。
大して難しいことではありませんので、それぐらいは任せてしまっても問題ないでしょう。