匹配集的数据结构

Question

我有一个应用程序,我有许多集.一组可能是
{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%的集合中; 我可以提前预测到这一点(但不是很好).

对于那些建议记忆的人:这就是memoized函数的数据结构.这些集代表已经计算过的一般解决方案,数据项是函数的新输入.通过将数据项与一般解决方案相匹配,我可以避免大量处理.

Answer 1

我看到另一个对你来说是双重的解决方案(即,针对每个集合测试数据项),并且使用二叉树,其中每个节点测试是否包含特定项目.

例如,如果您有集合A = {2,3}且B = {4}且C = {1,3},则您将拥有以下树

                      _NOT_HAVE_[1]___HAVE____
                      |                      |            
                _____[2]_____          _____[2]_____
                |           |          |           |
             __[3]__     __[3]__    __[3]__     __[3]__
             |     |     |     |    |     |     |     |
            [4]   [4]   [4]   [4]  [4]   [4]   [4]   [4]
            / \   / \   / \   / \  / \   / \   / \   / \
           .   B .   B .   B .   B    B C   B A   A A   A
                                            C     B C   B
                                                        C

在制作树之后,您只需进行50次比较 - 或者您可以在一组中进行多少项目.

例如,对于{1,4},你通过树分支:右(集合有1),左(没有2),左,右,你得到[B],意味着只包括集合B.在{1,4}.

这基本上称为"二元决策图".如果你被节点中的冗余所冒犯(因为你应该这样,因为2 ^ 50是很多节点......)那么你应该考虑简化形式,这称为"简化的有序二进制决策图"和是一种常用的数据结构.在此版本中,节点在冗余时合并,并且您不再具有二叉树,而是具有有向非循环图.

ROBBD上的Wikipedia页面可以为您提供更多信息,以及指向实现各种语言数据结构的库的链接.