Случайный взвешенный выбор в T-SQL

Question

Как вы случайным образом выбираете строку таблицы в T-SQL на основе примененного веса для всех строк-кандидатов?

Например, у меня есть набор строк в таблице с весами 50, 25 и 25 (что добавляет до 100, но не нужно), и я хочу выбрать одну из них случайным образом со статистическим эквивалентом результата до соответствующего веса.

Answer 1

Ответ Дейна включает в себя «Я», который вводит закон квадрата. (n*n/2) строк после объединения, где в таблице n строк.

Что было бы более идеально, так это возможность только один раз проанализировать таблицу.

DECLARE @id int, @weight_sum int, @weight_point int
DECLARE @table TABLE (id int, weight int)

INSERT INTO @table(id, weight) VALUES(1, 50)
INSERT INTO @table(id, weight) VALUES(2, 25)
INSERT INTO @table(id, weight) VALUES(3, 25)

SELECT @weight_sum = SUM(weight)
FROM @table

SELECT @weight_point = FLOOR(((@weight_sum - 1) * RAND() + 1), 0)

SELECT
    @id = CASE WHEN @weight_point < 0 THEN @id ELSE [table].id END,
    @weight_point = @weight_point - [table].weight
FROM
    @table [table]
ORDER BY
    [table].Weight DESC

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

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

DECLARE @id int, @weight_sum int, @weight_point int, @next_weight int, @row_count int
DECLARE @table TABLE (id int, weight int)

INSERT INTO @table(id, weight) VALUES(1, 50)
INSERT INTO @table(id, weight) VALUES(2, 25)
INSERT INTO @table(id, weight) VALUES(3, 25)

SELECT @weight_sum = SUM(weight)
FROM @table

SELECT @weight_point = ROUND(((@weight_sum - 1) * RAND() + 1), 0)

SELECT @next_weight = MAX(weight) FROM @table
SELECT @row_count   = COUNT(*)    FROM @table
SET @weight_point = @weight_point - (@next_weight * @row_count)

WHILE (@weight_point > 0)
BEGIN
    SELECT @next_weight = MAX(weight) FROM @table WHERE weight < @next_weight
    SELECT @row_count   = COUNT(*)    FROM @table WHERE weight = @next_weight
    SET @weight_point = @weight_point - (@next_weight * @row_count)
END

-- # Once the @weight_point is less than 0, we know that the randomly chosen record
-- # is in the group of records WHERE [table].weight = @next_weight

SELECT @row_count = FLOOR(((@row_count - 1) * RAND() + 1), 0)

SELECT
    @id = CASE WHEN @row_count < 0 THEN @id ELSE [table].id END,
    @row_count = @row_count - 1
FROM
    @table [table]
WHERE
    [table].weight = @next_weight
ORDER BY
    [table].Weight DESC

Answer 2

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

DECLARE @id int, @weight_sum int, @weight_point int
DECLARE @table TABLE (id int, weight int)

INSERT INTO @table(id, weight) VALUES(1, 50)
INSERT INTO @table(id, weight) VALUES(2, 25)
INSERT INTO @table(id, weight) VALUES(3, 25)

SELECT @weight_sum = SUM(weight)
FROM @table

SELECT @weight_point = ROUND(((@weight_sum - 1) * RAND() + 1), 0)

SELECT TOP 1 @id = t1.id
FROM @table t1, @table t2
WHERE t1.id >= t2.id
GROUP BY t1.id
HAVING SUM(t2.weight) >= @weight_point
ORDER BY t1.id

SELECT @id

Answer 3

Часть "с постепенным увеличением и накоплением [sic] весовой суммы" стоит дорого, если у вас много записей. Если у вас уже есть широкий диапазон баллов / весов (т. Е. Диапазон достаточно широк, чтобы большинство весов записей были уникальными. 1-5 звезд, вероятно, не снизили бы его), вы можете сделать что-то подобное, чтобы выбрать значение веса , Я использую VB.Net здесь, чтобы продемонстрировать, но это можно легко сделать и на чистом языке:

Function PickScore()
    'Assume we have a database wrapper class instance called SQL and seeded a PRNG already
    'Get count of scores in database
    Dim ScoreCount As Double = SQL.ExecuteScalar("SELECT COUNT(score) FROM [MyTable]")
    ' You could also approximate this with just the number of records in the table, which might be faster.

    'Random number between 0 and 1 with ScoreCount possible values
    Dim rand As Double = Random.GetNext(ScoreCount) / ScoreCount

    'Use the equation y = 1 - x^3 to skew results in favor of higher scores
    ' For x between 0 and 1, y is also between 0 and 1 with a strong bias towards 1
    rand = 1 - (rand * rand * rand)

    'Now we need to map the (0,1] vector to [1,Maxscore].
    'Just find MaxScore and mutliply by rand
    Dim MaxScore As UInteger = SQL.ExecuteScalar("SELECT MAX(Score) FROM Songs")
    Return MaxScore * rand
End Function

Запустите это и выберите запись с наибольшим количеством баллов меньше, чем возвращаемый вес. Если этот результат набрал более одной записи, выберите его наугад. Преимущества здесь в том, что вам не нужно поддерживать какие-либо суммы, и вы можете настроить уравнение вероятности, которое будет соответствовать вашим вкусам. Но опять же, это лучше всего работает при большем распределении баллов.

Answer 4

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

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

Answer 5

Если вам нужно получить группу сэмплов (скажем, вы хотите сэмплировать 50 строк из набора из 5 млн. Строк), где у каждой строки есть столбец с именем Weight, который равен int и где большие значения означают больше веса, вы можете использовать эту функцию:

SELECT * 
FROM 
(
    SELECT TOP 50 RowData, Weight 
    FROM MyTable 
    ORDER BY POWER(RAND(CAST(NEWID() AS VARBINARY)), (1.0/Weight)) DESC
) X 
ORDER BY Weight DESC

Ключ здесь использует функцию POWER (), как показано здесь

Ссылка на выбор случайной функции: здесь и здесь

В качестве альтернативы вы можете использовать:

1.0 * ABS(CAST(CHECKSUM(NEWID()) AS bigint)) / CAST(0x7FFFFFFF AS INT) 

Вы разыгрываете контрольную сумму как BIGINT вместо INT из-за этой проблемы:

Поскольку контрольная сумма возвращает int, а диапазон int равен -2 ^ 31 (-2,147,483,648) до 2 ^ 31-1 (2,147,483,647), функция abs () может вернуть ошибку переполнения, если результат окажется точным -2147483648! Шансы, очевидно, очень низкие, около 1 на 4 миллиарда, однако мы каждый день запускали их по таблице строк ~ 1,8 млрд, так происходило примерно раз в неделю! Исправление - привести контрольную сумму к бигинт перед прессом.