Как реализовать алгоритм частоты появления?

Question

[hiwibu]

Есть массив, в нем 100 объектов. На текущий момент при каждом показе выводится случайный объект.
Теперь нужно, чтобы на основании поля приоритета определнные элементы показывались чаще
Например, если поле priority = 2, то элемент показывается в 2 раза чаще. Если 3, то в 3.

У кого есть какие мысли, как это можно реализовать?

Answer 1

[GavriKos]

Ну так обычное распределение по весам. Каждый объект имеет вес. Суммируете все веса, кидаете рандом в пределах этой суммы. Далее начинаете идти по массиву, и суммировать веса. Как только просуммированный вес станет больше выданного рандомом - вот он ваш элемент.
Пример.
Три объекта, с весами 2, 1, 1. Кидаете рандом до 4. Выпадает например 3. Начинаете суммировать - сначала 2 - пропускаем первый элемент. Потом добавляем 1 - и это равно тому что выдал рандом. Возвращаем второй элемент.
Главное с пороговыми значениями не напутать.

Comments

[#алгоптимизируй #отботизируй]

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

[GavriKos]

С Sharp Абсолютно верно. Только вот если приоритеты очень сильно различаются - то ваш способ может быть затратным.

[#алгоптимизируй #отботизируй]

GavriKos: А я и не предлагал использовать этот способ. =)

[xmoonlight]

GavriKos: Excellent!

Answer 2

[Андрей]

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

Т.е. 100 объектов - 100 счетчиков.

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

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

И так каждый раз. Таким образом получаем отображение наименее показанного объекта с учетом приоритетов минимальными усилиями и с достаточно прозрачной логикой.