6

随机选择两个集合，两个集合都包含不同的键（一个键可能属于多个集合，一个集合永远不能包含重复的键）。

返回一个整数，表示属于两个集合的键数。

例如 intersect({1,2,3,4},{3,4,5}) 返回 2 。

我只需要十字路口的大小。我不需要确切知道十字路口有哪些钥匙。

是否有任何数据结构在少于 O(n) 的时间内支持这种操作？

编辑：

读取数据确实需要 O(n) time，但这不会导致您不能在少于 O(n) time 的时间内执行交集操作的结论。

想象这个场景：

我有 N 套，每套包含 100 个钥匙。我读了它们，那是 N*100 操作。现在我想知道女巫对集合有最大的交集，即 O(N²) 交集操作。所以我想降低交集操作的复杂性。我真的不知道关心读取和构造集合需要多少时间，最多 N*100，这与 O(N²) 交集操作相比没什么。

请注意，您无法通过小于 O(N²) 的交集运算找到具有最大交集的集合对，我可以证明这一点。您必须执行所有的交集运算。

（他的基本思想是，让我们想象一个完整的图，有 N 个顶点，每个顶点代表一个集合，Nx(N-1)/2 个边，每个代表连接对的交点。现在给每个边一个非你想要的所有负重（代表交叉点大小），我总是可以构造 N 个集合满足那些 Nx(N-1)/2 边权重。这证明了我的主张。）

4

2 回答 2

11

我建议您看看两种可能的替代方案，它们在实践中效果特别好（尤其是在大集合的情况下）。

1.布隆过滤器数据结构

布隆过滤器是一种节省空间（基于位数组）的概率数据结构，用于测试元素是否是集合的成员。假阳性匹配是可能的，但假阴性是不可能的。

在误报率和布隆过滤器的内存占用之间存在权衡。因此，可以针对不同的用例估计合适的布隆过滤器大小。

每个集合都可以与它自己的布隆过滤器相关联。Bloom Filter 很容易得到，对应不同集合的交集：所有对应不同 Bloom Filter 的位数组都可以用按位AND运算组合起来。

拥有对应于交集的布隆过滤器，可以快速找到所有相交集中存在的项目。

除此之外，无需对整个集合进行实际迭代即可估计交集的基数： https ://en.wikipedia.org/wiki/Bloom_filter#The_union_and_intersection_of_sets

2.跳表数据结构

跳过列表是一种数据结构，它允许在有序的元素序列中进行快速搜索和交叉。通过维护子序列的链接层次结构，可以实现快速搜索和交叉，每个子序列跳过更少的元素。

简而言之，Skip List 与普通的 Linked List 数据结构非常相似，但是 Skip List 的每个节点都有几个指向项目的附加指针，这些指针位于更远的位置（指针，“跳过”其他几个节点名单）。

因此，为了获得交集 - 需要维护所有正在相交的跳过列表中的指针。在跳过列表相交期间，指针会跳过项目，这些项目并不存在于所有相交的跳过列表中。因此，通常相交运算的运行时复杂度比 快O(N)。

Skip Lists 的交集算法在《Introduction to Information Retrieval》一书中进行了描述（由 Christopher D. Manning、Prabhakar Raghavan、Hinrich Schütze 撰写）： http: //nlp.stanford.edu/IR-book/html/ htmledition/faster-postings-list-intersection-via-skip-pointers-1.html

跳过列表在高性能、功能齐全的文本搜索引擎库中被积极使用：Apache Lucene（在倒排索引组件中使用了跳过列表）。

这是关于在 Lucene 中使用跳过列表的另一个 Stackoverflow 问题：Lucene如何在倒排索引中使用跳过列表？

于 2016-08-26T23:50:01.730 回答
2

让我们假设有一种算法可以在更短的O(n)时间内检查交叉点的长度。现在让我们阅读部分输入。我们有两种选择：我们已经阅读了整套和另一套的一部分，或者我们已经阅读了第一套的一部分和另一套的一部分。

选项1）：

反例 - 让我们采用这样的输入，即存在一个在集合 1 中读取但尚未从集合 2 中读取但在集合 2 中的元素 - 我们将收到不正确的结果。

选项 2）：

反例 - 我们可以输入这样的存在元素，该元素存在于两组中，但至少有一组未被读取。我们收到不正确的结果。

好的，我们已经证明，当我们不读取整个输入时，没有这样的算法可以返回正确的结果。

让我们阅读整个输入 -n数字。糟糕，复杂度是O(n)。

证明结束。

于 2016-08-25T21:28:43.907 回答