2009-11-24

C++0xの新しい乱数ライブラリ、random

注意:最新ドラフトのN3000のrandomの規定は、コンセプトが却下される前の文面であり、今後、変更があると思われる。

C++は標準ライブラリが貧弱であるとは、よく言われることだ。ことに、乱数に関しては、貧弱の極みである。ご存じのように、C++は、Cから標準ライブラリを引き継いでいる。rand()だ。これは、0からRAND_MAXまでの値を返すと規定されている。RAND_MAXは実装によって異なるが、ほとんどの処理系では、32767である。現代の乱数需要を満たすには、あまりにも小さすぎる。

この状況を打破すべく、C++0xには新しい乱数のライブラリが盛り込まれた。randomである。これはBoostの実装を元にしているのだが、Boostとは少し違っている。今回はそのrandomを、浅く触りだけ紹介しようと思う。というのも、ライブラリの細かなメンバ関数の一つ一つまで説明するのは、甚だ冗長であるし、残念ながら私は、乱数のアルゴリズムを詳細に論ずるだけの数学的知識を持ち合わせていないからだ。そんな私が解説するのであるから、数式を見ただけでジンマシンがでるほどの数学アレルギーをお持ちの型も、安心して読み進めてもらいたい。

使い方

randomは、<random>をincludeすることによって使用できる。

#include <random>

randomを利用するに当たって、最低限知っておかなければならないことは二つある。engineとdistributionである。

engine

エンジンは、乱数生成のクラスである。乱数はこのクラスで生成されることになる。標準で、様々なアルゴリズムが用意されている。もちろん、標準のコンセプトに乗っ取って、自分で実装することも出来る。コンセプトはすでに廃止されたが、便宜上こう呼ぶことにする。あるいは、インターフェースとでもいうべきか。

標準ライブラリは、おもに三つのエンジンを提供し、そのエンジンをベースに、さらに三つのアダプタエンジンを提供している。

とはいっても、一般ユーザーが主に使うのは、そのエンジンをさらにtypedefしたものである。ここでは、主にメルセンヌ・ツイスタを使うことにする。その他のアルゴリズムや、具体的な実装方法に興味があれば、規格を読んでもらいたい。

さて、早くコードが読みたいせっかちな諸君のために、エンジンを使ったコード例を示そう。

int main()
{
    std::mt19937 engine ;

    std::cout << "min: " << engine.min() << std::endl ;
    std::cout << "max: " << engine.max() << std::endl ;

    for ( int i = 0 ; i != 10 ; ++i )
        std::cout << engine() << std::endl ;
}

これで乱数は生成できた。めでたしめでたし・・・・・・ならず。

残念ながら、話はハッピーエンドには終わらないのである。確かに乱数は生成できた。ただし、これではあまり使い勝手がよくない。無論、諸君は私より数学が得意であろうから、「値の範囲が便利じゃないって? 別にかまわんよ。値の範囲の調整ぐらい自前でやるさ」と思うかも知れない。しかし、私は先ほども言ったように、数学的知識が絶望的に足りないので、一体どうやって正しく値の範囲を変更すればよいのか分からない。私は先天的に数学を理解する脳の部分を持たずに生まれてきているので、数式というものは、まったく頭に入らないのである。

そもそも、仮に値の範囲を変更する方法を知っていたとしても、いちいちそんな面倒な事を自前で書きたくはない。真に優れたプログラマというのは、自分でコードを書かないものである。コードを書かなければ、バグを生み出す恐れはないからだ。幸い、標準ライブラリは、値を希望の範囲に変えてくれるクラスを提供してくれている。

distribution

engineクラスの生成する乱数を、ユーザーの欲しい値の範囲に変えてくれるのが、distributionクラスの役割だ。

ここで、六面のサイコロを作るものとする。六面のサイコロは、1から6までの数字を、一様に、ランダムで出すものである。型は、intでいいだろう。さっそく、distributionクラスを使って、サイコロを実装しよう。

int main()
{
    std::mt19937 engine ;

    std::uniform_int_distribution<int> distribution( 1, 6 ) ;

    for ( int i = 0 ; i != 10 ; ++i )
        std::cout << distribution(engine) << std::endl ;
}

このように、uniform_int_distributionを使うことによって、整数型の、範囲を指定した乱数を生成させることが出来る。ここではintを使ったが、shortでもlongでも、signedでもunsignedでも、整数型なら、自由に使える。

実数の乱数

整数だけではなく、実数の乱数も欲しい所である。実数の為には、uniform_real_distributionクラスが用意されている。

