Алгоритм выбора случайного элемента...

← →
Knight © (2011-09-04 01:03) [0]

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

← →
Knight © (2011-09-04 01:18) [1]

Была идея -
1) брать рэндомайзное число от 1 до 6
2) в соответствии с ним извлекать из перемешанного массива {1,1,1,2,2,3} число, которое будет определять из какой части выборки получать строку
3) Делать выборку с сортировкой нужного поля по возрастанию
4) определять границы нужной части (число записей, делится на 3 части).
5) по граничным строкам генерить число, определяющее нужную строку.

Получается, что из первой части будет чаще, из второ реже, из третей ещё реже.

Но как-то мне это не очень нравиться.

← →
Anatoly Podgoretsky © (2011-09-04 01:28) [2]

> Knight (04.09.2011 01:03:00) [0]

Базы они разные бывают

← →
Германн © (2011-09-04 01:32) [3]

> Базы они разные бывают

А это вопрос не по базам. А по алгоритмам.
Только не ясный самому автору.

← →
Knight © (2011-09-04 01:35) [4]

> Только не ясный самому автору.

Точно, нужен пинок в нужном направлении :)

← →
Anatoly Podgoretsky © (2011-09-04 01:43) [5]

> Германн (04.09.2011 01:32:03) [3]

Random и запрос с нужным номером.

← →
Knight © (2011-09-04 01:46) [6]

> Anatoly Podgoretsky © (04.09.11 01:43) [5]

Тогда все строки равноправны, что мне не надо.

← →
MBo © (2011-09-04 08:56) [7]

Пусть дан массив A[] из N положительных чисел.

Насчитаем массив B[k] = Sum[i = 1..k] (1 / A[i])

Теперь на каждый запрос получаем случайное число R = Random*B[N], бинарным поиском находим индекс B, куда попадает R

P.S. Для широкого диапазона чисел функция 1/A может давать слишком резкое распределение.

← →
Anatoly Podgoretsky © (2011-09-04 09:17) [8]

> Knight (04.09.2011 01:46:06) [6]

Используй Оракл

← →
Sha © (2011-09-04 09:45) [9]

> Требуется алгоритм выбора случайной строки из базы данных в зависимости от значения некого поля.

Он такой не один. Какой из них нужен?

← →
Knight © (2011-09-05 11:59) [10]

> Он такой не один. Какой из них нужен?

Который оптимальнее для баз. А вообще, все бы посмотрел.

← →
Sha © (2011-09-05 12:18) [11]

> А вообще, все бы посмотрел.

Все подходящие алгоритмы посмотреть невозможно, т.к. их множество неперечислимо.
Какой из них показать?

← →
Dimka Maslov © (2011-09-05 12:20) [12]

Устанавливаем в зависимости от поля пороговое значение 0 - 100% вероятности 1 - 0% вероятности. Генерируем случайное число в диапазоне от 0 до 1. Если полученное число больше порогового - производим нужное нам действие.

← →
Knight © (2011-09-05 12:37) [13]

> Какой из них показать?

Простой. И чтобы поменьше нагрузка на сервер.

Повторю ещё задачу.
1) Есть таблица базы
2) количество строк примем равным паре сотен тысяч
3) в таблице есть поле - Field1 в котором число от 0 до 500.
4) требуется выдавать "случайную" строку из базы так, чтобы частота её появления была обатно пропорциональна значению поля Field1, т.е. чем больше значение, тем реже она выбирается.

← →
Sha © (2011-09-05 12:42) [14]

> Knight © (05.09.11 12:37) [13]

[7] читал?

> число от 0 до 500
> обатно пропорциональна

1/0 = ?

на клиенте сгенерить параметр, удовлетоворяющий "обратной пропорциональности" (0-500)

сделать селект по field1 = параметр.
добаваить во where второй уровень случайности (синтаксис от сервера зависит)

Задача странная какая-то.
Подозреваю, что в таблице не больше 1000 записей.

← →
Очень злой (2011-09-05 23:53) [17]

> > Какой из них показать?
>
> Простой. И чтобы поменьше нагрузка на сервер.
>
> Повторю ещё задачу.
> 1) Есть таблица базы
> 2) количество строк примем равным паре сотен тысяч
> 3) в таблице есть поле - Field1 в котором число от 0 до
> 500.
> 4) требуется выдавать "случайную" строку из базы так, чтобы
> частота её появления была обатно пропорциональна значению
> поля Field1, т.е. чем больше значение, тем реже она выбирается.
>
>

Частота выбора определяется точным значением поля? Или достаточно того, что чем больше значение поля - тем частота ниже?

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

← →
CRLF (2011-09-06 11:32) [18]

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

Экспоненциальное распределение курите

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

select * from T
where 1/T.Field > Random [0,1]

погонял под mssql, на больших кол-вах испытаний примерно похоже.

select
Cast( ROW_NUMBER()OVER(order by IdMainShot) as INT) as NUM,
*
from mainshot MS
where 1/SALDO > RAND()

Хотя, точнее, надо похоже и правду Экспоненциальное распределение смотреть.
Но так по-моему проще и быстрее.

Алгоритм выбора случайного элемента... Найти похожие ветки