Выберите случайную строку, но с коэффициентом

Question

У меня есть набор данных, каждый из которых имеет число «шансов» от 1 до 100. Я стараюсь сделать это наиболее эффективным способом. Коэффициенты не обязательно составляют до 100.

У меня было несколько идей.

a) Выберите весь набор данных, а затем добавьте все коэффициенты и создайте случайное число от 1 до этого числа. Затем пройдите через набор данных, вычитая коэффициенты из числа до тех пор, пока оно не станет 0.

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

б)

SELECT * FROM table WHERE (100*RAND()) < odds 

Я считал LIMIT 0,1

Но если элементы имеют одинаковую вероятность только один из будет возвращен

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

Я думаю, я мог бы order by odds ASC затем взять весь набор данных, а затем с PHP взять случайный из строк с теми же шансами, что и первая запись (самая низкая).

Кажется, это неуклюжие решения.

У кого-нибудь есть превосходное решение? Если нет, какой из вышеперечисленных вариантов лучше?

Answer 1

Я не пробовал, но возможно что-то вроде этого (с? Случайным числом от 0 до SUM(odds) - 1)?

SET @prob := 0; 

SELECT 
    T.*, 
    (@prob := @prob + T.odds) AS prob 
FROM table T 
WHERE prob > ? 
LIMIT 1 

Это в основном так же, как ваша идея а), но полностью в один (ну, технически два, если считать переменные команды настройки) SQL.

Answer 2

Выполняйте некоторые предварительные работы, добавьте несколько столбцов в таблицу, которые помогут выбрать. Например предположим, что эти строки

X 2 
Y 3 
Z 1 

мы добавим некоторые кумулятивные значения

Key Odds Start End 
X 2  0  1  // range 0->1, 2 values == odds 
Y 3  2  4  // range 2->4, 3 values == odds 
Z 1  5  5  // range 5->5, 1 value == odds 

Start и End выбираются следующим образом. Первая строка имеет начало нуля. Последующие строки имеют начало больше, чем предыдущий. Конец - это (Start + Odds-1).

Теперь выбрать случайное число R в диапазоне от 0 до Max (End)

Select * from T where R >= T.Start and R <= T.End 

Если база данных является достаточно умным, мы можем, мы сможем использовать

Select * from T where R >= T.Start and R <= (T.Start + T.Odds - 1) 

Я спекулируя что наличие столбца End с индексом может дать лучшую производительность. Кроме того, Max (End), возможно, где-то спрятался и обновляется триггером, когда это необходимо.

Ясно, что есть некоторые проблемы при обновлении Start/End. Это может быть не так уж плохо, если либо

• Содержимое таблиц являются стабильными
• или вставки в природе некоторым образом упорядочен, так что каждая новая строка просто продолжается от старого высокого.

Answer 3

Если у вас есть индекс на столбце шансов, и первичный ключ, это будет очень эффективным:

SELECT id, odds FROM table WHERE odds > 0 

база данных не будет даже читать из таблицы, было бы получить все, что нужно от индекса шансов.

Затем вы выбираете случайное значение между 1 и числом возвращенных строк.

Затем выберите эту строку из массива возвращенных строк.

Затем, в конце концов, выделить всю строку целевой:

SELECT * FROM table WHERE id = ? 

Это обеспечивает равномерное распределение между всеми рядами со значением шансов.

---

В качестве альтернативы поместите коэффициенты в другую таблицу с помощью первичного ключа автоинкремента.

Odds 
ID  odds 
1  4 
2  9 
3  56 
4  12 

Сохраните внешний ключ ID в основной таблице вместо значения шансов и проиндексируйте его.

Сначала получите максимальное значение. Это никогда не касается базы данных. Он использует индекс:

SELECT MAX(ID) FROM Odds 

Получите случайное значение от 1 до макс.

Затем выберите запись.

SELECT * FROM table 
JOIN Odds ON Odds.ID = table.ID 
WHERE Odds.ID >= ? 
LIMIT 1 

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

Существует целая глава по случайному выбору в книге SQL Antipatterns.

Answer 4

Что делать, если вы взяли свой код и добавили ORDER BY RAND() и LIMIT 1?

SELECT * FROM table WHERE (100*RAND()) < odds ORDER BY RAND() LIMIT 1 

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

Answer 5

select * from table 
where id between 1 and 100 and ((id % 2) <> 0) 
order by NewId() 

Answer 6

Хм. Не совсем понятно, какой результат вы хотите, так что несите меня, если это немного сумасшедшее. При этом, как насчет:

Сделать новый стол.Таблица представляет собой фиксированные таблицы данных, и выглядит следующим образом:

Odds 
==== 
    1 
    2 
    2 
    3 
    3 
    3 
    4 
    4 
    4 
    4 
etc, 
etc. 

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

Тогда просто выберите один из этих наборов наугад.

Answer 7

Общее решение, подходящие для O (журнал (п)) обновления, что-то вроде этого: объекты

• магазин, как листья (сбалансированного) дерева.
• В каждом узле ветви сохраняются веса всех объектов под ним.
• При добавлении, удалении или изменении узлов обновите вес своих родителей.

Затем выберите число от 0 до (общий вес - 1) и пройдите по дереву, пока не найдете нужный объект.

Поскольку вы не заботитесь о порядке вещей в дереве, вы можете сохранить их как массив из N указателей и чисел N-1.