Взвешенные случайные числа

Question

Я пытаюсь реализовать взвешенные случайные числа. Сейчас я просто бьюсь головой о стену и не могу этого понять.

В моем проекте (диапазоны рук Холдема, субъективный анализ олл-инов) я использую случайные -функции Boost. Итак, допустим, я хочу выбрать случайное число от 1 до 3 (то есть 1, 2 или 3). Твистер-генератор Boosen's Mersenne работает как шарм. Однако я хочу, чтобы выборка была взвешена, например, так:

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

Есть ли в Boost какая-то функциональность для этого?

Answer 1

Существует простой алгоритм выбора предмета в случайном порядке, где предметы имеют индивидуальный вес:

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 2

Обновлен ответ на старый вопрос. Вы можете легко сделать это в C ++ 11 только с помощью 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';
}

Вывод в моей системе:

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

Обратите внимание, что большая часть кода выше посвящена просто отображению и анализу выходных данных. Фактическое поколение - всего несколько строк кода. Выходные данные демонстрируют, что запрошенные «вероятности» были получены. Вы должны разделить запрошенный вывод на 1,5, поскольку это то, к чему суммируются запросы.

Answer 3

Если ваши веса изменяются медленнее, чем они нарисованы, C ++ 11 discrete_distribution будет самым простым:

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

Обратите внимание, однако, что c ++ 11 discrete_distribution вычисляет все накопленные суммы при инициализации. Обычно вы этого хотите, потому что это ускоряет время выборки за один раз O (N). Но для быстро меняющегося дистрибутива это потребует больших затрат на вычисления (и память). Например, если веса представляли, сколько элементов существует, и каждый раз, когда вы их рисуете, вы удаляете его, вам, вероятно, понадобится собственный алгоритм.

Воля ответит https://stackoverflow.com/a/1761646/837451 избегает этих издержек, но будет медленнее извлекать из, чем C ++ 11, потому что он не может использовать бинарный поиск.

Чтобы убедиться, что он делает это, вы можете увидеть соответствующие строки (/usr/include/c++/5/bits/random.tcc на моей установке 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;
    }

Answer 4

То, что я делаю, когда мне нужно взвешивать числа, использует случайное число для веса.

Например: мне нужно, чтобы генерировались случайные числа от 1 до 3 со следующими весами:

• 10% случайного числа может быть 1
• 30% случайного числа может быть 2
• 60% случайного числа может быть 3

Тогда я использую:

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

При этом в случайном порядке 10% вероятности составляют 1, 30% - 2 и 60% - 3.

Вы можете играть с ним, как вам нужно.

Надеюсь, я смогу вам помочь, удачи!

Answer 5

Соберите сумку (или std :: vector) из всех предметов, которые можно выбрать.
Убедитесь, что количество каждого элемента пропорционально вашему весу.

Пример:

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

Так что имейте сумку с 100 предметами с 60 1, 35 2 и 5 3.
Теперь случайным образом отсортируйте сумку (std :: random_shuffle)

Выбирайте элементы из пакета последовательно, пока он не опустеет.
После опустошения повторно перемешать сумку и начать снова.

Answer 6

Я реализовал несколько простых взвешенных случайных алгоритмов .

Answer 7

Выберите случайное число на [0,1), которое должно быть оператором по умолчанию () для ускоренного ГСЧ. Выберите элемент с кумулятивной функцией плотности вероятности> = это число:

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
}

Где random01 () возвращает double> = 0 и <1. Обратите внимание, что приведенное выше не требует вероятностей для суммирования до 1; это нормализует их для вас. </p>

p - это просто функция, присваивающая вероятность элементу в коллекции [начало, конец). Вы можете опустить его (или использовать тождество), если у вас просто есть последовательность вероятностей.