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

Question

当我玩交易卡牌游戏时，我经常想知道处理以下问题的最有效数据结构是什么。

在这样的游戏中，我面对一个包含N张卡牌（N ~ 30..60..100）的牌组，其中每张卡牌从可能的M种卡牌类型（M ~ 通常为1000..10000种）中选择。卡牌通常不需要是唯一的，即可以有重复的卡牌类型。在游戏开始和进行过程中，我会逐渐了解对手使用的卡牌。有一个数据集，其中包括先前看到的K（K ~ 通常为100000..100000个）个完整牌组的内容。我想使用在某个游戏中获得的逐步增加的样本查询此数据集，以制作对手使用的可能牌组的排名列表。

鉴于现代硬件的限制（即可用几GB RAM），哪种数据结构是执行此类查询的最有效方法？

一个非常小的例子

• possible card types = [1..10]

• known K decks:

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

• on turn 1, I reveal that an opponent uses card #5; thus, my list of candidates is reduced to:

  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 is ranked higher than the rest in the results, because there are double 5s in that deck, so it's probably more likely that it is

• on turn 2, I reveal that an opponent uses card #1; list of candidates is reduced to:

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

我的解决方案想法

显然，一种微不足道的解决方案是将K个牌组存储为N个整数的数组。对于给定的一个牌组，查询p张卡牌的匹配分数需要进行O(N*p)次检查。每次我们看到一个匹配，就会将分数增加1。因此，对于一个查询p张卡牌的情况，检查所有K个已知牌组需要进行O(KNp)次操作，即在最坏情况下大约需要进行100000 * 100 * 100次操作 => 1e9，这是非常繁重的工作。

我们可以建立一个索引，对于每种已知的卡牌类型，它将保存指向出现该卡牌的牌组的指针列表——然而，这并不能解决交叉所有这些列表的问题（它们将会非常庞大，可能有90..95%的牌组中都有这种卡牌）。对于给定的p张卡牌查找，它归结为交叉p个K个牌组指针列表，并在过程中计算交集得分。大致上，这是O(Kp)，但具有相当大的常数。在后期仍然需要进行1e7次操作。

然而，如果我们利用每一轮实际上会进一步限制数据集的事实，我们可以重新应用过滤器到上一个查询中出现的任何内容。这样，每个回合只需要O(K)的操作，即1e5次操作。 有没有更好的方法来执行，理想情况下不依赖于K的值？

- dpm_min

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)

应该清楚的是，这需要与牌组本身相同数量的内存。也就是说，你有最多M张牌，每张牌都有高达N个牌组引用，而不是N组K张牌。

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

以下是第二个优化：保留候选人名单。你不再关心其他的牌组；它们已经从候选人名单中删除了。当下一张卡片1被揭示时，你在你的索引中查找1，并得到[d1、d3、d4]。然后将其与第一个候选人名单相交，以产生[d3、d4]。

在最坏的情况下，您将执行N次交集（每个卡片一个），每个交集有K个项目（如果牌组都非常相似）。但在大多数情况下，一张卡片出现的牌组数量将远小于K，因此候选人名单长度可能会很快缩小。

最后，如果您将牌组引用存储为哈希映射，则交集会非常快，因为您只需在下一张翻开的卡片的大项列表中查找来自（通常很小的）现有候选人名单的项目。这些查找是O（1）。

这是搜索引擎工作的基本思想。你有一个单词列表，每个单词都包含它出现在文档中的引用。您可以非常快速地将数亿个文档的列表缩小到仅有几篇。

- Jim Mischel

Answer 2

你的想法是使用交叉的指向牌堆指针的列表，这很好，但你错过了一些优化。

按某些标准（即牌堆索引）对牌堆进行排序，并使用二进制搜索来遍历列表（使用堆获取最小的牌堆ID并将其提升到匹配或超过当前最大的牌堆ID）。这样可以更快地遍历它们，特别是如果交集中没有太多的牌堆。

此外，存储先前的交集，以便下一步只需要对2个列表进行交集操作（先前的结果和新卡片）。

最后，你可以简单地忽略那些太流行的卡片，只需在最终结果中检查它们即可。

我建议你实施这样的解决方案并运行一些基准测试。 它将比O（K）更快。

- Sorin