Angka acak berbobot

Saya mencoba menerapkan bilangan acak berbobot. Saat ini aku hanya membenturkan kepalaku ke dinding dan tidak bisa memahami ini.

Dalam proyek saya (rentang tangan Hold'em, analisis ekuitas all-in subjektif), saya menggunakan fungsi acak Boost. Jadi, katakanlah saya ingin memilih nomor acak antara 1 dan 3 (jadi 1, 2 atau 3). Generator twister mersenne Boost bekerja seperti pesona untuk ini. Namun, saya ingin pick diberi bobot seperti ini:

1 (weight: 90)
2 (weight: 56)
3 (weight:  4)

Apakah Boost memiliki semacam fungsi untuk ini?

Ada algoritme langsung untuk memilih item secara acak, di mana item memiliki bobot individual:

1) hitung jumlah semua bobot

2) pilih nomor acak yang 0 atau lebih besar dan kurang dari jumlah bobot

3) periksa item satu per satu, kurangi bobotnya dari nomor acak Anda, sampai Anda mendapatkan item di mana nomor acaknya kurang dari bobot item itu

Pseudo-code menggambarkan ini:

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");

Ini harus mudah untuk disesuaikan dengan wadah penambah Anda dan semacamnya.

Jika bobot Anda jarang berubah tetapi Anda sering memilihnya secara acak, dan selama wadah Anda menyimpan pointer ke objek atau panjangnya lebih dari beberapa lusin (pada dasarnya, Anda harus membuat profil untuk mengetahui apakah ini membantu atau menghalangi) , lalu ada pengoptimalan:

Dengan menyimpan jumlah bobot kumulatif di setiap item, Anda dapat menggunakan pencarian biner untuk memilih item yang sesuai dengan bobot pick.

Jika Anda tidak mengetahui jumlah item dalam daftar, maka ada algoritme yang sangat rapi yang disebut reservoir sampling yang dapat disesuaikan untuk diberi bobot.

Jawaban yang diperbarui untuk pertanyaan lama. Anda dapat dengan mudah melakukan ini di C ++ 11 hanya dengan std :: lib:

#include <iostream>
#include <random>
#include <iterator>
#include <ctime>
#include <type_traits>
#include <cassert>

int main()
{
    // Set up distribution
    double interval[] = {1,   2,   3,   4};
    double weights[] =  {  .90, .56, .04};
    std::piecewise_constant_distribution<> dist(std::begin(interval),
                                                std::end(interval),
                                                std::begin(weights));
    // Choose generator
    std::mt19937 gen(std::time(0));  // seed as wanted
    // Demonstrate with N randomly generated numbers
    const unsigned N = 1000000;
    // Collect number of times each random number is generated
    double avg[std::extent<decltype(weights)>::value] = {0};
    for (unsigned i = 0; i < N; ++i)
    {
        // Generate random number using gen, distributed according to dist
        unsigned r = static_cast<unsigned>(dist(gen));
        // Sanity check
        assert(interval[0] <= r && r <= *(std::end(interval)-2));
        // Save r for statistical test of distribution
        avg[r - 1]++;
    }
    // Compute averages for distribution
    for (double* i = std::begin(avg); i < std::end(avg); ++i)
        *i /= N;
    // Display distribution
    for (unsigned i = 1; i <= std::extent<decltype(avg)>::value; ++i)
        std::cout << "avg[" << i << "] = " << avg[i-1] << '\n';
}

Output di sistem saya:

avg[1] = 0.600115
avg[2] = 0.373341
avg[3] = 0.026544

Perhatikan bahwa sebagian besar kode di atas dikhususkan untuk hanya menampilkan dan menganalisis keluaran. Generasi sebenarnya hanyalah beberapa baris kode. Outputnya menunjukkan bahwa "probabilitas" yang diminta telah diperoleh. Anda harus membagi output yang diminta dengan 1,5 karena itulah yang ditambahkan oleh permintaan.

Jika bobot Anda berubah lebih lambat daripada yang digambar, C ++ 11 discrete_distributionakan menjadi yang termudah:

#include <random>
#include <vector>
std::vector<double> weights{90,56,4};
std::discrete_distribution<int> dist(std::begin(weights), std::end(weights));
std::mt19937 gen;
gen.seed(time(0));//if you want different results from different runs
int N = 100000;
std::vector<int> samples(N);
for(auto & i: samples)
    i = dist(gen);
