Escolha aleatória ponderada em T-SQL

Question

Como você seleciona aleatoriamente uma linha de tabela no T-SQL com base em um peso aplicado para todas as linhas candidatas?

Por exemplo, tenho um conjunto de linhas em uma tabela com pesos de 50, 25 e 25 (que somam 100, mas não é necessário) e quero selecionar uma delas aleatoriamente com um resultado estatístico equivalente ao respectivo peso.

Answer 1

A resposta de Dane inclui uma autojunção de uma forma que introduz uma lei quadrática. (n*n/2) linhas após a junção, onde há n linhas na tabela.

O que seria mais ideal é poder analisar a tabela apenas uma vez.

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

Isso passará pela tabela, configurando @id para cada registro id valor e ao mesmo tempo diminuindo @weight apontar.Eventualmente, o @weight_point ficará negativo.Isto significa que o SUM de todos os pesos anteriores é maior que o valor alvo escolhido aleatoriamente.Este é o recorde que queremos, então a partir desse ponto estabelecemos @id para si mesmo (ignorando quaisquer IDs na tabela).

Isso percorre a tabela apenas uma vez, mas precisa percorrer toda a tabela, mesmo que o valor escolhido seja o primeiro registro.Como a posição média está na metade da tabela (e menos se ordenada por peso crescente), escrever um loop poderia ser mais rápido...(Especialmente se as ponderações estiverem em grupos comuns):

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

Você simplesmente precisa somar os pesos de todas as linhas candidatas, escolher um ponto aleatório dentro dessa soma e selecionar o registro que coordena com esse ponto escolhido (cada registro carrega incrementalmente uma soma de peso acumulada).

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

O "carregando incrementalmente uma soma de peso acumulada [sic]" parte é cara se você tiver muitos registros.Se você também já possui uma ampla variedade de pontuações/pesos (ou seja:o intervalo é amplo o suficiente para que a maioria dos pesos dos registros sejam únicos.1-5 estrelas provavelmente não seriam suficientes), você pode fazer algo assim para escolher um valor de peso.Estou usando VB.Net aqui para demonstrar, mas isso também poderia ser feito facilmente em Sql puro:

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

Execute isso e escolha o registro com a maior pontuação menor que o peso retornado.Se mais de um registro compartilhar essa pontuação, escolha-o aleatoriamente.As vantagens aqui são que você não precisa manter nenhuma soma e pode ajustar a equação de probabilidade usada de acordo com seu gosto.Mas, novamente, funciona melhor com uma distribuição maior de pontuações.

Answer 4

A maneira de fazer isso com geradores de números aleatórios é integrar a função de densidade de probabilidade.Com um conjunto de valores discretos você pode calcular a soma do prefixo (soma de todos os valores até este) e armazená-la.Com isso você seleciona o valor da soma mínima do prefixo (agregado até a data) maior que o número aleatório.

Em um banco de dados, os valores subsequentes após uma inserção devem ser atualizados.Se a frequência relativa de atualizações e o tamanho do conjunto de dados não tornarem o custo de fazer isso proibitivo, significa que o valor apropriado pode ser obtido a partir de uma única consulta s-argável (predicado que pode ser resolvido por uma pesquisa de índice). .

Answer 5

Se você precisar obter um grupo de amostras (digamos, você deseja amostrar 50 linhas de uma coleção de 5 milhões de linhas), onde cada linha possui uma coluna chamada Weight que é um int e onde valores maiores significam mais peso, você pode usar esta função:

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

A chave aqui é usar a função POWER( ) conforme ilustrado aqui

Uma referência sobre a escolha de uma função aleatória é aqui e aqui

Alternativamente, você pode usar:

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

Você lança soma de verificação como BIGINT em vez de INT por causa de esse emitir:

Como a soma de verificação retorna um INT e o intervalo de um INT é -2^31 (-2.147.483.648) a 2^31-1 (2.147.483.647), a função ABS () pode retornar um erro de transbordamento se o resultado for exatamente -2,147,483,648 !As chances são obviamente muito baixas, cerca de 1 em 4 bilhões, no entanto, estávamos executando a mesa de ~ 1,8b todos os dias, então estava acontecendo cerca de uma vez por semana!A correção é lançar a soma de verificação para Bigint antes do ABS.