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

Ответ 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

Ответ 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

Ответ 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

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

Ответ 4

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

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