Случайный взвешенный выбор в 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, но это можно легко сделать и на чистом Sql:

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 (2147 483,647), функция ABS () может вернуть ошибку переполнения, если результат будет точно -2,147,483,648. !Шансы, очевидно, очень низкие, около 1 из 4 миллиардов, однако мы проводили его за столом ~ 1,8B ряд каждый день, так что это происходило примерно раз в неделю!Исправление заключается в приведении контрольной суммы к bigint перед прессом.