T-SQL의 무작위 가중치 선택

Question

모든 후보 행에 적용된 가중치를 기반으로 T-SQL에서 테이블 행을 어떻게 무작위로 선택합니까?

예를 들어, 테이블에 50, 25, 25(최대 100이 되지만 꼭 그럴 필요는 없음) 가중치가 부여된 행 집합이 있고, 해당 행과 동일한 통계 결과를 사용하여 그 중 하나를 무작위로 선택하려고 합니다. 무게.

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), 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를 무시하고).

이는 테이블을 한 번만 실행하지만 선택한 값이 첫 번째 레코드인 경우에도 전체 테이블을 실행해야 합니다.평균 위치는 테이블의 절반(오름차순으로 정렬된 경우 더 적음)이므로 루프를 작성하는 것이 더 빠를 수 있습니다.(특히 가중치가 공통 그룹에 있는 경우):

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

각 행에 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)이므로 ABS () 함수는 결과가 정확히 -2,147,483,648 인 경우 오버플로 오류를 반환 할 수 있습니다. !기회는 분명히 약 1,400 억에서 약 1.8b 행 테이블 위로 실행하고 있었기 때문에 일주일에 한 번 약 1 주일이 걸렸습니다!수정은 ABS 전에 체크섬을 BigInt에 시전하는 것입니다.