Допустим, вам нужен режим перемешивания в вашем музыкальном сервисе или сервисе Netflix. Вам придется сочетать случайность с весом, например популярность, релевантность и т. Д. . С этого момента я буду использовать термин “взвешенный” для представления комбинации таких входных данных, как популярность, актуальность, новизна и т.Д
Подходы
Существует множество подходов к этому, которые приведут к несколько иным результатам. Сейчас мы коснемся только пары идей, но, возможно, в будущем добавим еще больше.
📙 Пул популярности
Один из подходов к извлечению случайно взвешенных данных состоит в том, чтобы сначала ограничить доступные данные, а затем выбрать случайный элемент из списка.
Пример : Возьмите 500 лучших песен, возглавляющих чарты за десятилетие, и просмотрите их.
Этот подход хорош, если вы хотите всегда исключать менее популярные песни, но ловушка заключается в том, что вы, по сути, ограничиваете себя только 500 песнями из коробки; если вы когда-либо использовали Pandora, вы будете знать, насколько это может повторяться.
📒 Взвешенный Массив
Этот подход аналогичен нашему окончательному подходу, но менее эффективен. Я хотел сначала обсудить это, потому что, скорее всего, люди будут плохо думать и внедрять эту технику.
Допустим, у вас есть номера 1-6, и вы хотите, чтобы 2 и 4 появлялись чаще, чем остальные. В нормально распределенном наборе у вас будет массив, подобный:
[1, 2, 3, 4, 5, 6]
И вы получите такую случайную запись, какую только может сделать для вас генератор случайных чисел. Однако простой способ добавить вес здесь – увеличить количество раз, когда появляется число, например:
[1, 2, 2, 3, 4, 4, 5, 6]
Если вы выберете случайное число из этого набора, то, скорее всего, это будет 2 или 4, но это все равно может быть все остальное. В отличие от подхода Пул популярности , это все равно позволит выбирать непопулярные товары с меньшей вероятностью.
Чтобы определить колеблющиеся веса, вы могли бы добавить больше чисел:
[1, 2, 2, 2, 2, 2, 2, 2, 3, 4, 4, 4, 5, 6]
Просто на первый взгляд, какой предмет, по вашему мнению, с наибольшей вероятностью появится здесь?
Это чрезвычайно простой способ добавления весов, но он совсем не эффективен. Это хорошо для бросков кубиков, но не более того.
📗 Уменьшение популярности
Это мой предпочтительный подход по сравнению с описанным выше. То, что мы собираемся здесь сделать, – это вычесть числа друг из друга, чтобы получить наиболее популярный товар. Существуют различные варианты этого подхода, которые вы можете изучить, поэтому не думайте, что эта реализация является конечной целью.
Давайте сначала начнем с описания простого набора данных; мы будем использовать фильмы 2019 года. Я назначу им произвольный вес ( 0-1 ), который, как мы притворяемся, составлен из отзывов пользователей, релевантности для пользователя и т.д.
0. [0.91] Parasite 1. [0.89] Avengers: Endgame 2. [0.85] Joker 3. [0.76] Once Upon a Time... In Hollywood 4. [0.74] Marriage Story 5. [0.71] The Irishman 6. [0.61] Midsommar 7. [0.57] Ad Astra 8. [0.49] Yesterday 9. [0.25] Cats
Пример: Пример:
Как вы можете видеть, у нас есть подборка в основном хороших фильмов ( 0-5 ), затем подборка меньших фильмов. Вы также заметите, что наши веса могут быть любыми, например 0.91481 что усложняет использование описанного выше подхода с кубиками, когда мы добавляем больше элементов в массив.
В этом примере показано всего 10 фильмов, но за эти годы мы могли бы иметь дело с сотнями тысяч.
Цель этого подхода состоит в том, чтобы найти фильм, который вероятно хорош, но не полностью исключать другие, которые могут быть менее популярными. Вы когда-нибудь слышали о культовой классике? Бойцовский клуб , “Вещь” и “Бегущий по лезвию” провалились в прокате, но стали классикой.
Во-первых, мы захотим суммировать все наши веса в число.
// Realistically, you'd iterate or use a SQL SUM(...) function const sum: number = 0.91 + 0.89 + 0.85 + 0.76 + 0.74 + 0.71 + 0.61 + 0.57 + 0.49 + 0.25; // 6.78
Во-вторых, нам понадобится случайное число между 0 – суммой (6,78).
const sum: number = 6.78; // from above const target: number = Math.random() * sum; // 4.76821
Наконец, мы перебираем наш случайный набор данных, вычитая числа из этой целевой переменной. Когда мы опускаемся ниже нуля, мы берем именно тот товар, который с большей вероятностью будет популярен.
Прежде чем мы это осуществим, давайте поговорим об этом.
// Implemented below the explanation
Почему эта техника работает?
Когда мы суммируем цифры, чтобы достичь 6.78 , мы создаем верхнюю границу для нашего случайного числа. Этого не может быть 6.80 потому что у нас просто не так много фильмов. Если бы мы использовали меньшее число, например 6.00 , это означает, что мы бы оставили некоторые фильмы без рассмотрения. Суммируя все, он учитывает все наши возможности.
Мы берем случайное число в этих пределах в качестве произвольной цели . Это определит, сколько итераций нам нужно пройти, чтобы найти наш фильм.
Затем мы перебираем наши фильмы и вычитаем вес из нашей цели , пока не достигнем нуля. Это работает, потому что больший вес с большей вероятностью приведет вас к нулю, но меньший вес все равно может подтолкнуть вас к черте.
Например, если ваша цель находится в 0.75 у популярного фильма есть действительно хорошие шансы переступить черту: 0.75 - 0.91 = -0.16 . Но меньший фильм или несколько меньших фильмов все равно не сработали бы:
0,75 -.50//все еще выше 0,0 0.50 -.31//все еще выше 0.0 0.31 - .02//все еще выше 0.0 0.02 - 0.15 = -0.13//наконец-то
Вы можете увидеть здесь, как потребовалось 4 менее популярных фильма, чтобы преодолеть эту нулевую черту, но 🎊 это был 0.15 это в конечном счете доказало, что менее популярные фильмы МОЖНО выбирать, хотя и реже.
for (let movie of movies) {
if ((target -= movie.weight) < 0) {
return movie;
}
}
Вот еще один пример , в котором используется более равномерно распределенный набор весов, чтобы вы могли более четко видеть, как получаются результаты.
Но, как вы можете видеть, у каждого фильма есть возможность быть выбранным. Наиболее популярные из них выбираются чаще, но даже Кошки могут время от времени показываться.
Если вы будете повторять этот пример снова и снова, вы увидите, что цифры меняются при каждом выполнении, но они будут примерно одинаковыми.
Полный Пример
const movies = [
{ "selected": 0, "title": "Parasite", "weight": 1.0 },
{ "selected": 0, "title": "Avengers: Endgame", "weight": 0.9 },
{ "selected": 0, "title": "Joker ", "weight": 0.8 },
{ "selected": 0, "title": "Once Upon a Time... In Hollywood", "weight": 0.7 },
{ "selected": 0, "title": "Marriage Story", "weight": 0.6 },
{ "selected": 0, "title": "The Irishman", "weight": 0.5 },
{ "selected": 0, "title": "Midsommar", "weight": 0.4 },
{ "selected": 0, "title": "Ad Astra", "weight": 0.3 },
{ "selected": 0, "title": "Yesterday", "weight": 0.2 },
{ "selected": 0, "title": "Cats", "weight": 0.1 },
];
/**
* Get random movie from our list
*
* @param Movie[] movies
* @return Movie
*/
function getRandomMovie(movies) {
const sum = movies.reduce((accumulator, movie) =>
(isNaN(accumulator) ? movie.weight : accumulator) + movie.weight);
let target = Math.random() * sum;
for (let movie of movies) {
if ((target -= movie.weight) < 0) {
return movie;
}
}
// Unreachable
return movies[0];
}
// Test iterations
for (let i = 0, l = 500; i < l; i++) {
const movie = getRandomMovie(movies);
// Increment how many times this movie was selected for demonstrations
movie.selected ++;
}
// Log our movie array to see how many times each was picked
console.log(movies);
😎 Как это может быть лучше/масштабируемо?
Мы полностью суммируем все веса, чтобы определить верхнюю границу нашего коэффициента рандомизации, но если у вас 10 миллионов строк, это может оказаться ненужной затратой. Возможно, вы могли бы выбрать произвольный фиксированный вес, а затем применить этот метод к смещению строк.
Например, если бы у нас было 1000 фильмов, мы могли бы суммировать веса 100 из них. Может быть, вы случайным образом выбираете число от 0 до (1000-100), так что в итоге вы получаете 762 . Запрос на 100 строк в этот момент:
SELECT * FROM `movies` LIMIT 100 OFFSET 762
Я должен отметить, что этот метод позволит вам в большей степени зависеть от ваших данных. Если строки 762-862 все это плохие фильмы, тогда вы будете собирать плохой урожай.
Можно подумать, что способ обойти это – сначала рандомизировать набор данных; и вы были бы правы, но это неэффективно для больших наборов данных.
Лучшим подходом было бы взять случайные числа и проверить, находится ли ваш первичный ключ В наборе данных. Люди, знакомые с Laravel, могут узнать этот стиль по их Нетерпеливой загрузке реализации.
const howManyRows = 10000000;
const sizeOfSet = 10;
let numbers = [];
// Generate random numbers from max set
// NOTE: This isn't dealing with potential duplicates
// but that may be superfluous for such scale.
for (let i = 0, l = sizeOfSet; i < l; i++) {
numbers.push(Math.floor(Math.random() * howManyRows));
}
// Log
console.log(numbers);
// 0: 8316350
// 1: 9670724
// 2: 6592105
// 3: 2823263
// 4: 4172139
// 5: 6591340
// 6: 5969071
// 7: 8285343
// 8: 3639895
// 9: 5067900
Который затем может превратиться в SQL-запрос, подобный:
SELECT * FROM `movies` WHERE `id` IN (8316350, 9670724, 6592105, ...)
Теперь у вас есть эффективно выбранный рандомизированный сегмент чрезвычайно большого набора данных, к которому вы можете применить нашу методику взвешенной рандомизации.
Заключительное Примечание : Описанный выше метод предполагает последовательные числовые идентификаторы и, скорее всего, не будет работать с чем-то вроде Монго ObjectId . Вероятно, для этого есть дополнительные решения, но я напишу о них в другой статье.
Обратная связь
- А ты что подумал?
- Какая ваша любимая техника?
- Вы заметили какие-либо ошибки в моем коде?
- Как это может быть лучше?
- Я что-то пропустил в своей статье?
А до тех пор наслаждайтесь своей взвешенной рандомизацией.
Оригинал: “https://dev.to/mattkenefick/fetch-random-items-that-are-likely-popular-3kpm”