匹配集的数据结构
我有一个应用程序，我有许多集。 一套可能是
{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函数的数据结构。 这些集代表已经计算的一般解决方案，数据项是函数的新输入。 通过将数据项与一般解决方案相匹配，我可以避免大量处理。
我看到另一个对你来说是双重的解决方案（即，针对每个集合测试数据项），并且使用二叉树，其中每个节点测试是否包含特定项目。
例如，如果您有集合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 . BBCBAAAA CBCB C 在制作树之后，您只需要进行50次比较—或者您可以在一组中进行多少项目。
例如，对于{1,4}，你通过树分支：右（集合有1），左（没有2），左，右，你得到[B]，意味着只包括集合B.在{1,4}。
这基本上称为“二元决策图”。 如果你被节点中的冗余所冒犯（因为你应该这样，因为2 ^ 50是很多节点……）那么你应该考虑简化forms，这称为“简化的有序二进制决策图”和是一种常用的数据结构。 在此版本中，节点在冗余时合并，并且您不再具有二叉树，而是具有有向非循环图。
ROBBD上的Wikipedia页面可以为您提供更多信息，以及指向实现各种语言数据结构的库的链接。
我无法certificate这一点，但我相当确定没有可以轻易击败O（n）界限的解决方案。 你的问题是“太笼统”：每个集合都有m = 50个属性（即属性k是它包含数字k），并且要点是所有这些属性彼此独立 。 没有任何聪明的属性组合可以预测其他属性的存在。 排序不起作用，因为问题是非常对称的，50个数字的任何排列都会产生同样的问题，但搞砸了任何类型的排序。 除非你的输入有一个隐藏的结构 ，否则你运气不好。
但是，存在一些速度/内存权衡的空间。 也就是说，您可以预先计算小查询的答案 。 设Q是一个查询集，而supersets(Q)是包含Q的集合的集合，即问题的解决方案。 然后，您的问题具有以下关键属性
Q ⊆ P => supersets(Q) ⊇ supersets(P)
换句话说， P = {1,3,4}的结果是Q = {1,3}的结果的子集合。
现在，预先计算小查询的所有答案。 为了演示，我们将采用大小<= 3的所有查询。您将得到一张表
supersets({1}) supersets({2}) ... supersets({50}) supersets({1,2}) supersets({2,3}) ... supersets({1,2,3}) supersets({1,2,4}) ... supersets({48,49,50})
用O（m ^ 3）个条目。 要计算，例如， supersets({1,2,3,4}) ，您需要查找superset({1,2,3})并在此集合上运行线性算法。 关键在于，平均而言， superset({1,2,3})将不包含完整的n = 50,000个元素，但只有一小部分n / 2 ^ 3 = 6250 ，这使得速度提高了8倍。
（这是其他答案建议的“反向索引”方法的概括。）
但是，根据您的数据集，内存使用会相当糟糕。 但是你可以通过注意像{1,2,3,4}类的查询可以从几个不同的预先计算的答案中计算出来来省略某些行或加速算法，例如supersets({1,2,3})和supersets({1,2,4}) ，你将使用其中最小的一个。
如果你要提高性能，你将不得不做一些花哨的事情来减少你所做的集合比较。
也许您可以对数据项进行分区，以便您拥有1是一个组中最小元素的所有那些，以及其中2是另一个组中最小项的所有那些，依此类推。
在搜索时，您会在搜索集中找到最小值，并查看该值所在的组。
或者，也许，通过’此数据项包含N’对于N = 1..50将它们分组为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：{1,4}
2：{1,5}
3：{2}
4：{1,2,3,4,5}
5：{}
6：{2,5}
...
因此，对于任何特定集合{x_0，x_1，…，x_i}，您需要交叉x_0，x_1和其他集合。 例如，对于集合{2,3,4}，您需要将{1,5}与{2}和{1,2,3,4,5}相交。 因为您可以对倒排索引中的所有集合进行排序，所以可以将要交叉的集合的长度与最小集合相交。
如果您有非常“受欢迎”的项目（在我们的示例中为4）并且具有巨大的索引集，那么这可能是一个问题。
关于交叉的一些话。 您可以在倒排索引中使用排序列表，并成对交叉集合（以递增的长度顺序）。 或者，由于您的项目不超过50K，您可以使用压缩位集（每个数字约为6Kb，稀疏位集较少，约50个数字，不那么贪婪），并且按位设置相交位。 对于有效的稀疏位集，我认为。
分割位图列表的一种可能方法是创建一个（Compiled Nibble Indicators）数组
假设您的64位位图之一的位设置为0到8位。
在hex中，我们可以将其视为0x000000000000001F
现在，让我们将其转换为更简单和更小的表示。 每个4位半字节，或者至少有一个位设置或不设置。 如果是，我们将其表示为1，如果不是，我们将其表示为0。
因此hex值减少到位模式0000000000000011，因为右手2个半字节具有唯一具有位的位。 创建一个包含65536个值的数组，并将它们用作链接列表的头部或一组大型数组….
将每个位图编译成紧凑的CNI 。 将其添加到正确的列表中，直到编译完所有列表。
然后拿针。 将其编译为CNI格式。 使用它来值，下标到列表的头部。 该列表中的所有位图都有可能成为匹配项。 其他列表中的所有位图都无法匹配。
这是一种分裂它们的方法。
现在在实践中，我怀疑链表是否符合您的性能要求。
如果编写一个函数来将位图编译为CNI ，则可以使用它作为CNI对数组进行排序的基础。 然后让你的数组为65536个头，只需下标到原始数组作为范围的开始。
另一种技术是只编译64位位图的一部分，因此你的头数较少。 分析您的模式应该可以让您了解哪些半字节最有效的分区。
祝你好运，请告诉我们你最终会做什么。
邪恶。
与搜索标准匹配的集合的索引类似于集合本身。 我们没有使用小于50的唯一索引，而是使用小于50000的唯一索引。由于您不介意使用一些内存，因此可以预先计算5000位整数的50个元素中的匹配集。 然后你索引到预先计算的匹配，基本上只做你的（（设置和数据）==设置）但是在代表匹配集的50000位数上。 这就是我的意思。
#include enum { max_sets = 50000, // should be >= 64 num_boxes = max_sets / 64 + 1, max_entry = 50 }; uint64_t sets_containing[max_entry][num_boxes]; #define _(x) (uint64_t(1) << x) uint64_t sets[] = { _(1) | _(2) | _(4) | _(7) | _(8) | _(12) | _(18) | _(23) | _(29), _(3) | _(4) | _(6) | _(7) | _(15) | _(23) | _(34) | _(38), _(4) | _(7) | _(12) | _(18), _(1) | _(4) | _(7) | _(12) | _(13) | _(14) | _(15) | _(16) | _(17) | _(18), _(2) | _(4) | _(6) | _(7) | _(13) | _(15), 0, }; void big_and_equals(uint64_t lhs[num_boxes], uint64_t rhs[num_boxes]) { static int comparison_counter = 0; for (int i = 0; i < num_boxes; ++i, ++comparison_counter) { lhs[i] &= rhs[i]; } std::cout << "performed " << comparison_counter << " comparisons" << std::endl; } int main() { // Precompute matches memset(sets_containing, 0, sizeof(uint64_t) * max_entry * num_boxes); int set_number = 0; for (uint64_t* p = &sets[0]; *p; ++p, ++set_number) { int entry = 0; for (uint64_t set = *p; set; set >>= 1, ++entry) { if (set & 1) { std::cout << "sets_containing[" << entry << "][" << (set_number / 64) << "] gets bit " << set_number % 64 << std::endl; uint64_t& flag_location = sets_containing[entry][set_number / 64]; flag_location |= _(set_number % 64); } } } // Perform search for a key int key[] = {4, 7, 12, 18}; uint64_t answer[num_boxes]; memset(answer, 0xff, sizeof(uint64_t) * num_boxes); for (int i = 0; i < sizeof(key) / sizeof(key[0]); ++i) { big_and_equals(answer, sets_containing[key[i]]); } // Display the matches for (int set_number = 0; set_number < max_sets; ++set_number) { if (answer[set_number / 64] & _(set_number % 64)) { std::cout << "set " << set_number << " matches" << std::endl; } } return 0; }
运行此程序产生：
sets_containing[1][0] gets bit 0 sets_containing[2][0] gets bit 0 sets_containing[4][0] gets bit 0 sets_containing[7][0] gets bit 0 sets_containing[8][0] gets bit 0 sets_containing[12][0] gets bit 0 sets_containing[18][0] gets bit 0 sets_containing[23][0] gets bit 0 sets_containing[29][0] gets bit 0 sets_containing[3][0] gets bit 1 sets_containing[4][0] gets bit 1 sets_containing[6][0] gets bit 1 sets_containing[7][0] gets bit 1 sets_containing[15][0] gets bit 1 sets_containing[23][0] gets bit 1 sets_containing[34][0] gets bit 1 sets_containing[38][0] gets bit 1 sets_containing[4][0] gets bit 2 sets_containing[7][0] gets bit 2 sets_containing[12][0] gets bit 2 sets_containing[18][0] gets bit 2 sets_containing[1][0] gets bit 3 sets_containing[4][0] gets bit 3 sets_containing[7][0] gets bit 3 sets_containing[12][0] gets bit 3 sets_containing[13][0] gets bit 3 sets_containing[14][0] gets bit 3 sets_containing[15][0] gets bit 3 sets_containing[16][0] gets bit 3 sets_containing[17][0] gets bit 3 sets_containing[18][0] gets bit 3 sets_containing[2][0] gets bit 4 sets_containing[4][0] gets bit 4 sets_containing[6][0] gets bit 4 sets_containing[7][0] gets bit 4 sets_containing[13][0] gets bit 4 sets_containing[15][0] gets bit 4 performed 782 comparisons performed 1564 comparisons performed 2346 comparisons performed 3128 comparisons set 0 matches set 2 matches set 3 matches
3128 uint64_t比较胜过50000比较，所以你赢了。 即使在最糟糕的情况下，这将是一个包含所有50个项目的密钥，您只需要进行num_boxes * max_entry比较，在这种情况下为39100.仍然优于50000。
由于数字小于50，您可以使用64位整数构建一对一哈希，然后使用按位运算在O（1）时间内测试集合。 哈希创建也将是O（1）。 我认为要么是XOR，要么是测试零，要么是AND，然后进行相等性测试就行了。 （如果我正确理解了问题。）
将您的集合放入一个数组（不是链表）和SORT他们。 排序标准可以是1）集合中的元素数量（集合表示中的1位数），或2）集合中的最低元素。 例如，设A={7, 10, 16} ， B={11, 17} 。 然后在标准1）下BA
当新数据项到达时，您可以使用二进制搜索（对数时间）来查找数组中的起始候选集。 然后线性搜索数组并根据数组中的集合测试数据项，直到数据项变得“大于”集合。
您应该根据集合的范围选择排序标准。 如果所有集合都将0作为最低元素，则不应选择标准2）。 反之亦然，如果设定基数的分布不均匀，则不应选择标准1）。
另一个更健壮的排序标准是计算每组中元素的范围，并根据它进行排序。 例如，集合A中的最低元素是7，最高元素是16，因此您将其跨度编码为0x1007 ; 类似地，B的跨度将是0x110B 。 根据“跨度代码”对集合进行排序，然后再次使用二进制搜索来查找与数据项目具有相同“跨度代码”的所有集合。
计算“跨度代码”在普通C中运行缓慢，但如果你采用汇编可以快速完成 - 大多数CPU都有指令找到最多/最不重要的设置位。
这不是一个真正的答案更多的观察：这个问题看起来可以有效地并行化甚至分布，这至少会减少运行时间到O（n /核心数）
您可以构建包含每个元素的“haystack”列表的反向索引：
std::set needle; // {4, 7, 12, 18} std::vector> haystacks; // A list of your each of your data sets: // 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, std::hash_map[int, set > element_haystacks; // element_haystacks maps each integer to the sets that contain it // (the key is the integers from the haystacks sets, and // the set values are the index into the 'haystacks' vector): // 1 -> {1, 4} Element 1 is in sets 1 and 4. // 2 -> {1, 5} Element 2 is in sets 2 and 4. // 3 -> {2} Element 3 is in set 3. // 4 -> {1, 2, 3, 4, 5} Element 4 is in sets 1 through 5. std::set answer_sets; // The list of haystack sets that contain your set. for (set ::const_iterator it = needle.begin(); it != needle.end(); ++it) { const std::set &new_answer = element_haystacks[i]; std::set existing_answer; std::swap(existing_answer, answer_sets); // Remove all answers that don't occur in the new element list. std::set_intersection(existing_answer.begin(), existing_answer.end(), new_answer.begin(), new_answer.end(), inserter(answer_sets, answer_sets.begin())); if (answer_sets.empty()) break; // No matches :( } // answer_sets now lists the haystack_ids that include all your needle elements. for (int i = 0; i < answer_sets.size(); ++i) { cout << "set: " << element_haystacks[answer_sets[i]]; }
如果我没有弄错的话，这将具有O(k*m)的最大运行时间，其中是整数所属的集合的平均数量，m是针集的平均大小（<50）。 不幸的是，由于构建反向映射（ element_haystacks ），它会产生大量内存开销。
如果您存储已排序的vectors而不是sets并且element_haystacks可能是50元素vector而不是hash_map我相信您可以稍微改进一下。
我很惊讶没有人提到STL包含一种算法来处理这类事情。 因此，您应该使用包含 。 如其所描述的，对于O（M + N）的最差情况性能，它最多执行2 *（N + M）-1次比较。
因此：
bool isContained = includes( myVector.begin(), myVector.end(), another.begin(), another.end() );
如果你需要O（log N）时间，我将不得不屈服于其他响应者。
另一个想法是完全预先捕捉你的大象。
建立
创建一个64位X 50,000元素位数组。
分析搜索集，并在每行中设置相应的位。
将位图保存到磁盘，因此可以根据需要重新加载。
搜索
将元素位数组加载到内存中。
创建一个位图数组，1 X 50000.将所有值设置为1.这是搜索位数组
拿你的针，走过每个值。 将它用作元素位数组的下标。 取相应的位数组，然后将它转换为搜索数组。
针对每个匹配元素，对针中的所有值以及搜索位数组执行此操作将保持1。
重建
遍历搜索位数组，对于每个1，您可以使用元素位数组来重建原始值。
你有几个数据项？ 它们真的都是独特的吗？ 您可以缓存热门数据项，还是在运行之前使用存储桶/基数排序将重复项组合在一起？
这是一种索引方法：
1）将50比特字段分成例如10个5比特子字段。 如果你真的有50K套，那么3个17位的块可能更接近标记。
2）对于每个集合，选择一个子字段。 一个很好的选择是子场，其中该集合具有最多位设置，几乎任意地断开关系 – 例如使用最左边的这样的子场。
3）对于每个子字段中的每个可能的位模式，记下分配给该子字段并匹配该模式的集合列表，仅考虑子字段。
4）给定一个新的数据项，将其划分为5位块，并在每个查找表中查找每个数据项，以获得要测试的集合列表。 如果您的数据是完全随机的，则可以获得两倍或更多的加速因子，具体取决于每组中最密集的子字段中设置的位数。 如果攻击者可以为你编制随机数据，也许他们会发现几乎但不完全匹配集合的数据项，你根本不会做得很好。
可能存在利用集合中任何结构的余地，通过对位进行编号，使得集合在其最佳子字段中倾向于具有两个或更多位 – 例如，对位进行聚类分析，如果它们倾向于将它们视为相似的一起出现。 或者，如果您可以预测数据项中的模式，请在步骤（2）中更改集对子字段的分配，以减少预期的错误匹配数。
增加：需要多少个表来保证任何2位始终属于同一个表？ 如果你看一下http://en.wikipedia.org/wiki/Projective_plane中的组合定义，你会发现有一种方法可以从57个不同的57（= 1 + 7 + 49）位中提取7位的集合。方式使得对于任何两个位，至少一个集合包含它们。 可能不是很有用，但它仍然是一个答案。