Частотный (весовой) коэффициент или выбор случайного числа с учетом веса
В продолжение процедуры приборки папки "Входящие" от залежалых писем, заношу в блог ссылку, на обсуждение и варианты реализации алгоритма выбора случайного элемента списка, у которого элементы имеют веса, влияющие на вероятность выбора конкретного элемента (элемент с большим весом должен иметь большую вероятность быть выбранным).
Вопрос звучал так:
Есть динамический список неких объектов, у каждого из которых определён свой частотный (весовой) коэффициент. Коэффициент описывается, например, шкалой 1,2...n, со смыслом "чем больше номер, тем чаще должен появлятся объект при выборе". Сейчас выбор идёт простым рандомайзером, но нужно как-то задействовать этот коэффициент. Вопрос в том, как это сделать?
Ссылка была прислана некоторое время назад Павлом. Обсуждение датировано 2005 годом, но общая суть актуальности не потеряла.
Постоянная ссылка ·
Добавьте на news2.ru
Похожие записи:
- Сертификация по ASP.NET на Brainbench
- Интервью с руководителем PhpShop
- UTel - Узнай свой номер!
- Парсинг и генерация RSS на PHP и Perl
- Составление полного списка файлов заданной папки на Perl
Сергей febb said,
Июнь 26, 2008 @ 09:13
Заинтересовала задача
Первый способ там неправильный. Чтобы найти правильный ответ, нужно знать сумму всех весов. Также получать сначала сумму, а потом еще раз проходить массив - неэффективно. Также неэффективно несколько раз получать RND - нафиг это надо вообще. Решение на мой взгляд такое. Задача решается двумя циклами, каждый из которых проходится только один раз. Опишу наглядно, так как подзабыл синтаксис перла уже давно.
Чтобы лучше понять, можно представить список в виде лунок, ширина каждой равна весовому коэффициенту. Ставим лунки последовательно и кидаем шарик
Получается рулетка с лунками неодинаковой ширины 
Функция (заводим массив чисел, возвращаем порядковый номер числа)
1-й цикл.
Имеем массив 1 1 3 4 1 5.
Заместо них, чтобы не тратить память, в массив циклом суммируем число с предыдущим, то есть заводим вместо него
1 2 5 9 10 15.
тут же с каждой итерацией считаем сумму , прибавляя каждый новый член, получаем SUM = 42. Сумму сразу, как в примерах, считать неэффективно.
После первого цикла вычисляем RND * SUM, допустим получили 0.4 * 14 = 5,6
2-й цикл.
вариант а) Простейший. Начинаем сравнивать полученную RND * SUM со значением в каждой лунке.
1) 5,6