いま、0.0から1.0の範囲の実数を、一様かつランダムに生成したいとする。一体何故、このような乱数が必要になるのか、私にはいまいち分からないが、諸君の大部分は、私より数学が得意であろうから、なにがしかの理由を知っているのであろう。

int main()
{
    std::mt19937 engine ;

    std::uniform_real_distribution<double> distribution( 0.0, 1.0 ) ;

    for ( int i = 0 ; i != 10 ; ++i )
        std::cout << distribution(engine) << std::endl ;
}

ご覧の通りである。

distributionは他にもある。ここで紹介していないのは、uniformではない乱数を返すものである。つまり、範囲内の値が、同じ確率ででないのである。こう書くと、奇妙に聞こえるかも知れない。例えば、Normal Distributionだ。数学の分からない私には何がそんなに嬉しいのか理解できないが、範囲内の値を、正規分布な乱数で返すdistributionクラスである。その他にも、BernoulliだのPoissonだのSamplingだのと、色々あり、しかもその中d、さらに細かく別れているのだが、私にはさっぱり理解できない。多分、数学の出来る変態達には、垂涎もののクラスなのだろう。

seed

なるほど、randomの使い方はだいたい分かった。しかし、このままでは、実際に使うことは出来ぬ。凡そ乱数というものは、初期化を必要とする。メルセンヌなんとかいうアルゴリズムが、エラい数学のセンセーのお墨付きであったとしても、所詮は数式に過ぎぬ。何か外部から、最初の値を、真の乱数を与えてやらなければならないのだ。さもなくば、乱数の値は、プログラムを何度実行しても、同じものになってしまう。

標準ライブラリには、seed_seqというクラスがあり、これでもって、エンジンを初期化できる。

追記:engineに渡すseed sequenceを満たしたクラスのオブジェクトは、lvalueでなければならない。

    std::vector< std::uint_least32_t > v ;
    std::seed_seq seed( v.begin(), v.end() ) ;
    std::mt19937 engine( seed ) ;

seed_seqは、イテレーターをとる。各value_typeは、2の32乗に丸められて、seed_seqのprivateなメンバ変数であるvectorに格納される。エンジンは、seed_seqを使って初期化される。要素はいくつあってもかまわない。ただし、すべて使われるという保証はない。それは実装依存である。

問題なのは、一体どうやってこのvを乱数で埋めるかという話である。

真の乱数

乱数には、疑似乱数と真の乱数がある。今まで使っていたのは、疑似乱数である。ここでは、真の乱数が必要なのである。

本当の意味での真の乱数というのは、ラジウムとガイガーカウンターを組み合わせたデバイスであろう。なぜなら、ラジウムがいつアルファ崩壊するかは、観測するまで分からず、完全に確立の問題だからである。

余談だが、私は常々これに疑問を持っている。我々が観測しようがしまいが、アルファ崩壊する時は決まっているはずである。むしろ、アルファ崩壊を観測した我々と、アルファ崩壊を観測していない我々の、両方が存在するのではないかと思う。それはさておき。

残念ながら、そのようなデバイスは非常に高価であり、一般ユーザーのコンピューターには取り付けられていない。そこまで真の乱数とはいかなくても、ある程度のまともな乱数は、一般のコンピューターにも存在する。たとえば、現在の時刻であるとか、CPUの温度などだ。

幸いにして、C++0xの標準ライブラリには、そのような乱数を生成するクラスがある。random_deviceである。

int main()
{
    std::random_device rnd ;
    for ( int i = 0 ; i != 10 ; ++i )
        std::cout << rnd() << std::endl ;
}

「なんだ。最初からこれを使えばいいではないか」と思うかも知れない。ところが、普通の乱数の需要は、ここまで大がかりな乱数を使う必要はないのである。その理由については、私より簡潔かつ詳しく解説している本が山ほどあるので、ここでは説明しない。もし、分かりやすい本を知らないのと言うのであれば、結城浩の『新版暗号技術入門――秘密の国のアリス』がおすすめである。今手元にないので確認できないが、確か乱数について解説していたと思う。

さて、では早速、エンジンを初期化しよう。

int main()
{
    // ランダムデバイス
    std::random_device rnd ;

    // 初期化用ベクタ
    std::vector< std::uint_least32_t> v(10) ;

    // ベクタの初期化
    std::generate( v.begin(), v.end(), std::ref(rnd) ) ;
    
    // 乱数エンジン
    std::mt19937 engine( std::seed_seq( v.begin(), v.end() ) ) ;

    // distribution
    std::uniform_real_distribution<double> distribution(0.0, 1.0) ;
    

    for ( int i = 0 ; i != 10 ; ++i )
        std::cout << distribution(engine) << std::endl ;
}

