Случайная ротация баннеров в зависимости от стоимости?

Question

[Илья Лесных]

Допустим мы имеем систему показа баннеров. Каждый показ баннеров обходится его владельцу в какую-то денежку, размер которой он выставляет сам. Например средняя цена 1 рубль, а кто-то поставил 2 рубля. Хочется чтобы баннеры тех, кто готов тратить больше денег — крутились чаще, но при этом давали возможность более дешевым баннерам так же отображаться в рекламном блоке (допустим, что блок — это страничка с 5 рандомными баннерами). Воспоминания из математики подсказывают мне, что нужно воспользоваться логарифмами/экспонентами для расчета вероятности показа баннера в конкретном блоке в зависимости от его стоимости, но до конца продумать уравнение не могу. Подскажите алгоритм.

Comments

[s0rr0w]

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

[Илья Лесных]

нет, не требуется гарантированный показ, но требуется вероятностный показ.

Answer 1

[ksurent]

Берется отрезок (например, [0, 1]), делится на N частей, где N — количество баннеров. Размер каждой части пропорционален стоимости. Загадывается случайное число в промежутке от 0 до размера отрезка. В какой подотрезок попало число, тот баннер и показывается. В принципе, очень похоже на то, что уже описали выше.

Пример: есть три баннера стоимостью 50, 30 и 10 рублей. Берем отрезок [0, 1] и делим на части:
1. [0, 0.5] — первый баннер
2. (0.5, 0.8] — второй
3. (0.8, 1] — третий (до единицы, т.к. баннеров больше нету)
Загадываем число rand(0, 1), показываем баннер того подотрезка, куда оно попало.
Т.к. у первого баннера самая большая стоимость, то и подотрезок у него самый большой, а значит вероятность попадания случайного числа в этот подотрезок тоже становится выше (при условии, что rand() выдает числа с равномерным распределением).

Comments

[Илья Лесных]

Скорее тогда нужно сделать так: 50+30+10=90=100%. Тогда 50 рублей ~ 50*100/90=55% [0, 0.55]
Неплохая идея, спасибо.

[Салават Ситдиков]

Aliance, а как вы получите 0.6 randomом? Будете делить на 100? Так это та же методика, при которой требуется вводить коэффициент, что про баннер при цене 57 копеек.

[Илья Лесных]

В общем-то я реализовал данный алгоритм, пока локально на кривых данных и с выборкой из массива, а не из БД — но сам по себе алгоритм работает как мне нужно. Спасибо.

[Илья Лесных]

Нашел небольшую недоработку что ли: при примере с 3 баннерами и разными ценами (5,3,1) все отрабатывает идеально. На практике же баннеров будет больше 100 -> если оставить алгоритм по такой схеме, то проценты вероятности показа каждого баннера будут меньше 1%. Нужно группировать по ценам. То есть есть 10 баннеров с ценами 1,1,2,2,2,3,3,3,3,3 — тогда получаем 1-20% (0-20), 2-30% (20-50), 3-50% (50-100) и дальше если попадаем, скажем, в промежуток (50-100), то уже рандомно берём баннер с ценой 3 рубля.

[Салават Ситдиков]

Aliance,
1. Вам приходится хранить данные об отрезках в которые попадают баннеры
2. Выбирать из отрезка рандомно баннер.
Вы выполняете в два раза больше работы, чем можно было бы.

Answer 2

[Georg]

x = random() //x от 0 до 1
sum = s1+s2+s3 //сумма стоимостей
if (x<s1/sum) then banner1 //если х попало в интервал показа первого баннера, то покажем его
elseif (x<s2/sum) then banner2
elseif (x<s3/sum) then banner3

алгоритм такой

Comments

[Georg]

Виноват последние 2 строки кода читаем как
elseif (x<(s1+s2)/sum) then banner2
elseif (x<1) then banner3

[Илья Лесных]

Наверное не получится так: сумма стоимостей — неизвестны, а количество баннеров — непостоянны.

