21

入力例：

SELECT*FROMテスト;
 id | パーセント   
---- + ----------
  1 | 50
  2 | 35   
  3 | 15   
（3行）

平均して50％の時間でid = 1の行、35％の時間行でid = 2、15％の時間行でid = 3のクエリをどのように記述しますか？

のようなものを試しましSELECT id FROM test ORDER BY p * random() DESC LIMIT 1たが、間違った結果になります。10,000回実行すると、次のような分布が得られますが、分布{1=6293, 2=3302, 3=405}はほぼ次のようになると予想しました{1=5000, 2=3500, 3=1500}。

何か案は？

4

6 に答える 6

24

これでうまくいくはずです：

WITH CTE AS (
    SELECT random() * (SELECT SUM(percent) FROM YOUR_TABLE) R
)
SELECT *
FROM (
    SELECT id, SUM(percent) OVER (ORDER BY id) S, R
    FROM YOUR_TABLE CROSS JOIN CTE
) Q
WHERE S >= R
ORDER BY id
LIMIT 1;

サブクエリQは次の結果を返します。

1  50
2  85
3  100

次に、範囲[0、100）で乱数を生成し、その数以上の最初の行を選択します（WHERE句）。WITH乱数が1回だけ計算されるように、共通テーブル式（）を使用します。

ところで、SELECT SUM(percent) FROM YOUR_TABLEは任意の重みを含めることができますpercent-厳密にパーセンテージである必要はありません（つまり、合計で100まで）。

[SQLフィドル]

于 2012-10-23T23:11:48.667 に答える
9

ORDER BY random（）^（1.0 / p）

EfraimidisとSpirakisによって記述されたアルゴリズムから。

于 2017-10-10T11:02:21.267 に答える
4

ブランコが受け入れた解決策は素晴らしいです（ありがとう！）。ただし、（私のテストによると）パフォーマンスが同じで、おそらく視覚化が容易な代替案を提供したいと思います。

要約しましょう。元の質問は、おそらく次のように一般化できます。

IDと相対的な重みのマップが与えられた場合、マップ内のランダムなIDを返すクエリを作成しますが、確率はその相対的な重みに比例します。

パーセントではなく、相対的な重みに重点が置かれていることに注意してください。ブランコが彼の答えで指摘しているように、相対的な重みを使用することは、パーセントを含むすべてに有効です。

ここで、一時テーブルに配置するいくつかのテストデータについて考えてみます。

CREATE TEMP TABLE test AS
SELECT * FROM (VALUES
    (1, 25),
    (2, 10),
    (3, 10),
    (4, 05)
) AS test(id, weight);

元の質問よりも複雑な例を使用していることに注意してください。これは、合計が100になると便利ではなく、同じ重み（20）が複数回使用されている（ID 2および3の場合）という点です。後で説明するように、これを考慮することが重要です。

最初に行う必要があるのは、重みを0から1までの確率に変換することです。これは、単純な正規化（weight / sum（weights））にすぎません。

WITH p AS ( -- probability
    SELECT *,
        weight::NUMERIC / sum(weight) OVER () AS probability
    FROM test
),
cp AS ( -- cumulative probability
    SELECT *,
        sum(p.probability) OVER (
            ORDER BY probability DESC
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
        ) AS cumprobability
    FROM p
)
SELECT
    cp.id,
    cp.weight,
    cp.probability,
    cp.cumprobability - cp.probability AS startprobability,
    cp.cumprobability AS endprobability
FROM cp
;

これにより、次の出力が得られます。

 id | weight | probability | startprobability | endprobability
----+--------+-------------+------------------+----------------
  1 |     25 |         0.5 |              0.0 |            0.5
  2 |     10 |         0.2 |              0.5 |            0.7
  3 |     10 |         0.2 |              0.7 |            0.9
  4 |      5 |         0.1 |              0.9 |            1.0

上記のクエリは確かに私たちのニーズに厳密に必要な以上の作業を行っていますが、この方法で相対確率を視覚化することは有用であり、idを選択する最後のステップは簡単です。

SELECT id FROM (queryabove)
WHERE random() BETWEEN startprobability AND endprobability;

それでは、クエリが期待される分布のデータを返していることを確認するテストと一緒にすべてをまとめましょう。を使用generate_series()して、乱数を100万回生成します。

WITH p AS ( -- probability
    SELECT *,
        weight::NUMERIC / sum(weight) OVER () AS probability
    FROM test
),
cp AS ( -- cumulative probability
    SELECT *,
        sum(p.probability) OVER (
            ORDER BY probability DESC
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
        ) AS cumprobability
    FROM p
),
fp AS ( -- final probability
    SELECT
        cp.id,
        cp.weight,
        cp.probability,
        cp.cumprobability - cp.probability AS startprobability,
        cp.cumprobability AS endprobability
    FROM cp
)
SELECT *
FROM fp
CROSS JOIN (SELECT random() FROM generate_series(1, 1000000)) AS random(val)
WHERE random.val BETWEEN fp.startprobability AND fp.endprobability
;

これにより、次のような出力が得られます。

 id | count  
----+--------
 1  | 499679 
 3  | 200652 
 2  | 199334 
 4  | 100335

ご覧のとおり、これは予想される分布を完全に追跡します。

パフォーマンス

上記のクエリは非常にパフォーマンスが高いです。私の平均的なマシンでも、PostgreSQLがWSL1インスタンスで実行されている場合（ホラー！）、実行は比較的高速です。

     count | time (ms)
-----------+----------
     1,000 |         7
    10,000 |        25
   100,000 |       210
 1,000,000 |      1950

テストデータを生成するための適応

ユニット/統合テストのテストデータを生成するときに、上記のクエリのバリエーションをよく使用します。アイデアは、現実を追跡する確率分布を近似するランダムデータを生成することです。

そのような状況では、開始分布と終了分布を1回計算し、その結果をテーブルに保存すると便利です。

CREATE TEMP TABLE test AS
WITH test(id, weight) AS (VALUES
    (1, 25),
    (2, 10),
    (3, 10),
    (4, 05)
),
p AS ( -- probability
    SELECT *, (weight::NUMERIC / sum(weight) OVER ()) AS probability
    FROM test
),
cp AS ( -- cumulative probability
    SELECT *,
        sum(p.probability) OVER (
            ORDER BY probability DESC
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
        ) cumprobability
    FROM p
)
SELECT
    cp.id,
    cp.weight,
    cp.probability,
    cp.cumprobability - cp.probability AS startprobability,
    cp.cumprobability AS endprobability
FROM cp
;

次に、これらの事前計算された確率を繰り返し使用できるため、パフォーマンスが向上し、使用が簡単になります。

ランダムなIDを取得したいときにいつでも呼び出すことができる関数ですべてをラップすることもできます。

CREATE OR REPLACE FUNCTION getrandomid(p_random FLOAT8 = random())
RETURNS INT AS
$$
    SELECT id
    FROM test
    WHERE p_random BETWEEN startprobability AND endprobability
    ;
$$
LANGUAGE SQL STABLE STRICT

ウィンドウ関数フレーム

上記の手法は、非標準のフレームでウィンドウ関数を使用していることに注意してくださいROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW。これは、一部の重みが繰り返される可能性があるという事実に対処するために必要です。そのため、最初に重みが繰り返されるテストデータを選択しました。

于 2020-05-23T08:39:09.203 に答える
2

提案されたクエリは機能しているようです。このSQLFiddleデモを参照してください。ただし、間違った分布が作成されます。下記参照。

PostgreSQLがサブクエリを最適化するのを防ぐために、VOLATILESQL関数でラップしました。PostgreSQLには、サブクエリが外部クエリのすべての行に対して1回実行されることを意図していることを知る方法がないため、強制的に揮発性にしない場合は、1回だけ実行されます。別の可能性（クエリプランナーが将来最適化する可能性があります）は、相関サブクエリのように見せることです。たとえば、次のように常にtrueのwhere句を使用するこのハックのように：http ：//sqlfiddle.com/# ！12 / 3039b / 9

推測では（更新して機能しなかった理由を説明する前に）、テスト方法に誤りがあったか、PostgreSQLが相関サブクエリではないことに気づいて実行している外部クエリのサブクエリとしてこれを使用していますこの例のように、一度だけ。。

更新：作成されたディストリビューションは、期待したものではありません。ここでの問題は、 ;の複数のサンプルを取得することによって分布を歪めていることです。単一のサンプルrandom()が必要です。

このクエリは正しい分布を生成します（SQLFiddle）：

WITH random_weight(rw) AS (SELECT random() * (SELECT sum(percent) FROM test))
 SELECT id
FROM (                   
  SELECT 
    id,
    sum(percent) OVER (ORDER BY id),
    coalesce(sum(prev_percent) OVER (ORDER BY id),0) FROM (
      SELECT 
        id,
        percent,
        lag(percent) OVER () AS prev_percent
      FROM test
    ) x
) weighted_ids(id, weight_upper, weight_lower)
CROSS JOIN random_weight
WHERE rw BETWEEN weight_lower AND weight_upper;

言うまでもなく、パフォーマンスはひどいものです。ネストされた2つのウィンドウセットを使用しています。私がしていることは：

  • （id、percent、previous_percent）を作成し、それを使用して、範囲ブラケットとして使用される2つの実行中の重みの合計を作成します。それから
  • ランダムな値を取得し、それを重みの範囲にスケーリングしてから、ターゲットブラケット内に重みを持つ値を選択します
于 2012-10-23T22:44:09.187 に答える
1

これがあなたが遊ぶための何かです：

select t1.id as id1
  , case when t2.id is null then 0 else t2.id end as id2
  , t1.percent as percent1
  , case when t2.percent is null then 0 else t2.percent end as percent2 
from "Test1" t1 
  left outer join "Test1" t2 on t1.id = t2.id + 1
where random() * 100 between t1.percent and 
  case when t2.percent is null then 0 else t2.percent end;

基本的に、between句を適用する2つの列があるように、左外部結合を実行します。

テーブルを正しい方法で注文した場合にのみ機能することに注意してください。

于 2012-10-23T22:52:09.503 に答える
1

Branko Dimitrijevicの回答に基づいて、私はこのクエリを作成しました。これは、階層型ウィンドウ関数を使用した合計を使用することで高速になる場合と高速でない場合がありpercentます（とは異なりますROLLUP）。

WITH random AS (SELECT random() AS random)
SELECT id FROM (
    SELECT id, percent,
    SUM(percent) OVER (ORDER BY id) AS rank,
    SUM(percent) OVER () * random AS roll
    FROM test CROSS JOIN random
) t WHERE roll <= rank LIMIT 1

順序が重要でない場合は、SUM(percent) OVER (ROWS UNBOUNDED PRECEDING) AS rank,最初にデータを並べ替える必要がないため、望ましい場合があります。

私はまた、Mechanic Weiの答え（この論文で説明されているように）を試しました。これはパフォーマンスの点で非常に有望であるように見えますが、いくつかのテストの後、分布はオフになっているようです。

SELECT id
FROM test
ORDER BY random() ^ (1.0/percent)
LIMIT 1
于 2018-08-31T02:40:19.147 に答える