数据结构在卡片游戏中快速匹配

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

在这样的比赛中，我面对一个拥有N张牌（N〜30..60..100）的牌组的对手，他们中的每一个都是从可能的M种牌（M〜1000〜10000）中选出的。 卡通常不要求是唯一的，即可以有重复的卡类型。 比赛前对手的套牌内容是未知的。

随着游戏的开始和进展，我慢慢地学习一张卡片，一张对手使用哪张卡片。 有一个数据集，其中包含K（K〜通常为100000..100000s）的全部内容。 我想用逐渐增加的样本来查询这个数据集，这个样本是我在某个游戏中获得的，以便制作一个对手使用的可能套牌的排名列表。

考虑到合理的现代硬件（即可用的几千兆字节RAM）的限制，做这种查询的最有效的数据结构是什么？

一个非常小的例子

d1 = [1, 4, 6, 3, 4]
d2 = [5, 3, 3, 9, 5]
d3 = [5, 10, 4, 10, 1]
d4 = [3, 7, 1, 8, 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

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

我的解决方案的想法

当然，微不足道的解决方案是将K个甲板存储为N个整数的数组。 对于一个卡组显示的p卡的查询获得匹配分数，因此需要O（N * p）检查。 每当我们看到一场比赛时，我们只是将分数提高1.因此，检查所有K个已知套牌与p卡片的查询将会花费O（KNp），即在最差情况下大约100000 * 100 * 100次操作=> 1e9 ，这是很多工作。

我们可以设置一个索引，该索引将持有一张指向卡片的指针列表，用于每种已知的卡片类型 - 但是，它不能解决所有这些列表相交的问题（并且它们将会非常庞大可能是在90..95％的已知套牌中找到的牌）。 对于给定的p卡查找，归结为K个卡组指针相交的p列表，计算过程中的交集分数。 粗略地说，这是O（Kp），但是具有相当大的常数。 它在后期仍然是1e7运营。

但是，如果我们将使用实际上每一个下一个回合都会进一步限制我们的数据集的事实，那么我们可以重新应用过滤到先前查询中出现的任何内容。 这样，它就是O（K）每一轮=> 1e5的操作。

有没有更好的表现方式，理想情况下，不取决于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: 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张卡组，而是有多达M张卡，每张卡最多有N张卡组参考。

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

这是第二次优化：你保留候选人名单。 你不再对其他的套牌感兴趣; 他们已经从候选人名单中被淘汰出局。 当显示下一张牌1时，您在索引中查找1，就会得到[d1,d3,d4] 。 你与候选人的第一个列表相交产生[d3,d4] 。

在最糟糕的情况下，你最终会做N个十字路口（每卡一个）K个项目（如果这些套牌都非常相似）。 但在大多数情况下，卡片所在的套牌数量将远小于K，因此您的候选名单长度可能会很快缩短。

最后，如果将存储库引用存储为散列映射，则交集非常快，因为您只需从大量项目列表中的（通常较小的）现有候选列表中查找下一张转存的项目的项目。 这些查找是O（1）。

这是搜索引擎工作原理的基本思路。 您有一个单词列表，每个单词都包含单词出现在其中的文档的引用。您可以快速将文档列表从数亿个缩小到仅有的少数几个。

你的想法与交叉p列表指针是好的，但你错过了一些优化。

按照一些标准对甲板进行排序（即甲板指数），并使用二进制搜索来通过列表前进（使用堆取最小甲板ID并将其提前以匹配或超过当前最大甲板ID）。 这样你可以更快地完成它们，特别是如果你在十字路口没有很多套牌的话。

同时存储前一个交点，以便下一步移动时只需要交叉2个列表（之前的结果和新卡）。

最后，你可以忽略太受欢迎的卡片，并在最终结果中检查它们。

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

上一篇: Data structure for quick match in a card game

下一篇: Record audio that is being played from device to headphone jack