Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Случайный выбор объектов с разными вероятностями

Автор: Riddik 24.2.2012, 14:59

Привет!
Прошу помочь придумать алгоритм для такой задачи:

Есть набор объектов (A, B, C, D), у каждого своя вероятность, что сейчас выпадит именно он, например для A - 50%, B - 20%, C - 30%, D - 0%(не выпадит никогда). Какой-то объект должен быть обязательно выбран, но какой именно - зависит от вероятности каждого. Т.е. понятно, что A будет чаще других, D - никогда.
Этот момент критичен по времени выполнения, надо чтобы быстро.

Не могу никак придумать првильный алгоритм.

Люди подсказывают так:

Код


int r = rand() % 100;

if (r < 0)
{
   return "D"; // это условие никогда не выполнится, можем его не учитывать
}

if (r < (0 + 20))
{
   return "B";
}

if (r < (20 + 30))
{
   return "C";
}

if (r < (20 + 30 + 50))
{
   return "A";
}

Или для N объектов:

Код


int cases[CASE_MAX] = { ... };
int caseSum = 0;

for (int i = 0; i < CASE_MAX; ++i)
{
   caseSum += cases[i];
}

...
int r = rand() % caseSum;
int caseLimit = 0;

for (int i = 0; i < (CASE_MAX - 1); ++i)
{
   caseLimit += cases[i + 1];

   if (r < caseLimit)
   {
      return i; // return case index
   }
}

return CASE_MAX - 1; // last case

Но есть проблемы. Если несколько объектов имеют одинаковую вероятность, то придется заводить ещё отдельный массив с индексами таких объектов и снова генерировать случайное число, чтобы выбрать из таких объектов один случайный.

Но главное - все же не очень правильно вычисляется вероятность, как мне кажется.

Есть идеи, что можно ещё придумать?

Автор: boostcoder 24.2.2012, 15:05

использовать приоритетную очередь? ;)

Автор: Riddik 24.2.2012, 15:09

А как обеспечить, чтобы объект, у которого вероятность больше, чаще стоял на выходе?

Автор: boostcoder 24.2.2012, 15:13

что значит "чаще" ?
у кого приоритет выше - тот первым выйдет.
для того чтоб очередь использовать многократно - при выходе элемента, добавляем его обратно.

или я не правильно понял задачу?

Добавлено через 3 минуты и 2 секунды
и да - с приоритетными очередями есть проблема: нет стандартной реализации "хорошей" приоритетной очереди. та, что в стандартной библиотеке - ужасная реализация.элементы с более низкими приоритетами вовсе никогда не выйдут, пока имеются элементы с более высокими приоритетами.

хорошая реализация есть в boost: http://www.boost.org/doc/libs/1_49_0/doc/html/heap.html

Добавлено через 6 минут и 36 секунд
приоритеты элементов http://www.boost.org/doc/libs/1_49_0/doc/html/heap/concepts.html#heap.concepts.mutability. значит, распределение можно регулировать.

Автор: Riddik 24.2.2012, 15:22

Цитата(boostcoder @ 24.2.2012, 15:13

)

или я не правильно понял задачу?

Понял верно.
Спасибо за наводку на приоритетную очередь, буду пробовать. Единственное условие - буст не вариант использовать в текущем проекте, нельзя его с собой таскать, придётся разбираться и писать самому smile

Если будут ещё идеи, прошу высказываться smile

Автор: boostcoder 24.2.2012, 15:32

Цитата(Riddik @ 24.2.2012, 15:22

)

нельзя его с собой таскать

что значит "таскать" ?
для готового продукта, исходники буста таскать не нужно smile

Автор: Riddik 24.2.2012, 15:37

Не так выразился smile

Нельзя его использовать - подключать к текущему проекту. Такие условия.

Автор: Michrutka 24.2.2012, 17:01

Как вариант можно взять массив из 100 элементов и заполнить его согласно твоим процентам: у А будет 50 позиций, у Б - 30 и тд.
брать рендомное число в пределах 0-99 и смотреть на какую позицию попадешь.
в итоге будет нормальное распределние.

хотя это не очень красиво, да.

ан нет. это уже предлагали. сорри.

Автор: Riddik 24.2.2012, 17:35

Всё равно спасибо!

Автор: Qu1nt 24.2.2012, 20:15

Вот, набросал.

Код


#include <algorithm>
#include <ctime>
#include <iostream>
#include <map>
#include <string>
#include <vector>

int main()
{
    std::srand(static_cast<unsigned int>(std::time(0)));

    std::vector<std::pair<std::string, unsigned int>> data;
    data.push_back(std::make_pair("A", 50));
    data.push_back(std::make_pair("B", 20));
    data.push_back(std::make_pair("C", 30));
    data.push_back(std::make_pair("D", 0));

    std::vector<unsigned int> weights(data.size());
    weights[0] = data[0].second;
    for (unsigned int i = 1; i < data.size(); ++i)
    {
        weights[i] = weights[i - 1] + data[i].second;
    }

    std::vector<std::pair<std::string, unsigned int>> result(data.size());
    for (unsigned int i = 0; i < 1e5; ++i)
    {
        unsigned int dice = rand() % weights.back();
        unsigned int item = std::distance(weights.begin(), std::find_if(weights.begin(), weights.end(), 
            [&dice] (unsigned int weight)
            {
                return dice < weight;
            }));

        ++result[item].second;
    }

    std::for_each(result.begin(), result.end(), 
        [] (const std::pair<std::string, unsigned int>& pair)
        {
            std::cout << pair.first << ": " << pair.second << std::endl;
        });
}

http://liveworkspace.org/code/daa70b237fe8a538a296788da0592921

Автор: Riddik 24.2.2012, 22:11

Большое спасибо!