VPF::Случайно выбрать объект при заданных вероятностях

Userman

Дата 7.7.2009, 13:22 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 80
Регистрация: 21.8.2008

Репутация: нет
Всего: нет

Есть массив объектов, у которых есть числовое поле. Чем больше значение поля, тем больше вероятность выбора этого объекта.
Например, объектам соответствуют следующие значения поля:
[1] 2
[2] 1
[3] 0
[4] 1
Значит первый объект выберется с вероятностью 1/2, второй - 1/4, третий - 0, четвёртый - 1/4.
Надо, чтобы это выполнялось максимально быстро.

Это сообщение отредактировал(а) Userman - 7.7.2009, 13:24

GoldFinch

Дата 7.7.2009, 13:36 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26

сделай массив с указателями на объекты,
такой что если у объекта все=N то там N указателей на объект,
получиш равномерное распределение, и выбирай от туда случайный элемент

semibug

Дата 7.7.2009, 20:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 323
Регистрация: 27.3.2009

Репутация: нет
Всего: нет

Можно попробовать такой вариант:

Код


int Random( unsigned int *Tab, int Len )
{
    unsigned int sum = 0;
    for ( int i = 0; i < Len; i++ )
          sum += Tab[i];
    unsigned int r = rand( sum );
    int res = 0;
    unsigned int k = 0;
    for ( int i = 0; i < Len; i++ )
          if ( ( k += Tab[i] ) > r ) break; else res++;
    return res;
}

Это сообщение отредактировал(а) semibug - 7.7.2009, 20:19

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »