当我玩交易卡牌游戏时,我经常想知道处理以下问题的最有效数据结构是什么。
在这样的游戏中,我面对一个包含N张卡牌(N ~ 30..60..100)的牌组,其中每张卡牌从可能的M种卡牌类型(M ~ 通常为1000..10000种)中选择。卡牌通常不需要是唯一的,即可以有重复的卡牌类型。在游戏开始和进行过程中,我会逐渐了解对手使用的卡牌。有一个数据集,其中包括先前看到的K(K ~ 通常为100000..100000个)个完整牌组的内容。我想使用在某个游戏中获得的逐步增加的样本查询此数据集,以制作对手使用的可能牌组的排名列表。
鉴于现代硬件的限制(即可用几GB RAM),哪种数据结构是执行此类查询的最有效方法?
一个非常小的例子
在这样的游戏中,我面对一个包含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的值?