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

Question

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

Гидролокатор является инструментом контроля качества. Это измеряет качество JAVA-приложений через соблюдение кодирования соглашений правил, метрических мер и усовершенствованных индикаторов.

Гидролокатор основан на следующих проектах:

JavaNCSS: Метрики качества
Checkstyle: Cheking
PMD Стиля: сканирование Кода для потенциальных ошибок.
Cobertura: Тестовое покрытие

Вы могли также использовать Человекообразная обезьяна для обнаружения дублирования.

89

c++ boost random

задан moswald 24 February 2017 в 21:05

3 ответа

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

Пример:

1 60%
2 35%
3 5%

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

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

3

ответ дан 24 November 2019 в 07:14

Выберите случайное число на [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 () возвращает двойное значение> = 0 и <1. Обратите внимание, что приведенное выше не требует суммирования вероятностей до 1; он нормализует их для вас.

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

0

ответ дан 24 November 2019 в 07:14

Другие вопросы по тегам:

c++ boost random

Похожие вопросы:

score 151 · Accepted Answer

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

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

Это должно быть несложно для адаптации к вашим буст-контейнерам и тому подобному.

Если ваши веса редко меняются, но вы часто выбираете один случайным образом, и пока ваш контейнер хранит указатели на объекты или более нескольких десятков элементов (в основном, вы должны профилировать, чтобы знать, помогает это или мешает), тогда есть оптимизация:

Сохраняя совокупную сумму веса в каждом элементе, вы можете использовать двоичный поиск , чтобы выбрать элемент, соответствующий выбранному весу.

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