Choix pondéré aléatoire dans T-SQL

Question

Comment sélectionner au hasard une ligne de tableau dans T-SQL en fonction d'un poids appliqué à toutes les lignes candidates ?

Par exemple, j'ai un ensemble de lignes dans un tableau pondérées à 50, 25 et 25 (ce qui fait 100 mais ce n'est pas obligatoire), et je souhaite en sélectionner une au hasard avec un résultat statistique équivalent au respectif. poids.

Answer 1

La réponse de Dane inclut une auto-jointure d'une manière qui introduit une loi carrée. (n*n/2) lignes après la jointure où il y a n lignes dans la table.

Ce qui serait idéal, c'est de pouvoir analyser la table une seule fois.

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

Cela passera par la table, en définissant @id à chaque enregistrement id valeur tout en décrémentant @weight indiquer.Finalement, le @weight_point deviendra négatif.Cela signifie que le SUM de tous les poids précédents est supérieur à la valeur cible choisie au hasard.C'est le record que nous voulons, donc à partir de ce moment-là, nous établissons @id à lui-même (en ignorant les identifiants de la table).

Cela parcourt la table une seule fois, mais doit parcourir la table entière même si la valeur choisie est le premier enregistrement.Parce que la position moyenne est à mi-chemin dans le tableau (et moins si elle est classée par poids croissant), l'écriture d'une boucle pourrait éventuellement être plus rapide...(Surtout si les pondérations sont dans des groupes communs) :

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

Vous devez simplement additionner les poids de toutes les lignes candidates, puis choisir un point aléatoire dans cette somme, puis sélectionner l'enregistrement qui se coordonne avec ce point choisi (chaque enregistrement transporte progressivement avec lui une somme de poids accumulée).

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

Le "portant progressivement une somme de poids accumulée" une partie coûte cher si vous avez beaucoup de disques.Si vous disposez déjà d’un large éventail de scores/pondérations (c’est-à-dire :la plage est suffisamment large pour que la plupart des poids des enregistrements soient uniques.1 à 5 étoiles ne suffiraient probablement pas), vous pouvez faire quelque chose comme ceci pour choisir une valeur de poids.J'utilise VB.Net ici pour démontrer, mais cela pourrait également être facilement fait en SQL pur :

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

Exécutez ceci et choisissez l'enregistrement avec le score le plus élevé inférieur au poids renvoyé.Si plusieurs enregistrements partagent ce score, choisissez-le au hasard.Les avantages ici sont que vous n'avez pas besoin de conserver de sommes et que vous pouvez modifier l'équation de probabilité utilisée en fonction de vos goûts.Mais encore une fois, cela fonctionne mieux avec une plus grande répartition des scores.

Answer 4

La façon d’y parvenir avec les générateurs de nombres aléatoires consiste à intégrer la fonction de densité de probabilité.Avec un ensemble de valeurs discrètes, vous pouvez calculer la somme des préfixes (somme de toutes les valeurs jusqu'à celle-ci) et la stocker.Avec cela, vous sélectionnez la valeur minimale de la somme des préfixes (agrégat à ce jour) supérieure au nombre aléatoire.

Sur une base de données, les valeurs suivantes après une insertion doivent être mises à jour.Si la fréquence relative des mises à jour et la taille de l'ensemble de données ne rendent pas le coût de cette opération prohibitif, cela signifie que la valeur appropriée peut être obtenue à partir d'une seule requête s-argable (prédicat qui peut être résolu par une recherche d'index). .

Answer 5

Si vous avez besoin d'obtenir un groupe d'échantillons (par exemple, vous souhaitez échantillonner 50 lignes à partir d'une collection de 5 millions de lignes), chaque ligne ayant une colonne appelée Weight qui est un int et là où des valeurs plus grandes signifient plus de poids, vous pouvez utiliser cette fonction :

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

La clé ici consiste à utiliser la fonction POWER( ) comme illustré ici

Une référence sur le choix d'une fonction aléatoire est ici et ici

Alternativement, vous pouvez utiliser :

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

Vous lancez la somme de contrôle comme BIGINT au lieu de INT à cause de ce problème:

Étant donné que la somme de contrôle renvoie un int et que la plage d'un int est -2 ^ 31 (-2,147,483 648) à 2 ^ 31-1 (2 147,483 647), la fonction ABS () peut renvoyer une erreur de débordement si le résultat est exactement -2,147,483,648 !Les chances sont évidemment très faibles, environ 1 sur 4 milliards, mais nous le faisions sur une table en rangée de 1,8 milliard de 1,8 milliard, donc cela se produisait une fois par semaine!Fix consiste à lancer la somme de contrôle à Bigint avant les abdos.