T-SQL でのランダムな重み付き選択

Question

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

たとえば、テーブル内に 50、25、25 で重み付けされた行のセットがあり (合計すると 100 になりますが、そうする必要はありません)、それぞれの行と同等の統計結果を持つ行をランダムに 1 つ選択したいとします。重さ。

Answer 1

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

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

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

これはテーブルを通過し、設定されます @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
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

すべての候補行の重みを合計し、その合計内でランダムな点を選択し、その選択した点と一致するレコードを選択するだけです (各レコードには、累積された重みの合計が増分的に含まれます)。

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,6483,6483,6483,6483,6483,6483,6483,6483,647個のabs（）関数が返される可能性があります。 ！可能性は明らかに非常に低く、40億人に約1人ですが、毎日約1.8bの列のテーブルでそれを実行していたので、週に1回行われていました！修正は、腹筋の前にチェックサムをbigintにキャストすることです。