Как выбрать рандомную запись с бд на основе веса записи?

Question

[dfhusfhgsuo3]

Здравствуйте.

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

Допустим есть 4 записи в таблице, у каждой значение веса (как часто она будет попадаться 1-10).

Вариант с rand() в запросе плох, ибо большая нагрузка, трафика много.

Второй вариант, который мне удалось найти, создавать массив на N слотов с каждой записью. Каждую запись добавляем в массив по весу. И далее обычным shufle получаем уникальную строку.

Но в таком случае каждому человеку нужно будет делать массив, если таких 50-100 запросов в секунду - уже напряжно.

Может есть ещё какие-то варианты для такой выборки?

Спасибо!

Answer 1

[Slava Rozhnev]

Генерируем в РНР случайное число от 1 до количества записей. Выбираем строку по этому ID:

<?php
$query = "SELECT MAX(id) AS max FROM test";
$stmt = $pdo->prepare($query);
$stmt->execute();
$row = $stmt->fetch(PDO::FETCH_ASSOC);
$max_id = $row['max'];

$query = "SELECT * FROM test WHERE id >= ? LIMIT 1";

$stmt = $pdo->prepare($query);
$stmt->execute([rand(0, ($max_id-1))]);

$row = $stmt->fetch(PDO::FETCH_ASSOC);

print_r($row);

share PHP code

Comments

[rPman]

решение не учитывает веса а еще из-за дыр в списке значений id это не будет работать как ожидается, но если завести специальное поле - счетчик и обновлять его у всех записей при удалении добавлении записей, то будет работать, только вот обновлять эффективно такой список не получится

Answer 2

[rPman]

Мне кажется эта задача красиво средствами базы данных не решается.
Любое решение будет либо медленным, либо вероятностное распределение итоговое не будет желаемым.

100 запросов в секунду - зачем такой нетипичной задачей грузить базу данных?

Задайся вопросом, сколько у тебя записей? миллионы? миллиарды? может эффективнее будет держать список id на бакэнде массивом и выбирать от туда?
* Запили миниатюрный сервис с сокетами, в который бакэнд при удалении или добавлении записи будет присылать id, а при перезапуске будет загружать весь список id... памяти это занимать будет порядка 16х от количества записей умножить на логарифм (зависит от того какие списки поддерживает бакэнд, нужно хранить упорядочный num -> id, причем это просто массива, при добавлении id добавляется в конец, а при удалении - на место удаленного ставится элемент с конца, к сожалению тогда для быстрого удаления нужен map: id->num).
* Списков таких должно быть несколько - свой по каждому значению веса (считается что вес - целочисленный и вариантов значений значительно меньше общего количества записей), соответственно каждый id попадает в свой список.
* Каждый раз, как идет запрос на случайный id, считаешь два случайных числа:
- первое на интервале [0..максимальное значение веса) - выбираешь какой вес сейчас сработает
это нужно делать с учетом вероятности, которое соответствует каждому весу, т.е. для каждого веса свой интервал значений случайного числа, для 1 это будет попадание между [0..1), для 2 - [1..3), для 3 - [3..6), для 4 - [6..10),.. макс значение интервала равно сумма арифметической прогрессии 1....N где N максимальное значение веса. Левое значение интервала для n считать по формуле суммы арифметической прогрессии а правое + значение веса для него.
- второе, [0..максимальное значение num в соответствующем списке)
второе число даст искомый номер в массиве, а значит и id.
* Для значений весов которые не используются (пустые списки id) нужно будет исключать такое число из списка доступных значений весов, делать новый список с меньшим количеством и давать соответствие значений их этого нового списка с меньшим количеством весов и общим, чтобы такие неиспользуемые веса не попадались.
К примеру из весов 1..10 используются только 1,4 и 10, тогда делаем получаем новый список из 3 элементов, но в формуле расчета интервала для вычисления правой границы использовать значение веса, т.е.:
[0..1), [1,5),[5..15) - общий интервал [0..15)

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

Трудоемкость алгоритма О(1) с очень маленькой константой, но требует память O(n)= n*log(n) с процессором O(n) log(n) на любые модификации.

p.s. Данный алгоритм можно реализовать и в базе данных, на тригерах, так как держать в оперативной памяти списки не требуется, причем базы могут быть отдельные от реальной (очень неудобно и повышенная нагрузка на процессор, лучше использовать key->value базы данных только как хранилище списков id)