重み付きrandom.choice
速度が必要になった結果、Pythonのコードを全部C++で書き直す羽目になった@Angelworm_です。
配列から要素をランダムに一個取ってくる様なコードってPythonならこう。
x = random.choice([1,2,3,4,5])
で、Cとかだとこんな感じだとか(rand()が良くないのは置いておいて)。 乱数を配列のサイズで割ったあまりがランダムなインデックスだ。みたいな。
int array[] = {1,2,3,4,5}; int x = array[rand() % sizeof(array)];
さてさて、このそれぞれの要素に重みが有って、ソレを踏まえてランダムに要素が欲しい。
重み付き乱択といえば、長さ1の直線を発生確率毎に切って、[0, 1)な乱数の落ちた所の要素を選ぶというのが一般的なアルゴリズムだそうだ*1。ならば実装すればいいじゃんって話だけど、C++11ならライブラリに有ったので使う*2。
対象の配列と確率列が別にある場合だとこんな感じかも。
template<class S, class T, class Gen> S w_choice(std::vector<S>& data, std::vector<T>& pr, Gen& g) { std::discrete_distribution<int> gen(pr.begin(), pr.end()); return data[gen(g)]; }
prで与えられた重み列に基づいてdataからいい感じに取ってくる感じ。