Scelta ponderata casuale in T-SQL

Question

Come si seleziona casualmente una riga della tabella in T-SQL in base a un peso applicato per tutte le righe candidate?

Ad esempio, ho una serie di righe in una tabella ponderata 50, 25 e 25 (la cui somma dà 100 ma non è necessario) e desidero selezionarne una in modo casuale con un risultato statistico equivalente al rispettivo peso.

Answer 1

La risposta di Dane include che un sé si unisce in un modo che introduce una legge quadrata. (n*n/2) righe dopo l'unione in cui sono presenti n righe nella tabella.

L'ideale sarebbe poter analizzare la tabella solo una volta.

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

Questo passerà attraverso il tavolo, l'impostazione @id a ciascun record id valore e allo stesso tempo decrementarlo @weight punto.Alla fine, il @weight_point andrà negativo.Ciò significa che il SUM di tutti i pesi precedenti è maggiore del valore target scelto casualmente.Questo è il record che vogliamo, quindi da quel momento in poi stabiliremo @id a se stesso (ignorando eventuali ID nella tabella).

Questo viene eseguito attraverso la tabella solo una volta, ma deve essere eseguito attraverso l'intera tabella anche se il valore scelto è il primo record.Poiché la posizione media è a metà della tabella (e meno se ordinata in base al peso crescente), scrivere un ciclo potrebbe essere più veloce...(Soprattutto se le ponderazioni sono in gruppi comuni):

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

Devi semplicemente sommare i pesi di tutte le righe candidate, quindi scegliere un punto casuale all'interno di quella somma, quindi selezionare il record che si coordina con quel punto scelto (ogni record porta con sé in modo incrementale una somma di peso accumulata).

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

IL "portando in modo incrementale una somma di peso [sic] accumulata" parte è costosa se hai molti record.Se inoltre disponi già di un'ampia gamma di punteggi/pesi (es:l'intervallo è sufficientemente ampio da rendere la maggior parte dei pesi dei record univoci.1-5 stelle probabilmente non basterebbero), puoi fare qualcosa del genere per scegliere un valore di peso.Sto usando VB.Net qui per dimostrare, ma questo potrebbe essere facilmente fatto anche in puro 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

Eseguilo e scegli il record con il punteggio più alto inferiore al peso restituito.Se più di un record condivide lo stesso punteggio, selezionalo a caso.I vantaggi qui sono che non devi mantenere alcuna somma e puoi modificare l'equazione della probabilità utilizzata per adattarla ai tuoi gusti.Ma ancora una volta, funziona meglio con una distribuzione più ampia di punteggi.

Answer 4

Il modo per farlo con i generatori di numeri casuali è integrare la funzione di densità di probabilità.Con un insieme di valori discreti è possibile calcolare la somma del prefisso (somma di tutti i valori fino a questo) e memorizzarla.Con questo si seleziona il valore minimo della somma del prefisso (aggregato fino ad oggi) maggiore del numero casuale.

In un database i valori successivi ad un inserimento devono essere aggiornati.Se la frequenza relativa degli aggiornamenti e la dimensione del set di dati non rendono proibitivo il costo di questa operazione, significa che il valore appropriato può essere ottenuto da una singola query s-argable (predicato che può essere risolto mediante una ricerca nell'indice) .

Answer 5

Se è necessario ottenere un gruppo di campioni (ad esempio, si desidera campionare 50 righe da una raccolta di 5 milioni di righe) in cui ciascuna riga ha una colonna chiamata Weight che è un int e dove valori più grandi significano più peso, puoi usare questa funzione:

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 chiave qui è usare la funzione POWER( ) come illustrato Qui

Un riferimento sulla scelta di una funzione casuale è Qui E Qui

In alternativa puoi utilizzare:

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

Hai lanciato il checksum come BIGINT invece di INT per colpa di Questo problema:

Poiché il checksum restituisce un INT e l'intervallo di un INT è -2^31 (-2.147.483.648) a 2^31-1 (2.147.483.647), la funzione ABS () può restituire un errore di overflow se il risultato sembra essere esattamente -2.147.483.648 !Le possibilità sono ovviamente molto basse, circa 1 su 4 miliardi, tuttavia lo stavamo eseguendo su una tavola di riga di ~ 1,8 miliardi ogni giorno, quindi stava accadendo circa una volta alla settimana!La correzione è quella di lanciare il checksum su Bigint prima degli addominali.