dpm*_*min 7 algorithm computer-science data-structures
在玩交易卡游戏时,我经常想知道什么是最有效的数据结构来处理以下问题.
在这样的游戏中,我面对的是一个包含N张牌(N~30..60..100)的牌组的对手,每张牌都是从可能的M牌类型中选出的(M~通常是1000..10000s).卡通常不需要是唯一的,即可以有重复的卡类型.在比赛之前,对手牌组的内容是未知的.
随着游戏的开始和进展,我慢慢地逐卡学习,这是对手使用的牌.有一个数据集包括之前看到的甲板的K(K~通常为100000..100000s)的全部内容.我想使用在特定游戏中获得的逐渐增加的样本来查询该数据集,以制作对手使用的可能甲板的排序列表.
鉴于对合理现代硬件(即可用的几千兆字节RAM)的上述限制,进行此类查询的最有效数据结构是什么？
已知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.因此,检查所有K个已知甲板对p卡的查询将采用O(K N p),即最坏情况下大约100000*100*100次操作= > 1e9,这是很多工作.
我们可以设置一个索引,该索引将包含指向每个已知卡类型卡的卡片的指针列表 - 但是,它不能解决所有这些列表交叉的问题(并且它们将会很大,那里可能是在90..95%已知甲板中找到的卡片.对于给定的p卡查找,它归结为交叉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 副 K 张牌，而是最多 M 张牌，每张牌最多有 N 副牌参考。
当用户翻开第一张卡片 5 时，您可以快速在索引中查找 5 并获得候选列表[d2,d3,d4]。
这是第二个优化：保留候选者列表。你不再对剩下的套牌感兴趣；他们已从候选人名单中被删除。当下一张牌 1 亮出时，您在索引中查找 1 并得到[d1,d3,d4]。您将其与生成的第一个候选列表相交[d3,d4]。
在最坏的情况下，你最终会做 N 个交叉点（每张卡一个），每个 K 个项目（如果牌组都非常相似）。但在大多数情况下，一张牌所在的牌组数量将远小于 K，因此您的候选列表长度可能会很快缩小。
最后，如果您将牌组引用存储为哈希映射，那么交集会非常快，因为您只需从翻开的下一张卡片的大项目列表中的（通常很小）现有候选列表中查找项目。这些查找的时间复杂度为 O(1)。
这是搜索引擎工作原理的基本思想。您有一个单词列表，每个单词都包含对该单词出现的文档的引用。您可以非常快速地将文档列表从数亿个文档列表快速缩小到少数几个。