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

Question

[solomonych]

Приветствую!


Есть вот такая интересная задачка, которую мой программист что-то не может никак осилить:


у меня на сайте (строительный портал) решили внедрить что-то типа своей тизерной сети…

написать ее проблем не составило, но вот на чем произошел стопор:


вероятность показа объявлений решили сделать произведением ctr и цены клика, введенной рекламодателем (по системе гугла — выигрывает пересечение высокой цены клика и высокого качества объявления)…


Но вот как эффективно и правильно реализовать такое управления выборкой объявлений, пока не смогли допереть…


Буду благодарен за любые советы!!! :)

Comments

[Vitali Borovik]

Выборку из бд? Какой язык?

Answer 1

[ShouldNotSeeMe]

Если база объявлений в MySQL и объявлений не очень много, то можно приблизительно так:
SELECT… ORDER BY ctr*price+RAND()
где x — некоторый коэффициент

Comments

[solomonych]

Спасибо за совет! Неужели такое простое решение?..

[solomonych]

Кстати, где в этой формуле участвует «х»??

[niko83]

повидимому автор пропустил, должно быть так ctr*price+x*RAND()
rand() выдаёт случайное число от 0 до 1, но мне кажется это не лучшее решение.
Чтоб с низким ctr*price имели хоть какой-то шанс быть показаны X должен быть не меньше чем MAX(ctr*price) — MIN(ctr*price), слишком большой Х будет сводить к минимумому влияние значения ctr*price. Не думаю что самое удачное решение, но в какой-то мере оно решает проблему. Возможно этого вполне хватит.

Answer 2

[Андрей]

Позволю предложить тяжелое математическое решение:

1) нормализация и одновременно определение границ RND() для каждого объявления: ( LEFT[i]; LEFT[i+1] )

NORM=0
for i=0 to N-1
LEFT[i] = NORM
NORM = NORM + CTR[i]*PRICE[i]

2) работа

ADV_ID = GET_i_BY_LEFT_BORDER( RND()*NORM )

Answer 3

[1x1]

ORDER BY RAND() — самый простой, но весьма медленный для объёмных таблиц, это тоже стоит учитывать.