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

Question

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

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

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

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

b)

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

Я рассмотрел LIMIT 0,1

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

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

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

Похоже на неуклюжее решение.

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

Answer 1

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

 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

Начало и конец выбираются следующим образом. Первый ряд имеет начало с нуля. Последующие строки имеют начало на один больше, чем предыдущий конец. Конец (Старт + Коэффициенты - 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 2

Общее решение, подходящее для обновлений O (log (n)), выглядит примерно так:

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

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

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

Answer 3

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

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

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

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

Затем просто выберите один из этого набора случайным образом.

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

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

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

SELECT MAX(ID) FROM Odds

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

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

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

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

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

Answer 7

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

SET @prob := 0;

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

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