sql server - transact - Elección aleatoria ponderada en T-SQL

transact sql server 2008

Question

¿Cómo se selecciona aleatoriamente 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 a las respectivas peso.

Answer 1

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) .

Answer 2

La parte de "llevar incrementalmente una suma de peso acumulada [sic]" es costosa si tiene muchos 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 también podría hacerse fácilmente en 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

Ejecute esto y elija el registro con la puntuación más alta menor que el 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 3

Si necesita obtener un grupo de muestras (por ejemplo, desea muestrear 50 filas de una colección de filas de 5M) donde cada fila tiene una columna llamada Weight que es un int y donde valores más grandes significan más peso, puede usar esto función:

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 clave aquí es usar la función POWER () como se ilustra here

Una referencia sobre la elección de una función aleatoria está here y here

Alternativamente puedes usar:

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

BIGINT suma de comprobación como BIGINT lugar de INT debido a this problema:

Debido a que la suma de comprobación devuelve un int, y el rango de un int es -2 ^ 31 (-2,147,483,648) a 2 ^ 31-1 (2,147,483,647), la función abs () puede devolver un error de desbordamiento si el resultado es exactamente -2,147,483,648 ! Las posibilidades son obviamente muy bajas, alrededor de 1 en 4 mil millones, sin embargo, lo estábamos ejecutando en una tabla de filas de ~ 1.8b todos los días, ¡así que sucedía una vez por semana! La solución es lanzar la suma de comprobación a bigint antes de los abdominales.

Answer 4

Simplemente debe sumar los pesos de todas las filas candidatas, luego elegir un punto aleatorio dentro de esa suma, luego seleccionar el registro que coordina con ese punto elegido (cada registro lleva incrementalmente una suma de peso acumulada 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 5

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 irá a través de la tabla, fijando @id al valor de @id de cada registro mientras que al mismo tiempo disminuye el punto de @weight . Eventualmente, el @weight_point volverá negativo. Esto significa que la 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 a 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