Elección aleatoria ponderada en T-SQL

Question

¿Cómo se selecciona al azar una fila de tabla en T-SQL en función de un peso aplicado para todas las filas candidatas?

Por ejemplo, tengo un conjunto de filas en una tabla ponderada en 50, 25 y 25 (que suma hasta 100 pero no es necesario), y quiero seleccionar una de ellas al azar con un resultado estadístico equivalente al peso respectivo.

Answer 1

La respuesta de Dane incluye una auto unión de una manera que introduce una ley cuadrada. (n*n/2) filas después de la unión donde hay n filas en la tabla.

Lo que sería más ideal es poder analizar la tabla una sola 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 

Esto pasará a través de la mesa, el establecimiento de @id al valor de cada registro id mientras que al mismo tiempo disminuyendo @weight punto. Eventualmente, el @weight_point será negativo. Esto significa que el SUM de todos los pesos anteriores es mayor que el valor objetivo elegido al azar. Este es el registro que queremos, así que a partir de ese momento establecemos @id en sí mismo (ignorando cualquier ID en la tabla).

Esto se ejecuta en la tabla solo una vez, pero tiene que ejecutarse en toda la tabla incluso si el valor elegido es el primer registro. Debido a que la posición promedio está a la mitad de la tabla (y menos si se ordena por peso ascendente) escribir un bucle podría ser más rápido ... (Especialmente si las ponderaciones están en grupos comunes):

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

Simplemente necesita sumar los pesos de todas las filas candidatas, luego elija un punto aleatorio dentro de esa suma, luego seleccione el registro que coordina con ese punto elegido (cada registro lleva incrementalmente una suma de peso acumulado con él).

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

El "incrementalmente llevando una accumlating un [sic] de peso suma" parte es caro si usted tiene una gran cantidad de registros. Si también tiene una amplia gama de puntajes/pesos (es decir: el rango es lo suficientemente amplio como para que la mayoría de los pesos de los registros sean únicos. 1-5 estrellas probablemente no lo cortarían), puede hacer algo como esto para elegir un valor de peso . Estoy usando VB.Net aquí para demostrar, pero esto podría ser fácilmente hecho en pura SQL así:

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 

Ejecutar este, y recoger el registro con la mayor puntuación inferior al peso devuelto. Si más de un registro comparte ese puntaje, selecciónelo al azar. Las ventajas aquí son que no tiene que mantener ninguna suma, y ​​puede modificar la ecuación de probabilidad utilizada para satisfacer sus gustos. Pero, de nuevo, funciona mejor con una mayor distribución de puntajes.

Answer 4

La forma de hacer esto con generadores de números aleatorios es integrar la función de densidad de probabilidad. Con un conjunto de valores discretos puede calcular la suma del prefijo (suma de todos los valores hasta este) y almacenarla. Con esto, selecciona el valor de suma de prefijo mínima (agregada hasta la fecha) mayor que el número aleatorio.

En una base de datos, los valores posteriores después de una inserción deben actualizarse. Si la frecuencia relativa de las actualizaciones y el tamaño del conjunto de datos no hace que el costo de hacerlo sea prohibitivo, significa que se puede obtener el valor apropiado a partir de una sola consulta s-argable (predicado que se puede resolver mediante una búsqueda de índice) .