信頼に確率比例してノードを選択します

Question

誰もがいくつか付属の値に比例し、選択されたそれらの確率で、アイテムを選択するに関連するアルゴリズムやデータ構造を知っていますか？言い換えれば： http://en.wikipedia.org/wiki/Sampling_% 28statistics％29＃Probability_proportional_to_size_samplingする

ここで、コンテキストは、分散評判システムであり、添付の値は、したがって、一人のユーザが別に有している信頼の値です。このシステムでは、すべてのノードが完全に信頼され、完全に信頼されている友人や、未知数として起動のいずれか。あなたは友人を持って、あなたはあなたの直接の友人ではないユーザーの大規模なグループに信頼するかを知る必要があるよりも、より多くのノードが存在しますので、これは大規模なP2Pネットワークにそれ自体で有用ではありませんので、私は実装しましたダイナミック信託システムは、ここでの未知数は、友人の - 友人関係を経て信頼を得ることができます。

しょっちゅう各ユーザーは、中間ノードの別の選択された固定数はそれらを信頼してどのくらいに基づいて、彼らの信頼を再計算するために、ターゲット・ノードの（速度と帯域幅のために）固定数を選択します。未知数よりよく知られているになるチャンスを持っているように、再計算のためのターゲット・ノードを選択する確率は、その現在の信頼に反比例します。中間ノードは、中間の選択の確率は、その現在の信頼に比例していることを除いて、同じ方法で選択される。

私は簡単な解決策自分自身を書いたが、それはかなり遅いですし、私は私のためにこの側面を扱うためのC ++ライブラリを見つけるしたいと思います。私はもちろん私自身の調査を行っていると私は私が今を掘りてるTRSLを見つけることができました。それはおそらくかなり単純かつ一般的な問題のように思えるので、私はこのために使用することができ、より多くのC ++ライブラリがあると期待されるので、私はここで誰かがこの上でいくつかの光を当てることができますことを期待して、この質問をしています。

Answer 1

これは私がやるだろうと何でます：

int select(double *weights, int n) {
    // This step only necessary if weights can be arbitrary
    // (we know total = 1.0 for probabilities)
    double total = 0;
    for (int i = 0; i < n; ++i) {
        total += weights[i];
    }

    // Cast RAND_MAX to avoid overflow
    double r = (double) rand() * total / ((double) RAND_MAX + 1);
    total = 0;
    for (int i = 0; i < n; ++i) {
        // Guaranteed to fire before loop exit
        if (total <= r && total + weights[i] > r) {
            return i;
        }

        total += weights[i];
    }
}

あなたが望むように、

もちろん、複数のサンプルを生成するために、新しいrを毎回選択し、何回も第二のループを繰り返すことができます。