0

バックグラウンド：

1対1の対戦のトーナメントを実行できるデータベースを作成したいと思います。各対戦の勝ち負けとその対戦に関するコメントを追跡し、次のユニークな対戦をランダムに決定する必要があります。

ルール：

x人のプレイヤーがいます。各プレーヤーは、最終的には他のすべてのプレーヤーを1回プレイし、事実上、プレーヤーのすべての可能な固有の組み合わせをカバーします。

データベーステーブル（サンプルデータ付き）：

DECLARE @Players TABLE (
    ID INT PRIMARY KEY IDENTITY,
    Name VARCHAR(50)
)

ID Name  
-- ----- 
1  Alex  
2  Bob   
3  Chris 
4  Dave 

DECLARE @Matches TABLE (
    ID INT PRIMARY KEY IDENTITY,
    WinnerId INT,
    LoserId INT
)

ID WinnerId LoserId 
-- -------- ------- 
1  1        2       
2  4        2       
3  3        1    

DECLARE @Comments TABLE (
    ID INT PRIMARY KEY IDENTITY,
    MatchId INT,
    Comment VARCHAR(MAX)
)

ID MatchId Comment                        
-- ------- ------------------------------ 
1  2       That was a close one.          
2  3       I did not expect that outcome.

問題：

  • まだ発生していない単一のランダムな一致を取得するために効率的にクエリを実行するにはどうすればよいですか？

主な問題は、プレーヤーの数が時間の経過とともに増加する可能性があり、増加することです。現在、私の例のデータでは、4人のプレーヤーしかいないため、6つの可能な一致が残ります。

Alex,Bob
Alex,Chris
Alex,Dave
Bob,Chris
Bob,Dave
Chris,Dave

これは、プレーヤーのIDに対応する2つの乱数を取得し続け、そのマッチアップがすでに発生しているかどうかをマッチアップテーブルで確認するのに十分な小ささです。ある場合：さらに2つ取得し、プロセスを繰り返します。まだ使用していない場合は、次の対戦として使用します。ただし、10,000人のプレーヤーがいる場合、49995000の可能な対戦になり、単純に遅くなります。

より効率的なクエリのために、誰かが私を正しい方向に向けることができますか？データベース設計の変更も、それが物事をより効率的にするのに役立つのであれば、私はオープンです。

4

4 に答える 4

1

考えられるすべての組み合わせと再生されたものとの間に外部結合を作成し、再生されたものを除外すると、まだ再生されていない組み合わせが残ります。ランダムなものを選択することは、順序付けの簡単なケースです。

SELECT p1.Name, p2.Name FROM
  Players p1
  JOIN Players p2 ON (
    p1.ID < p2.ID
  )
  LEFT JOIN Matches ON (
       (WinnerId = p1.ID AND LoserId = p2.ID)
    OR (WinnerId = p2.ID AND LoserId = p1.ID)
  )
WHERE Matches.ID IS NULL
ORDER BY RAND()
LIMIT 1;

編集

以下のypercubeで指摘されているように、上記のLIMIT構文は MySQL 固有です。代わりに、SQL 実装に適した構文を使用する必要がある場合があります。それが何であるかをお知らせください。必要に応じて誰かがアドバイスできます。TOPMicrosoft SQL Server ではと Oracleを使用していることは知っていますROWNUMが、それ以外の場合は、あなたのグーグルはおそらく私のものと同じくらい優れています。:)

于 2012-04-22T21:46:20.983 に答える
0

あなたの問題では、A）プレーヤーのすべての2要素サブセットをB）ランダム化された順序で検討する必要があります。

Aの場合、他の回答は、さまざまな条件でSQL結合を使用することを提案しています。10,000人のプレーヤーを実際に処理する必要がある場合、データベースをあまり使用しないソリューションは、効率的な組み合わせ生成アルゴリズムを使用することです。TAOCPvol。からいくつかをリストした以前の回答を見つけました。4ここ。2要素のサブセットの場合、辞書式順序でプレーヤーIDを介した単純な二重ネストループで問題ありません。

for player_a in 1..num_players:
  for player_b in player_a+1..num_players:
    handle a vs. b

1..nパートBでは、プレーヤーを整数のシャッフルにマッピングする2番目のテーブルを使用できます1..n。トーナメントプロセスが完了するまで、このシャッフルされたマッピングを保持します。Knuth-Fisher-Yatesシャッフルを使用できます。

この問題のインスタンスのどこにいるかを追跡するために、コンビネーションジェネレーターの状態をデータベースに定期的に保存することをお勧めします。これは、元のテーブルだけからシーケンスのどこにいるかを把握するよりもおそらく速いでしょう。

おっしゃるように、この方法で10,000人のプレーヤーを対戦で処理すると、約5,000万人の対戦が処理されます。すべてのプレーヤーが互いに競争する必要がないトーナメント構造を検討するかもしれません。たとえば、AがBを打ち、BがCを打ち負かす場合、AがCを打ち負かすかどうかを考慮する必要がない場合があります。シナリオに該当する場合、この種のショートカットを使用すると時間を大幅に節約できます。

于 2012-04-22T22:29:01.713 に答える
0

データ セットは大きいですが、キーを使用するlimitと、1 つのキーが返されるとすぐに追加の処理が停止します。1 つの可能性として、次の一致を返すために以下のようなクエリを使用することがあります。

SELECT * FROM Players p1, Players p2 WHERE p1.ID <> p2.ID AND (p1.ID, p2.ID) NOT IN (Select WinnerID, LoserID FROM Matches) AND (p2.ID, p1.ID) NOT IN (Select WinnerID, LoserID FROM Matches) LIMIT 1
于 2012-04-22T21:45:15.947 に答える
0

なぜ無作為に 2 人のプレイヤーを選ぶ必要があるのか​​疑問に思っています。可能性のある一致のリスト全体を前もって生成してから、WinnerId 列を追加するのはどうですか? 次の試合では、WinnerId が設定されていない最初の行を選択します。

于 2012-04-22T21:50:07.193 に答える