Zufällige gewichtete Auswahl in T-SQL

Question

Wie wählt man zufällig eine Tabellenzeile in T-SQL basierend auf einer angewendeten Gewichtung für alle Kandidatenreihen aus?

Zum Beispiel habe ich eine Reihe von Zeilen in einer Tabelle mit 50, 25 und 25 gewichtet (was zu 100 addiert, aber nicht muss), und ich möchte eine von ihnen zufällig mit einem statistischen Ergebnis auswählen entspricht dem jeweiligen Gewicht.

Answer 1

Danes Antwort beinhaltet ein Selbst-Joins in einer Weise, die ein quadratisches Gesetz einführt. (n*n/2) Zeilen nach dem Join, wo sich n Zeilen in der Tabelle befinden.

Was wäre mehr ideal ist in der Lage, nur einmal den Tisch zu analysieren.

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 

Die durch den Tisch gehen, @id zu jeder id Wert Bilanz, während gleichzeitig der Einstellung @weight Punkt Erniedrigen. Schließlich wird die @weight_point negativ werden. Dies bedeutet, dass der SUM aller vorhergehenden Gewichte größer als der zufällig gewählte Zielwert ist. Dies ist der Datensatz, den wir wollen, und von diesem Punkt an setzen wir @id auf sich selbst (ignorieren alle IDs in der Tabelle).

Dies läuft nur einmal durch die Tabelle, muss aber die gesamte Tabelle durchlaufen, auch wenn der gewählte Wert der erste Datensatz ist. Da die durchschnittliche Position ist halb durch die Tabelle (und weniger, wenn nach aufsteigendem Gewicht geordnet) könnte eine Schleife möglicherweise schneller sein ... (Vor allem, wenn die Gewichtungen in gemeinsamen Gruppen sind):

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

Sie müssen einfach die Gewichte aller Kandidatenzeilen summieren, dann einen zufälligen Punkt innerhalb dieser Summe auswählen und dann den Datensatz auswählen, der mit diesem ausgewählten Punkt koordiniert (jeder Datensatz trägt inkrementell eine akkumulierende Gewichtssumme mit sich).

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

Die „schrittweise ein eine accumlating [sic] Gewichtssumme tragen“ Teil ist teuer, wenn Sie viele Datensätze haben. Wenn Sie bereits eine breite Palette von Scores/Gewichten haben (dh der Bereich ist breit genug, dass die meisten Datensätze Gewichte sind einzigartig. 1-5 Sterne würden wahrscheinlich nicht schneiden), können Sie etwas tun, um einen Gewichtungswert auszuwählen . Ich verwende hier VB.Net zu demonstrieren, aber dies leicht in reiner Sql als auch getan werden könnte:

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 

Run diese, und wählen Sie die Aufzeichnung mit dem größten weniger punkten als das zurück Gewicht. Wenn mehr als ein Datensatz dieses Ergebnis teilt, wählen Sie es zufällig aus. Die Vorteile hier sind, dass Sie keine Summen pflegen müssen, und Sie können die Wahrscheinlichkeitsgleichung nach Ihrem Geschmack anpassen. Aber wiederum funktioniert es am besten mit einer größeren Verteilung der Partituren.

Answer 4

Der Weg, dies mit Zufallszahlengeneratoren zu tun, ist die Wahrscheinlichkeitsdichtefunktion zu integrieren. Mit einer Reihe von diskreten Werten können Sie die Präfixsumme (Summe aller Werte bis zu diesem Wert) berechnen und speichern. Damit wählen Sie den Wert des Minumum-Präfix Summe (Aggregat bis Datum) größer als die Zufallszahl.

In einer Datenbank müssen die nachfolgenden Werte nach einem Einfügen aktualisiert werden. Wenn die relative Häufigkeit von Aktualisierungen und die Größe des Datensatzes die Kosten für die Durchführung dieses Verbots nicht erhöhen, bedeutet dies, dass der geeignete Wert aus einer einzelnen s-Argable-Abfrage (Prädikat, die durch eine Indexnachfrage aufgelöst werden kann) erhalten werden kann .