Выбор колеса рулетки с помощью SQL-запроса

Я реализую выбор колеса рулетки, и я хотел бы сохранить как можно больше кода в SQL. Моя попытка привела к запросу ниже. $1 — это случайная переменная того же диапазона, что и вес, который я отправляю в код SQL (было неясно, как заставить random() вызываться только один раз). Вес - это размер прорези ряда на колесе. random() — это функция SQLITE, которая возвращает случайное число. Вот запрос полностью:

SELECT id
FROM items
WHERE weight >= $1
ORDER BY random()
LIMIT 1

У меня вопрос, это все еще колесо рулетки? Базовый алгоритм потребовал бы суммирования всех весов, а затем выбора случайного значения в диапазоне 0..sum — это определило бы, какая строка была выбрана. Вместо этого эта подпрограмма сначала фильтрует все строки, которые соответствуют одному случайному числу, затем перемешивает их порядок и выбирает первую.

Одним тонким изменением является использование $1 вместо второго вызова random(). Это может сделать подпрограмму более справедливой, но я не уверен, что это так — это означало бы, что каждой строке был предоставлен собственный шанс быть отфильтрованным или нет.

Итак, я думаю, я спрашиваю, сколько стоит это зеркальное колесо рулетки, поскольку оно явно следует другим шагам. Но отражает ли это результаты?


sql sqlite algorithm roulette-wheel-selection
person Adam Luter    schedule 20.08.2009    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Одна вещь, о которой я только что подумал, это то, что это не колесо рулетки из-за этого простого доказательства на примере:

Если бы у вас было три предмета, по одному каждого веса один, два и три, то колесо рулетки выбрало бы их с вероятностью 1/6, 2/6 и 3/6. Однако моя процедура будет смещать более высокие веса:

Filter, A  ,   B,   C
  1   , 1/3, 1/3, 1/3
  2   , 0  , 1/2, 1/2
  3   , 0  , 0  , 1

Выше вы можете видеть, что для каждого из значений filter ($1 в вопросе) показаны элементы A, B и C с соответствующими шансами выбора. Если сложить все это вместе, то суммарные вероятности A, B и C составят 2/18, 5/18 и 11/18.

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

Это заставляет меня задаться вопросом, если бы вы выбрали фильтр для определенного нелинейного распределения, могли бы вы по-прежнему сделать этот запрос не только зеркальным, но и соответствующим колесу рулетки? И что это будет за дистрибутив?

person Adam Luter    schedule 20.08.2009
comment
Из-за отсутствия какого-либо ответа я соглашусь со своими собственными выводами;) (хотя спасибо за внимание!) - person Adam Luter; 24.08.2009