//do something with your samples...

Perhatikan, bagaimanapun, bahwa c ++ 11 discrete_distributionmenghitung semua jumlah kumulatif saat inisialisasi. Biasanya, Anda menginginkannya karena mempercepat waktu pengambilan sampel untuk biaya satu kali O (N). Tetapi untuk distribusi yang berubah dengan cepat, ini akan menimbulkan biaya perhitungan (dan memori) yang berat. Misalnya jika bobot mewakili berapa banyak item yang ada dan setiap kali Anda menggambarnya, Anda menghapusnya, Anda mungkin menginginkan algoritme khusus.

Jawaban Will https://stackoverflow.com/a/1761646/837451 menghindari overhead ini tetapi akan lebih lambat untuk diambil dari C ++ 11 karena tidak dapat menggunakan pencarian biner.

Untuk melihat bahwa ia melakukan ini, Anda dapat melihat baris yang relevan ( /usr/include/c++/5/bits/random.tccpada instalasi Ubuntu 16.04 + GCC 5.3 saya):

  template<typename _IntType>
    void
    discrete_distribution<_IntType>::param_type::
    _M_initialize()
    {
      if (_M_prob.size() < 2)
        {
          _M_prob.clear();
          return;
        }

      const double __sum = std::accumulate(_M_prob.begin(),
                                           _M_prob.end(), 0.0);
      // Now normalize the probabilites.
      __detail::__normalize(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
                            __sum);
      // Accumulate partial sums.
      _M_cp.reserve(_M_prob.size());
      std::partial_sum(_M_prob.begin(), _M_prob.end(),
                       std::back_inserter(_M_cp));
      // Make sure the last cumulative probability is one.
      _M_cp[_M_cp.size() - 1] = 1.0;
    }

Apa yang saya lakukan ketika saya perlu menimbang angka adalah menggunakan angka acak untuk menimbang.

Sebagai contoh: Saya perlu menghasilkan angka acak dari 1 hingga 3 dengan bobot sebagai berikut:

• 10% dari nomor acak bisa jadi 1
• 30% dari nomor acak bisa jadi 2
• 60% dari nomor acak bisa jadi 3

Kemudian saya menggunakan:

weight = rand() % 10;

switch( weight ) {

    case 0:
        randomNumber = 1;
        break;
    case 1:
    case 2:
    case 3:
        randomNumber = 2;
        break;
    case 4:
    case 5:
    case 6:
    case 7:
    case 8:
    case 9:
        randomNumber = 3;
        break;
}

Dengan ini, secara acak memiliki 10% probabilitas menjadi 1, 30% menjadi 2 dan 60% menjadi 3.

Anda bisa bermain dengannya sesuai kebutuhan Anda.

Semoga saya bisa membantu Anda, Semoga Sukses!

Bangun tas (atau std :: vector) dari semua barang yang bisa diambil.
Pastikan jumlah setiap item proporsional dengan bobot Anda.

Contoh:

• 1 60%
• 2 35%
• 3 5%

Jadi miliki tas dengan 100 item dengan 60 1, 35 2 dan 5 3.
Sekarang urutkan tas secara acak (std :: random_shuffle)

Pilih elemen dari tas secara berurutan sampai kosong.
Setelah kosong, atur ulang tasnya dan mulai lagi.

Pilih nomor acak pada [0,1), yang seharusnya menjadi operator default () untuk meningkatkan RNG. Pilih item dengan fungsi kepadatan probabilitas kumulatif> = angka itu:

template <class It,class P>
It choose_p(It begin,It end,P const& p)
{
    if (begin==end) return end;
    double sum=0.;
    for (It i=begin;i!=end;++i)
        sum+=p(*i);
    double choice=sum*random01();
    for (It i=begin;;) {
        choice -= p(*i);
        It r=i;
        ++i;
        if (choice<0 || i==end) return r;
    }
    return begin; //unreachable
}

Di mana random01 () mengembalikan double> = 0 dan <1. Perhatikan bahwa hal di atas tidak membutuhkan probabilitas yang berjumlah 1; itu menormalkannya untuk Anda.

p hanyalah sebuah fungsi yang menetapkan probabilitas ke item dalam koleksi [awal, akhir). Anda dapat menghilangkannya (atau menggunakan identitas) jika Anda hanya memiliki urutan probabilitas.

Saya telah menerapkan beberapa algoritma acak tertimbang sederhana .