mysql - 如何找到经常一起玩的玩家组

Question

我完全被算法困住了，我需要一些帮助。

我有一个视频游戏，我有很多 Tuple<MatchId,PlayerId> (约 1 亿)。所有这些元组都在 Mysql 数据库中，但如果需要可以导出到文本文件。

在这场比赛中，所有比赛都有 9 名球员。我想找到经常一起比赛的球员组，也就是说谁一起至少打了 10 场比赛，我想要这个比赛次数。

目前我的解决方案如下:我首先将这些元组分组为 Tuple<MatchId, Collection<PlayerId>>因此，该集合有 1 到 9 个玩家。

然后，对于subgroupSize 2 到 9 之间:对于列表的每一行，我生成了大小为 subgroupSize 的所有子组。 ( maximum=126 对于 subgroupSize=5 )。

然后我创建另一个列表 Tuple<MatchId, Subgroup> .然后我按子组对第二个列表进行分组，然后进行过滤并得到此 subgroupSize 的结果.

问题是，对于 subgroupSize =5，我将有我的第二个列表，它的大小是第一个列表的 126 倍，过滤前大约有 10 亿行...

所以，我想知道您是否有更好的解决方案可以提出:)

谢谢你们，祝你们有美好的一天!

Answer 1

这是一个可以在 MySQL 中实现的方法。这个想法是采用迭代方法。建立一个 2 人组合表，然后是 3 人组合等等。保留中间表并对其进行适当索引。

首先，创建一个至少参加过 10 场比赛的球员列表:

create table players1 as
    select t1.playerid
    from tuples t1
    group by t1.playerid
    having count(*) >= 10;

对于成对的玩家:

create table players2 as
    select t1.playerid as playerid1, t2.playerid as playerid2
    from players1 p1 join
         tuples t1
         on p1.playerid = t1.playerid join
         tuples t2
         on t1.matchid = t2.matchid and
            t1.playerid < t2.playerid join
         players1 p2
         on t2.playersid = p2.playersid
    group by t1.playerid, t2.playerid
    having count(*) >= 10;

这里的想法是 players1 表被用作 tuples 表的过滤器。

然后您可以对后续表格重复此过程。

老实说，我不确定这在 MySQL 中的效率如何。这在很大程度上取决于球员的数量以及参加过 10 场或更多比赛的球员的数量。