[Georg]

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

Answer 3

[Салават Ситдиков]

Хм, своего рода цена — это приоритет. Тогда можно воспользоваться следующим алгоритмом.
У нас есть n приоритетов. (1, 2, 3… n). Мы создаем массив данных — куда загоняем баннеры по следующему правилу:
Каждый баннер будет загнан k раз, где k — приоритет. А потом из этого массива будем рандомно выбирать баннер для показа.

Баннер 1 = 1 рубль
Баннер 2 = 2 рубля
Баннер 3 = 3 рубля
Массив = (Баннер 1, Баннер 2, Баннер 2, Баннер 3, Баннер 3, Баннер 3)

Выбирая рандомно из этого массива вы как раз решите свою задачу.

Comments

[Lev Lybin]

костыльный вариант:)

[Илья Лесных]

То есть цена 3 рубля = приоритет 3? А при цене в 0,57 рублей — сколько раз должен быть загнан баннер? :)

[Салават Ситдиков]

Введите коэффициент x 100 и будет вам целые числа )

[Илья Лесных]

Я так понимаю, что предложенное Вами решение и то, что выше (которое я пометил как решение) — одно и тоже, только разными словами? Тогда предлагаю обсуждать его там.

Answer 4

[leventov]

Это weighted random sampling problem.
Далее в гугле много много ссылок, базовые алгоритмы несколько сложнее чем приведенные выше подходы.

Comments

[Илья Лесных]

Так и не удалось найти алгоритма. Я так понял, что это «случайная выборка по весам»?

Answer 5

[merlin-vrn]

Составляете список из всех вариантов, причём те, которые должны быть в два раза чаще — появляются в списке дважды, соответственно, те, которые должны быть отображены 9 раз из 10, будут заполнять 90% списка. И потом из этого списка выбираете уже произвольный случайный элемент.

Список пересчитывается только при изменении весов или самого набора элементов.

Пример:
[1, 2, 2, 3, 4, 4, 4, 4, 2]
При случайном выборе мы получим:
1 — с вероятностью 1/9
2 — с вероятностью 3/9 = 1/3
3 — с вероятностью 1/9
4 — с вероятностью 4/9

Comments

[merlin-vrn]

Вообще, да, это классический wrandom, не понимаю, в чём проблема

Answer 6

[Андрей Кравчук]

openx.com/

Comments

[Илья Лесных]

К чему здесь эта ссылка? Там разве содержится алгоритм?

[Андрей Кравчук]

Каков вопрос — таков ответ. Судя по вопросу, вам лучше воспользоваться готовой системой баннерной рекламы, а не велосипеды изобретать. А по сути: задайте себе вопрос — какая должна быть зависимость вероятности показа баннера от его стоимости, и вы поймете как реализовать такой алгоритм.

[Илья Лесных]

Судя по ответу, вам лучше было промолчать.

Answer 7

[ComodoHacker]

Вам стоит почитать про алгоритмы планирования задач в операционных системах (task scheduling). Можно отталкиваться от них.

С другой стороны, у вас нет таких жестких ограничений, как при планировании задач, (время на планирование, дискретные приоритеты) поэтому можно рассмотреть и другие подходы.

Comments

[Илья Лесных]

поэтому можно рассмотреть и другие подходы

какие?

Answer 8

[Lev Lybin]

табличка:
ссылка, изображение, цена за показ, кол-во показов
link | img | cost | count
SELECT link, img FROM banners ORDER BY (count / cost) ASC LIMIT 1
пишу с хода идею, мог ошибиться, но вроде должно работать

Comments

[Lev Lybin]

кол-во показов — сделанных, т.е. при показе плюсуем, за одно и статистика

[Илья Лесных]

там уже есть 100500 табличек, отвечающих за вывод нужного тизера. Такая сортировка думаю будет тормозить, да и показы хранятся в отд. табличке.

Answer 9

[Иван Б]

Попробуйте так:
ORDER BY -LOG(1.0 – RAND()) / weight