重み付き乱数質問する

Question

アイテムが個別に重みを持つ場合、アイテムをランダムに選択するための簡単なアルゴリズムがあります。

1) すべての重みの合計を計算する

2) 0以上で重みの合計より小さい乱数を選択する

3) アイテムを一つずつ調べ、ランダムな数値から重量を引いていき、ランダムな数値がそのアイテムの重量よりも小さくなるアイテムを見つけます。

これを説明する疑似コード:

int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];
}
assert(!"should never get here");

これをブーストコンテナーなどに簡単に適応できるはずです。

重みはほとんど変更されないが、ランダムに選択することが多く、コンテナーがオブジェクトへのポインターを格納しているか、数十項目以上ある場合 (基本的に、これが役立つか妨げになるかを知るにはプロファイルを作成する必要があります)、最適化が行われます。

各アイテムの累積重量の合計を保存することで、二分探索ピッキング重量に対応するアイテムをピッキングします。

リスト内のアイテムの数がわからない場合は、非常に便利なアルゴリズムがあります。貯留層サンプリング重み付けできるように調整できます。

Answer 1