c++ - 匹配集的数据结构

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))，我很乐意用一些内存来换取一些性能。有没有人对如何组织这个有更好的想法？

编辑:非常感谢所有的答案。看来我需要提供有关该问题的更多信息。我先得到集合，然后一个接一个地得到数据项。我需要检查数据项是否与其中一组匹配。
集合很可能是“ block 状的”，例如对于给定的问题 1、3 和 9 可能包含在 95% 的集合中；我可以在某种程度上提前预测到这一点(但不是很好)。

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

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 是很多节点......)，那么您应该考虑简化形式，它被称为“简化的有序二进制决策图”和是一种常用的数据结构。在这个版本中，节点在冗余时被合并，不再是二叉树，而是有向无环图。

Wikipedia page on ROBBDs可以为您提供更多信息，以及为各种语言实现此数据结构的库的链接。