1

私はC++でおよそ2000の要素の配列を扱っています。

各要素は、その要素がランダムに選択される確率を表します。

次に、この配列を累積配列に変換しました。これを使用して、サイコロを振ったときに選択する要素を決定することを目的としています。

配列の例：{1,2,3,4,5}

累積配列の例：{1,3,6,10,15}

数字の3、4、または5が出たときに、累積配列で3を選択できるようにしたいと思います。

追加された複雑さは、私の配列が長いdoubleで構成されていることです。いくつかの連続した要素の例を次に示します。

0.96930161525189592646367317541056252139242133125662803649902343750 0.96941377254127855667142910078837303444743156433105468750000000000 0.96944321382974149711383993199831365927821025252342224121093750000 0.96946143938926617454089618153290075497352518141269683837890625000 0.969

これは、このデータセットを使用して加重確率を実行するためのひどい方法である可能性があるため、これを解決するためのより良い方法の提案を受け入れます。

4

4 に答える 4

2

あなたが使用することができますpartial_sum：

unsigned int SIZE = 5;
int array[SIZE] = {1,2,3,4,5};
int partials[SIZE] = {0};

partial_sum(array, array+SIZE, partials);
// partials is now {1,3,6,10,15}

配列に必要な値は、部分和から入手できます。

12 == array[2] + array[3] + array[4];

12 == partials[4] - partials[1];

合計は明らかに部分和の最後の値です。

15 == partial[4];
于 2013-02-19T10:02:43.730 に答える
1

部分和の配列を計算しなくても、ストリーム選択を使用して実際にこれを行うことができます。これがJavaでこれのために持っているコードです：

public static int selectRandomWeighted(double[] wts, Random rnd) {
    int selected = 0;
    double total = wts[0];

    for( int i = 1; i < wts.length; i++ ) {
        total += wts[i];

        if( rnd.nextDouble() <= (wts[i] / total)) {
            selected = i;
        }
    }

    return selected;        
}

合計でできるだけ多くの桁の精度を維持したい場合は、カハンの合計を使用して上記をさらに改善できる可能性があります。

ただし、この配列から繰り返し描画する場合は、部分和の配列を事前に計算し、バイナリ検索を使用して適切なインデックスを見つける方が高速です。

于 2013-02-21T04:45:33.817 に答える
1

最終ステップまで精度が低下しないように、情報を整数の分子および分母として格納することを検討してください。

于 2013-02-18T17:29:02.813 に答える
0

わかりました、私はこれを解決したと思います。

バイナリ分割検索を実行しましたが、

if (arr[middle] == value)

ORで追加しました

if (arr[middle] == value || (arr[middle] < value && arr[middle+1] > value))

これは私が望んでいた方法でそれを処理するようです。

于 2013-02-18T17:09:24.480 に答える