algorithm - 纸牌游戏快速匹配的数据结构

Question

播放时trading card games , 我经常想知道什么是处理以下问题最有效的数据结构。

在这样的游戏中，我面对的对手有一副包含 N 张牌(N ~ 30..60..100)的牌，每张牌都是从可能的 M 牌类型(M ~ 通常为 1000..10000s)中选出的.卡片一般不要求是唯一的，即可以有重复的卡片类型。对手牌组的内容在比赛前是未知的。

随着游戏的开始和进行，我慢慢地逐张学习对手使用的牌。有一个数据集包含 K(K ~ 通常为 100000..100000s)之前看到的牌组的全部内容。我想使用我在某个游戏中获得的逐渐增加的样本来查询此数据集，以制作对手可能使用的牌组的排名列表。

鉴于提到的合理现代硬件的限制(即几千兆字节的可用 RAM)，执行此类查询的最有效数据结构是什么？

一个非常小的例子

• 可能的卡片类型 = [1..10]

• 已知的 K 套牌:

  d1 = [1, 4, 6, 3, 4]
  d2 = [5, 3, 3, 9, 5]
  d3 = [5, 10, 4, 10, 1]
  d4 = [3, 7, 1, 8, 5]
  

• 在第 1 回合，我发现对手使用卡牌 #5；因此，我的候选人名单缩减为:

  d2 = [5, 3, 3, 9, 5] - score 2
  d3 = [5, 10, 4, 10, 1] - score 1
  d4 = [3, 7, 1, 8, 5] - score 1
  

  d2 在结果中排​​名高于其他，因为该副牌中有双 5，所以它很可能是

• 在第 2 回合，我揭示对手使用卡牌 #1；候选人名单缩减为:

  d3 = [5, 10, 4, 10, 1]
  d4 = [3, 7, 1, 8, 5]
  

我的解决方案

当然，简单的解决方案是将 K 副牌存储为 N 个整数的数组。因此，为一副牌显示的 p 张牌的给定查询获得匹配分数需要 O(N*p) 次检查。每次我们看到一场比赛时，我们只是将分数增加 1。因此，根据 p 张牌的查询检查所有 K 已知牌组将花费 O(K Np)，在最坏的情况下大约需要 100000 * 100 * 100 次操作 => 1e9，工作量很大。

我们可以设置一个索引，该索引将保存一个指针列表，该列表指向针对每种已知卡片类型遇到该卡片的牌组——但是，它并不能解决所有这些列表相交的问题(而且它们将是巨大的，可能在 90..95% 的已知套牌中都可以找到卡片)。对于给定的 p 卡查找，它归结为相交 p 个 K 牌组指针列表，计算过程中的相交分数。粗略地说，这是 O(Kp)，但常数相当大。后期还是1e7操作。

但是，如果我们使用这样一个事实，即实际上每个下一个回合都会进一步限制我们的数据集，我们可以将过滤重新应用于上一个查询中出现的任何内容。这样一来，每轮都是 O(K) => 1e5 次操作。

有没有一种方法可以在不依赖于 K 值的情况下实现更好的理想表现？

Answer 1

您可以做两件事来加快速度。首先，创建一个倒排索引，告诉您哪些牌组包含每张牌。所以在你上面的例子中:

d1 = [1, 4, 6, 3, 4]
d2 = [5, 3, 3, 9, 5]
d3 = [5, 10, 4, 10, 1]
d4 = [3, 7, 1, 8, 5]

您的索引是:

1: d1, d3, d4
3: d1, d2, d4
4: d1(2), d3
5: d2(2), d3, d4
6: d1
7: d4
8: d4
9: d2
10: d3(2)

应该清楚的是，这与套牌本身占用的内存量大致相同。也就是说，您没有 N 副 K 牌，而是最多 M 牌，每张牌最多有 N 副牌引用。

当用户翻开第一张牌 5 时，您会在索引中快速查找 5 并获得候选列表 [d2,d3,d4]。

这是第二个优化:您保留候选人名单。您不再对其余的套牌感兴趣；他们已从候选人名单中删除。当翻开下一张牌 1 时，您在索引中查找 1 并得到 [d1,d3,d4]。您将其与第一个候选人列表相交以生成 [d3,d4]。

在最坏的情况下，您最终会进行 N 次交集(每张牌一次)，每次交集 K 项(如果牌组都非常相似)。但在大多数情况下，一张牌所在的牌组数量会比 K 小得多，因此您的候选列表长度可能会很快缩小。

最后，如果您将牌组引用存储为 HashMap ，那么交集会非常快，因为您只需要从(通常很小的)现有候选列表中寻找下一张翻牌的大项目列表中的项目。这些查找是 O(1)。

这是搜索引擎工作原理的基本思想。您有一个单词列表，每个单词都包含对出现该单词的文档的引用。您可以很快地将文档列表从数亿缩小到少数。