Xpoint
   [напомнить пароль]

вероятностный выбор из таблички

Метки: [без меток]
[удл]
2005-10-17 17:09:15 [обр] dyker(0/3)[досье]

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

id rate
1 5
2 20
3 25

мне нужно выбрать из нее 1 строчку с вероятностью рассчитываемой из rate (то есть rate/sum(rate), для приведенной таблички вероятности соответственно: 0.1, 0.4, 0.5,). Пока есть только один вариант решения:
- сгенерить случайное число (от 0 до 1)
- выбрать все строчки, отсортированные по возрастанию rate
- начать строить отрезок следующего вида (не обязательно до конца, достаточно до того момента пока длина отрезка не превысит выпавшее число):
|---|------------|---------------|,
где длина каждого отрезок равна rate/sum(rate) для соответствующей строки. В какой отрезок попадет выбранное число - ту строку и использовать.

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

PS
СУБД - mysql 4 (доступна любая версия 4-ой ветки)

спустя 15 минут [обр] GRAy(8/259)[досье]

dyker[досье] Мне лично не понятно вот это:

мне нужно выбрать из нее 1 строчку с вероятностью рассчитываемой из rate (то есть rate/sum(rate), для приведенной таблички вероятности соответственно: 0.1, 0.4, 0.5,)

?

спустя 1 минуту [обр] Алексей В. Иванов(2/2861)[досье]
Сколько записей в таблице планируется быть?
спустя 12 минут [обр] dyker(0/3)[досье]
думаю порядка нескольких тысяч должно хватить
спустя 13 минут [обр] dyker(0/3)[досье]

GRAy[досье]

Мне лично не понятно вот это: ...

А что непонятно? Что такое вероятность или как она вычисляется или еще что-то?
Я привел конкретный пример таблицы с 3 записями и как для них вычисляется вероятность. (значение поля rate для строки делить на сумму поля rate для всех строк). При выборке мне нужно выбирать только одну строку с определенной вероятностью. Не знаю как понятнее объяснить... :(

спустя 1 час 32 минуты [обр] GRAy(8/259)[досье]

dyker[досье]
Непонято всё ;)

...
- сгенерить случайное число (от 0 до 1)
- выбрать все строчки, отсортированные по возрастанию rate
- начать строить отрезок следующего вида (не обязательно до конца, достаточно до того момента пока длина отрезка не превысит выпавшее число):




...

Зачем всё это? Непонятно как вы с помощью этой последовательности действий решаете поставленную задачу.
Насколько я понял то что вам требуется. Достаточно быстрым решением будет два последовательных запроса:

select sum(rate) from table;

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

select id, rate
from table
where rate/:summa = :prob

Всё. Это НЕ гарантирует вам единственности результата на произвольных данных, т.к. условию отбора может удовлетворять более чем одна запись.
Дальнейшее ускорение возможно, но ИМХО на нескольких тысячах записей можно и не париться.

спустя 5 минут [обр] Алексей В. Иванов(2/2861)[досье]
частотный (весовой) коэффициент
Для mysql одним запросом не получится, скорее всего т.к. нужно знать сумму всех весов, поэтому, придется выбирать все id,rate, а затем, за один проход, выбирать полную строку из БД по id.
Powered by POEM™ Engine Copyright © 2002-2005