0

背景：

我想创建一个可以运行 1 对 1 比赛的数据库。它需要跟踪每场比赛的获胜者和失败者以及有关该比赛的任何评论，并随机决定下一场独特的比赛。

规则：

有x个玩家。每个玩家最终将与其他玩家玩一次，实际上涵盖了所有可能的独特玩家组合。

数据库表（带有示例数据）：

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 实现使用适当的语法 - 让我们知道它是什么，如果需要，有人可以提供建议。我知道在 Microsoft SQL Server 中使用TOP和在 Oracle 中ROWNUM，但除此之外你的谷歌搜索可能和我的一样好。:)

于 2012-04-22T21:46:20.983 回答
0

虽然数据集很大，但是limit只要返回一个key，使用key就会停止额外的处理。一种可能性可能是使用如下查询来返回下一个匹配项。

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 回答
0

对于您的问题，您希望 A) 以随机顺序考虑玩家 B) 的所有 2 元素子集。

对于 A，其他答案建议使用具有各种条件的 SQL 连接。如果您确实需要处理 10,000 个玩家，那么数据库密集度较低的解决方案可能是使用有效的组合生成算法。我找到了一个先前的答案，列出了 TAOCP vol 中的一些内容。4这里。对于 2 元素子集的情况，按字典顺序对玩家 id 进行简单的双嵌套循环就可以了：

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

对于 B 部分，您可以使用第二个表将玩家映射1..n到整数的洗牌1..n。保持这个打乱的映射，直到你完成比赛过程。您可以使用Knuth-Fisher-Yates shuffle。

要跟踪您在此问题的实例中所处的位置，您可能希望定期将组合生成器的状态保存到数据库中。这可能比仅从原始表中找出您在序列中的位置要快。

正如您所提到的，以这种方式处理 10,000 名球员的比赛会导致近 5000 万场比赛需要处理。您可能会考虑一种不需要每个玩家与其他玩家竞争的锦标赛结构。例如，如果 A 击败 B 并且 B 击败 C，那么您可能不必考虑 A 是否击败 C。如果适用于您的场景，这种捷径可以节省大量时间。

于 2012-04-22T22:29:01.713 回答