Ważone liczby losowe

Próbuję zaimplementować ważone liczby losowe. Obecnie tylko walę głową w ścianę i nie mogę tego rozgryźć.

W moim projekcie (zakresy rąk w Hold'em, subiektywna analiza equity all-in) używam losowych funkcji Boosta. Powiedzmy, że chcę wybrać losową liczbę od 1 do 3 (czyli 1, 2 lub 3). Generator twisterów mersenne firmy Boost działa w tym jak urok. Jednak chcę, aby kilof był ważony, na przykład w ten sposób:

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

Czy Boost ma do tego jakąś funkcjonalność?

Istnieje prosty algorytm do losowego wybierania przedmiotu, w którym przedmioty mają indywidualną wagę:

1) obliczyć sumę wszystkich wag

2) wybierz liczbę losową równą 0 lub większą i mniejszą niż suma wag

3) przeglądaj elementy pojedynczo, odejmując ich wagę od liczby losowej, aż otrzymasz przedmiot, w którym liczba losowa jest mniejsza niż waga tego przedmiotu

Pseudokod ilustrujący to:

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

Powinno to być proste, aby dostosować się do twoich pojemników do przyspieszania i tym podobnych.

Jeśli twoje ciężary są rzadko zmieniane, ale często wybierasz jeden losowo i tak długo, jak twój pojemnik przechowuje wskaźniki do obiektów lub ma więcej niż kilkadziesiąt przedmiotów (w zasadzie musisz profilować, aby wiedzieć, czy to pomaga, czy przeszkadza) , to jest optymalizacja:

Przechowując skumulowaną sumę wag w każdej pozycji, możesz skorzystać z wyszukiwania binarnego w celu wybrania pozycji odpowiadającej masie pobrania.

Jeśli nie znasz liczby pozycji na liście, istnieje bardzo zgrabny algorytm zwany próbkowaniem zbiorników, który można dostosować do ważenia.

Zaktualizowana odpowiedź na stare pytanie. Możesz to łatwo zrobić w C ++ 11 za pomocą tylko 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';
}

Wyjście w moim systemie:

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

Zauważ, że większość powyższego kodu poświęcona jest tylko wyświetlaniu i analizowaniu danych wyjściowych. Faktyczna generacja to tylko kilka wierszy kodu. Dane wyjściowe pokazują, że żądane „prawdopodobieństwa” zostały uzyskane. Musisz podzielić żądane dane wyjściowe przez 1,5, ponieważ do tego sumują się żądania.

Jeśli twoje wagi zmieniają się wolniej niż są rysowane, C ++ 11 discrete_distributionbędzie najłatwiejszy:

#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...

Należy jednak pamiętać, że c ++ 11 discrete_distributionoblicza wszystkie skumulowane sumy podczas inicjalizacji. Zwykle jest to pożądane, ponieważ przyspiesza czas próbkowania przy jednorazowym koszcie O (N). Ale w przypadku szybko zmieniającej się dystrybucji będzie to wiązało się z dużym kosztem obliczeń (i pamięci). Na przykład, jeśli wagi reprezentowały liczbę elementów i za każdym razem, gdy rysujesz jeden, usuwasz go, prawdopodobnie będziesz potrzebować niestandardowego algorytmu.

Odpowiedź Willa https://stackoverflow.com/a/1761646/837451 pozwala uniknąć tego narzutu, ale będzie wolniejsza w użyciu niż z C ++ 11, ponieważ nie może używać wyszukiwania binarnego.

Aby zobaczyć, że to robi, możesz zobaczyć odpowiednie linie ( /usr/include/c++/5/bits/random.tccna mojej instalacji Ubuntu 16.04 + GCC 5.3):

  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;
    }

To, co robię, gdy muszę zważyć liczby, używa losowej liczby jako wagi.

Na przykład: Potrzebuję generowania liczb losowych od 1 do 3 o następujących wagach:

• 10% liczby losowej może wynosić 1
• 30% liczby losowej może wynosić 2
• 60% liczby losowej może wynosić 3

Następnie używam:

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;
}

W tym przypadku losowo ma 10% prawdopodobieństw 1, 30% 2 i 60% 3.

Możesz się nim bawić zgodnie ze swoimi potrzebami.

Mam nadzieję, że mogę ci pomóc, powodzenia!

Zbuduj worek (lub std :: wektor) wszystkich przedmiotów, które można wybrać.
Upewnij się, że liczba każdego elementu jest proporcjonalna do Twojej wagi.

Przykład:

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

Więc miej worek ze 100 pozycjami z 60 1, 35 2 i 5 3.
Teraz losowo posortuj torbę (std :: random_shuffle)

Wybierz elementy z worka po kolei, aż będzie pusty.
Po opróżnieniu zmień losowo worek i zacznij od nowa.

Wybierz losową liczbę na [0,1), która powinna być domyślnym operatorem () dla RNG doładowania. Wybierz pozycję z funkcją skumulowanej gęstości prawdopodobieństwa> = ta liczba:

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
}

Gdzie random01 () zwraca double> = 0 i <1. Zauważ, że powyższe nie wymaga sumowania prawdopodobieństw do 1; normalizuje je dla ciebie.

p jest po prostu funkcją przypisującą prawdopodobieństwo do elementu w kolekcji [początek, koniec). Możesz go pominąć (lub użyć tożsamości), jeśli masz tylko sekwencję prawdopodobieństw.

Zaimplementowałem kilka prostych ważonych algorytmów losowych .