Как выбрать случайный элемент из списка с учётом его веса?

Question

[Александр Буки]

Добрый день.
Засела в голове одна задачка с собеса.
Заранее прощу прощения за не совсем точно сформулированные условия, но суть примерно такая:
Есть массив рекламодателей.

[
{data: {...}, w: 5},
{data: {...}, w: 1000}
{data: {...}, w: 3}
]

Где data -это инфа которую нужно разместить на рекламном баннере на вашем сайте, а w - это "вес" этого рекламодателя, грубо говоря сумма, которую он заплатил.
Необходимо написать алгоритм, который случайным образом будет выбирать рекламодателя , но при этом частота попадания должна зависеть от "веса" - w.
То есть если w = 1000, то баннер должен показываться чаще, чем у рекламодателей с меньшим w.

Answer 1

[Николай Панаитов]

Можно такой подход. Интересно критику почитать.

var banners = [];
// Генерируем тестовый массив баннеров
for( var i = 1; i <= 5; i++ ){
	banners.push( {
		data: i,
		w: Math.floor( Math.random() * 1000 ) + 1 // Вес баннера от 1 до 1000 к примеру
	} );
}
console.log(banners);
var wt = 0; // Сумма веса всех баннеров
for( var i = 0; i < banners.length; i++ ){
	var banner = banners[i];
	banner.bound = wt += banner.w; // Определяем границу, которая зависит от веса
}
console.log(banners); // Проверить наглядно какие границы созданы
// Генерируем число от 0 до wt
var r = Math.floor( Math.random() * wt + 1 );
for( var i = 0; i < banners.length; i++ ){
	// Ищем какой баннер попал в полученное случайное число
	var banner = banners[i];
	if( r > banner.bound - banner.w && r < banner.bound ){
		console.log('banner ' + banner.data); // В итоге при таком подходе вероятность выпадения более ценного баннера выше, главное чтоб вес был > 0, иначе баннер найден неправильно.
	}	
}

Comments

[hint000]

Интересно критику почитать.

Математически верно. А стиль критиковать не хочу.

[Николай Панаитов]

hint000, ну говнокод понятное дело, сам алгоритм интересно было, типа есть ли более производительные вариант.

[hint000]

Николай Панаитов,

есть ли более производительные вариант

Можно разменять скорость на память. Имеет смысл, если выбор баннера происходит в [бесконечном] цикле. Тогда делаем так: заводим массив из wt элементов, заполняем его номерами баннеров всего один раз. Тогда r = Math.floor( Math.random() * wt ); сразу будет индексом элемента, содержащего номер баннера, без перебора.

[hint000]

Bavashi,

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

Ну а какой ещё математический смысл можно вкладывать в вес? Если у одного вес 1000, а у другого 10, то первый и должен показываться в 100 раз чаще, иначе зачем ему давать вес в 100 раз больше?
Если надо, чтобы первый показывался в 10 раз чаще второго, то надо первому задать вес в 10 раз больше.

По-моему, это очевично из условий, но если всё не так, то пусть автор вопроса прокомментирует. А то у нас получится как в школе на уроках литературы: "Что имел в виду автор?" (а в это время Гоголь, Тургенев и Чехов в гробах переворачиваются, узнав, что они имели в виду) :)

[Николай Панаитов]

Bavashi, Смотрите какая логика
Допустим 5 баннеров
ID | Стоимость (вес)
1 | 10
2 | 10
3 | 15
4 | 20
5 | 100
___________
Получается мы складываем стоимости и получаем общую сумму для 5 баннеров: 155
Теперь вероятность показа будет такая
1 | 10/155=0.064
2 | 10/155=0.064
3 | 15/155=0.096
4 | 20/155=0.129
5 | 100/155=0.645 -- для самого ценного баннера вероятность выпадения 64.5%
Мы не можем просто зная случайное число от 0 до 155 определить какой именно баннер, поэтому нужно хранить некий диапазон чисел, в который входит процент определенного баннера (то есть каждый баннер имеет какой-то интервал выигрышных для него чисел, на общем интервале), благодаря чем мы и находит к какому интервалу (баннеру) принадлежит сгенерированное случайное число. !!! Чем больше вес баннера, тем больше диапазон чисел принадлежит данному баннеру из общего интервала!
На счет индекса wt, так как баннеры могут быть одинаковой стоимости, то данный вами вариант индексации не годится. Может и годится, но нужно хранить [ ключ wt => [массив баннеров], то есть если определен wt получили массив баннеров с одинаковым весом и вывели рандомный баннер со списка. Но мне кажется при таком подходе вероятности выпадания баннеров нарушаются, тобишь не совсем верными получаются

[hint000]

Bavashi,

Так было бы честнее.

Ну смотрите: вот есть всего два клиента вы и я.
Я заплатил 10 рублей, а вы заплатили 990 рублей. Ваш баннер показали 99 раз, мой показали 1 раз. Теперь я говорю: "я платил не за то, чтобы мой баннер в 99% случаев не показывали, проще было бы объявить, что показывается баннер с весом 990. Так было бы честнее". Вот скажите, вам - заплатившему 990 рублей было бы честнее, чтобы мой баннер показывали чаще, чем в 1% случаев? Ну, например, оплата была бы та же самая, но мой баннер показывали бы в 10%, а ваш в 90%? В этом случае вы, как клиент говорите: "минуточку..." :) Заводите себе 9 клиентских учётных записей, с каждой платите по 10 рублей и получаете по 10% показов. В итоге вы с такой хитростью платите 90 рублей и получаете те же 90% показов, что получили бы за 990 рублей. А тот, кто показывает баннеры, получает в сумме 100 рублей вместо 1000, за то же самое количество показов. По вашему, это честнее?

[hint000]

Bavashi, окей, сделаю последнюю попытку достучаться до логики.
Пусть это будут не показы баннеров, а булки хлеба. По 10 рублей за булку. Я отдал 10 рублей и получил одну булку. Вы отдали 990 рублей и получили 99 булок. Я кричу: "Безобразие! Честнее было бы сказать, что весь хлеб получает тот, кто заплатил 990 рублей! Требую дать мне больше хлеба за мои 10 рублей!"
Какая разница, товары мы покупаем или услуги?

На мой взгляд, отдать 10 рублей и не увидеть своего баннера тоже не честнее.

Да с какого фига не увидеть-то? Увидеть один раз из ста - ровно столько, за сколько уплачено. Кто мешает заплатить больше и получить больше?

[Николай Панаитов]

По мне так, это рандом и все более менее правильно для всех, если ты хочешь рекламировать что-то, то будь добр приложи к этому какую-то денюшку, а так псевогенерато такой, что в любом случае будут показываться и баннеры обычных пользователей, просто реже чем те, которые по дороже!