sql-server - T-SQL でのランダム加重選択

Question

すべての候補行に適用された重みに基づいて、T-SQL でテーブル行をランダムに選択するにはどうすればよいですか?

たとえば、表に 50、25、および 25 で重み付けされた一連の行があり (合計すると 100 になりますが、100 になる必要はありません)、それらの 1 つをランダムに選択して、それぞれに等しい統計的結果を得たいとします。重さ。

Answer 1

Dane の答えには、自乗則を導入する方法での自己結合が含まれます。(n*n/2)テーブルに n 行ある結合後の行。

より理想的なのは、テーブルを一度だけ解析できることです。

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

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

これはテーブルを通過し、@id各レコードのid値に設定され、同時に@weightポイントが減少します。最終的には@weight_pointマイナスになります。これは、SUM先行するすべての重みの が、ランダムに選択されたターゲット値よりも大きいことを意味します。これが必要なレコードなので、その時点から@idそれ自体に設定します (テーブル内の ID は無視します)。

これはテーブルを 1 回だけ実行しますが、選択した値が最初のレコードであっても、テーブル全体を実行する必要があります。平均位置はテーブルの途中にあるため (重みの昇順の場合はそれ以下)、ループを記述する方が高速になる可能性があります... (特に重みが共通のグループにある場合):

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 WHERE weight = @next_weight
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))

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

すべての候補行の重みを合計し、その合計内のランダムなポイントを選択し、その選択したポイントと調整するレコードを選択するだけです (各レコードは、累積された重みの合計を増分的に運びます)。

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

多くのレコードがある場合、「累積する[原文のまま]重みの合計を段階的に運ぶ」部分は高価です。すでに幅広いスコア/重みがある場合 (つまり、範囲が十分に広いため、ほとんどのレコードの重みは一意です。1 ～ 5 個の星ではおそらく十分ではないでしょう)、次のような方法で重みの値を選択できます。 . ここでは実演のために VB.Net を使用していますが、これは純粋な 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

これを実行し、返された重みよりも小さい最大スコアを持つレコードを選択します。複数のレコードがそのスコアを共有している場合は、ランダムに選択します。ここでの利点は、合計を維持する必要がなく、好みに合わせて使用​​する確率方程式を微調整できることです。しかし、繰り返しになりますが、スコアの分布が大きいほど最適に機能します。

Answer 4

乱数発生器でこれを行う方法は、確率密度関数を統合することです。離散値のセットを使用すると、接頭辞の合計 (この値までのすべての値の合計) を計算して保存できます。これにより、乱数よりも大きいプレフィックス合計 (現在までの集計) の最小値を選択します。

データベースでは、挿入後の後続の値を更新する必要があります。更新の相対的な頻度とデータセットのサイズがこれを行うコストを法外なものにしない場合、適切な値が単一の s-argable (インデックスルックアップによって解決できる述語) クエリから取得できることを意味します。 .

Answer 5

サンプルのグループを取得する必要がある場合 (たとえば、500 万行のコレクションから 50 行をサンプリングしたい場合)、各行には と呼ばれる列があり、Weight値intが大きいほど重みが大きいことを意味する場合は、次の関数を使用できます。

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

ここで重要なのは、ここに示すように POWER( ) 関数を使用することです

ランダム関数の選択に関するリファレンスは、こことここにあります

または、次を使用できます。

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

この問題のため、BIGINT代わりにチェックサムをキャストします。INT

チェックサムは int を返し、int の範囲は -2^31 (-2,147,483,648) から 2^31-1 (2,147,483,647) であるため、結果が正確に -2,147,483,648 になると、abs() 関数はオーバーフロー エラーを返す可能性があります。 ! その可能性は明らかに非常に低く、約 40 億分の 1 ですが、毎日 18 億行のテーブルで実行していたため、週に 1 回程度発生していました。修正は、abs の前にチェックサムを bigint にキャストすることです。