5193


C++言語において、確率P(x,y)を実装しています。

P(x)については実装してみました。といっても`map`を利用して`key`が何回出現したかを`second`のカウンターを利用して全体で割ったものですが、

[code]

    std::map<int,int> P;
    for(int i=0;i<10;i++)
     P.insert(std::make_pair(i,0));
    P.find(rand())->second++;
    
[/code]

のような形で、P(x)と見立てたものです。

しかし、P(a,b)のような２つの変数となるとどのような実装方法が適切かわかりません。

P(a,b)を実装したい理由は、P(a,b,c)のように変数が3つの場合に、cは任意とした場合、cについて全て走査する必要があり効率的で無いからです。

どのようなデータ構造を利用すればよいでしょうか。


CC BY-SA 3.0
2015-01-01T07:04:09.110
2889
2015-01-25T02:59:06.130
2015-01-25T02:59:06.130
30
question
アルゴリズム c c++
2つの確率変数X,Yをとる確率関数 ​を表現するのに適したデータ構造を教えて下さい


確率分布を求めるのであればキーの定義域を有限個の階級に分割して、全組み合わせ分の一次元配列を確保する実装の方が良いのではないかと思います。分布が偏在することが分かっているのなら、ジャグド配列にして必要な個所だけ投票空間を確保したり、階級の大きさを不均等にすることも出来ます。

空間に比べて要素数が極端に少ないのであればmapのキーに構造体などを使えばキーの次元を変更できます。この場合構造体に比較演算子を実装する必要があります。


CC BY-SA 3.0
2015-01-24T05:31:08.783
5192
2015-01-24T05:31:08.783
5750
2889
answer


C++の`std::map`コンテナでは、そのキーとして値のペア(`std::pair`)や任意個数の値の組(`std::tuple`)も利用できます。（後者はコンパイラがC++11対応している必要があります）

確率変数が2個なら`std::pair<int,int>`、3個なら`std::pair<int,int,int>`をマップのキー型に利用すれば良いでしょう。これらの型では比較演算子も暗黙に提供されるので、そのまま`std::map`に利用できます。

[code]

    // 2変数の確率質量関数 P(X,Y)
    std::map<std::pair<int,int>, int> p;
    // 適当に初期化
    for (int x = 0; x < 10; ++x)
      for (int y = 0; y < 20; y += 2)
        p[std::make_pair(x, y)] = (x*100) + y;
    // P(5,10)を表示（注：正規化前の値）
    std::cout << "P(5,10)=" << p[std::make_pair(5, 10)] << std::endl;
    
    // 3変数の確率質量関数 Q(X,Y,Z)
    std::map<std::tuple<int,int,int>, int> q;
    // 適当に初期化
    for (int x = 0; x < 10; ++x)
      for (int y = 0; y < 20; y += 2)
        for (int z : {1, 2, 3, 5, 8, 13, 21, 34})
          q[std::make_tuple(x, y, z)] = (x*10000) + (y*100) + z;
    // Q(5,10,8)を表示（注：正規化前の値）
    std::cout << "Q(5,10,8)=" << q[std::make_tuple(5, 10, 8)] << std::endl;
    
[/code]

LiveDemo: <http://melpon.org/wandbox/permlink/z1eGIXIQus93g6w2>


CC BY-SA 3.0
2015-01-24T06:46:26.787
5193
2015-01-24T06:46:26.787
49
2889
answer