美しい。

random_deviceをstd::ref()で渡しているのには、理由がある。というのも、このクラス、コピーもmoveもできないのである。したがって、関数オブジェクトとして渡そうと思ったら、参照で渡さなければならない。これも、C++0xには、便利な関数が<functional>にあるので、問題ない。

Boost.Randomとの違い

BoostにはRandomというライブラリがあり、TR1はこれを参考にして設計された。とはいえ、実際のC++0xに採用されたrandomは、Boostのものとは、多少異なっている。特にBoostユーザーは、variate_generatorがないことに驚くであろう。しかし、これには理由がある。

variate_generatorは、engineとdistributionをラップする便利なクラスである。なぜ、C++0xにはないのだろうか。

いくつかの乱数のアルゴリズムでは、variate_generatorを使えば、ある種の最適化ができるはずだった。これは、variate_generatorの本来の目的だ。ところが、実際に実装してみた所、別にvariate_generatorがなくても、問題がないことが分かった。さらに、variate_generatorが、乱数のアルゴリズムの実装を制限する可能性も指摘された。そんなわけで、variate_generatorの本来の目的は、消えてしまったのだ。そこで、variate_generatorは、規格から消されることになった。

しかし、engineとdistributionのラッパーとしての役割はどうすればいいのか。二つの変数を管理するのは面倒だ。一つにまとめたい。わざわざ自前でクラスを書かなければならないのだろうか。

実は、C++0xの力を以てすれば、そんなことはわけないのである。

int main()
{
    // bindを使う方法
    auto rnd1 = std::bind( std::uniform_real_distribution<double>(0.0, 1.0), std::mt19937() ) ;
 

    std::cout << rnd1() << std::endl ;

    // lambdaを使う方法
    std::mt19937 engine ;
    std::uniform_real_distribution<double> distribution(0.0, 1.0) ;

    auto rnd2 = [&]{ return distribution(engine) ; } ;

    std::cout << rnd2() << std::endl ; 
}

もちろん、autoの代わりに、std::functionを使ってもよい。

最後に

このように、C++0xのrandomは、数学がまったく理解できないものでも使いこなせる、実に便利なライブラリなのである。

7 comments:

  1. 今手元の規格(N3126)を読んだところ、 random number engine に渡す seed sequence は lvalue でないといけないようです。
    なので、
    std::mt19937 engine( std::seed_seq( v.begin(), v.end() ) ) ;
    というコードはコンパイルが通らない可能性が。

    ReplyDelete
  2. それから細かいことですが、 std::seed_seq が乱数エンジンをどのように初期化するかは、規格で規定されてるようです(とはいえ今の gcc の実装は規格と微妙に異なっていますが)。
    これが規格で決まっていると、( std::mt19937 のような乱数エンジンも規格によってどのように乱数を生成するかが定められているので、)同じ引数から生成された std::seed_seq によって初期化された乱数エンジンは、実装によらず 常に同じ数値列を出力するようになり、シミュレーション結果の再現性を確保できるので、規格できちんと定められているのでしょう。

    とはいえ、 std::seed_seq ではない、一般の seed sequence の場合には、コンストラクタで渡されたデータを全て使う必要はないみたいですね。

    ReplyDelete
  3. おっと、本当だ。
    修正。

    ReplyDelete
  4. しかし、なぜlvalueでなければならないのだろう。

    ReplyDelete
  5. ああ、なるほど、seed sequenceって結構複雑な実装なんですね。
    しかし、これは極端なハナシ、

    std::seed_seq s({0}) ;
    だけでもいいということか。

    ReplyDelete
  6. あ、初期化リストはargument deductionにはならないな。
    するとこうか。

    std::seed_seq s( std::initializer_list<int>{0} ) ;

    ReplyDelete
  7. 通りすがりに古い記事にコメントつけさせてもらいます。

    > ほとんどの処理系では、32767である。現代の乱数需要を満たすには、あまりにも小さすぎる。
    >
    > この状況を打破すべく、C++0xには新しい乱数のライブラリが盛り込まれた。

    新しい乱数ライブラリが標準に盛り込まれた理由として、
    「RAND_MAX が小さすぎる」などという問題は挙げられていません。
    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1452.html

    未だに RAND_MAX を 16 bit 時代の 32767 に固定しているのは
    互換性をものすごく重要視している MSC ぐらいのものかと。
    少なくとも GCC が該当しない状態で「ほとんどの処理系では」と
    いうのは無理があるでしょう。

    ReplyDelete

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.