我有一个应用程序,其中有多个集合,一个集合可能是
{4, 7, 12, 18}
独特的数字,并且都小于50。
然后我有几个数据项:
1 {1, 2, 4, 7, 8, 12, 18, 23, 29}
2 {3, 4, 6, 7, 15, 23, 34, 38}
3 {4, 7, 12, 18}
4 {1, 4, 7, 12, 13, 14, 15, 16, 17, 18}
5 {2, 4, 6, 7, 13, 15}
数据项1、3和4与该集合匹配,因为它们包含集合中的所有项。
我需要设计一种数据结构,它可以很快地识别出数据项是集合的成员是否包含所有作为集合一部分的成员(因此数据项是集合的超集)。目前最好的估计是将少于50,000个集合。
我的当前实现方式使用64位无符号整数存储我的集合和数据,并将集合存储在列表中。然后,我通过迭代列表执行((set & data) == set)比较来检查数据项。它有效并且空间效率高,但是速度较慢(O(n)),我愿意为一些性能牺牲一些内存。有没有更好的想法如何组织它?
编辑:
非常感谢所有答案。看起来我需要提供有关问题的更多信息。我首先获取集合,然后逐个获取数据项。我需要检查数据项是否与其中一个集合匹配。
集合很可能是'稠密的',例如对于给定的问题1、3和9可能包含在95%的集合中;我可以事先某种程度上预测这一点(但不太准确)。
对于那些提出备忘录技术的人:这是备忘录函数的数据结构。集合代表已经计算过的通用解决方案,而数据项则是函数的新输入。通过将数据项与通用解决方案进行匹配,我可以避免大量的处理。