用于快速交叉操作的数据结构？
Data structures for fast intersection operations?
随机select两组，两组都包含不同的键（一个键可以属于多个组，一组不能包含重复的键）。
Return一个整数，表示属于两个集合的键数。
例如相交({1,2,3,4},{3,4,5}) returns 2 .
我只需要路口的大小。我不需要确切地知道路口有哪些键。
是否有任何数据结构在 少于 O(n) 时间 内支持这种操作？
编辑：
读出数据确实需要O(n)的时间，但是不会得出不能进行交集运算的结论少于 O(n) 时间 .
想像这个场景：
我有N套，每套100把钥匙。我读了一遍，那是 N*100 次操作。现在我想知道 对集合有最大的交集，那是 O(N²) 次交集操作。所以我想降低交集操作的复杂性。我真的不关心读取和构造集合需要多少时间，它最多是 N*100，这与 O(N²) 交集操作相比没什么。
请注意，您无法通过少于 O(N²) 次交集运算找到具有最大交集的集合对，我可以证明。您必须 做所有的交集操作。
（他的基本思想是，让我们想象一个完整的图，有 N 个顶点，每个顶点代表一个集合，和 Nx(N-1)/2 条边，每个代表连接对的交集。现在给出每条边都是你想要的非负权重（代表交集大小），我总是可以构造 N 组满足那些 Nx(N-1)/2 边权重。这证明了我的主张。）
让我们假设有一种算法可以在不到 O(n) 的时间内检查交叉点长度。现在让我们读取部分输入。我们有两个选择：
我们已经阅读了整套和另一套的一部分，或者我们已经阅读了第一套的一部分和另一套的一部分。
选项 1):
反例 - 让我们采用这样的输入，即存在一个在集合 1 中读取但尚未从集合 2 中读取但它在集合 2 中的元素 - 我们将收到不正确的结果。
选项 2):
反例 - 我们可以输入这样的元素，该元素存在于两组中但至少有一组未被读取。我们收到错误的结果。
好的，我们已经证明没有这样的算法 returns 在我们不读取整个输入时得到正确的结果。
让我们读取整个输入 - n 个数字。哎呀，复杂度是O(n).
证明结束。
我建议您看一下两种可能的替代方案，它们在实践中效果特别好（尤其是在大集合的情况下）。
1。 Bloom Filter数据结构
布隆过滤器是一种space高效（基于位数组）概率数据结构，用于测试元素是否是集合的成员。假阳性匹配是可能的，但假阴性是不可能的。
在误报率和布隆过滤器的内存占用之间存在权衡。因此，可以为不同的用例估计布隆过滤器的适当大小。
每个集都可以与其自己的布隆过滤器相关联。 很容易得到Bloom Filter，它对应于不同集合的交集：所有的位数组，对应于不同的Bloom Filter，可以使用按位组合AND 操作.
有了与交集对应的布隆过滤器，就可以快速找到所有相交集中存在的项目。
除此之外，可以在不对整个集合进行实际迭代的情况下估计交集的基数： https://en.wikipedia.org/wiki/Bloom_filter#The_union_and_intersection_of_sets
2。 Skip list数据结构
跳表是一种数据结构，允许在有序的元素序列中进行快速搜索和交集。通过维护子序列的链接层次结构可以实现快速搜索和交集，每个子序列跳过较少的元素。
简而言之，Skip List 与普通的 Linked List 数据结构非常相似，但是 Skip List 的每个节点都有几个额外的指向项目的指针，它们位于更远的位置（指针，“跳过”列表中的其他几个节点）。
因此，为了获得交集——需要维护所有被交集的Skip Lists中的指针。在 Skip Lists 的交集期间，指针会跳过项目，这些项目并不存在于所有相交的 Skip Lists 中。因此，通常交集操作的运行时复杂度比 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 中使用跳跃列表的额外 Whosebug 问题：how lucene use skip list in inverted index?
随机select两组，两组都包含不同的键（一个键可以属于多个组，一组不能包含重复的键）。
Return一个整数，表示属于两个集合的键数。
例如相交({1,2,3,4},{3,4,5}) returns 2 .
我只需要路口的大小。我不需要确切地知道路口有哪些键。
是否有任何数据结构在 少于 O(n) 时间 内支持这种操作？
编辑：
读出数据确实需要O(n)的时间，但是不会得出不能进行交集运算的结论少于 O(n) 时间 .
想像这个场景：
我有N套，每套100把钥匙。我读了一遍，那是 N*100 次操作。现在我想知道 对集合有最大的交集，那是 O(N²) 次交集操作。所以我想降低交集操作的复杂性。我真的不关心读取和构造集合需要多少时间，它最多是 N*100，这与 O(N²) 交集操作相比没什么。
请注意，您无法通过少于 O(N²) 次交集运算找到具有最大交集的集合对，我可以证明。您必须 做所有的交集操作。
（他的基本思想是，让我们想象一个完整的图，有 N 个顶点，每个顶点代表一个集合，和 Nx(N-1)/2 条边，每个代表连接对的交集。现在给出每条边都是你想要的非负权重（代表交集大小），我总是可以构造 N 组满足那些 Nx(N-1)/2 边权重。这证明了我的主张。）
让我们假设有一种算法可以在不到 O(n) 的时间内检查交叉点长度。现在让我们读取部分输入。我们有两个选择：
我们已经阅读了整套和另一套的一部分，或者我们已经阅读了第一套的一部分和另一套的一部分。
选项 1):
反例 - 让我们采用这样的输入，即存在一个在集合 1 中读取但尚未从集合 2 中读取但它在集合 2 中的元素 - 我们将收到不正确的结果。
选项 2):
反例 - 我们可以输入这样的元素，该元素存在于两组中但至少有一组未被读取。我们收到错误的结果。
好的，我们已经证明没有这样的算法 returns 在我们不读取整个输入时得到正确的结果。
让我们读取整个输入 - n 个数字。哎呀，复杂度是O(n).
证明结束。
我建议您看一下两种可能的替代方案，它们在实践中效果特别好（尤其是在大集合的情况下）。
1。 Bloom Filter数据结构
布隆过滤器是一种space高效（基于位数组）概率数据结构，用于测试元素是否是集合的成员。假阳性匹配是可能的，但假阴性是不可能的。
在误报率和布隆过滤器的内存占用之间存在权衡。因此，可以为不同的用例估计布隆过滤器的适当大小。
每个集都可以与其自己的布隆过滤器相关联。 很容易得到Bloom Filter，它对应于不同集合的交集：所有的位数组，对应于不同的Bloom Filter，可以使用按位组合AND 操作.
有了与交集对应的布隆过滤器，就可以快速找到所有相交集中存在的项目。
除此之外，可以在不对整个集合进行实际迭代的情况下估计交集的基数： https://en.wikipedia.org/wiki/Bloom_filter#The_union_and_intersection_of_sets
2。 Skip list数据结构
跳表是一种数据结构，允许在有序的元素序列中进行快速搜索和交集。通过维护子序列的链接层次结构可以实现快速搜索和交集，每个子序列跳过较少的元素。
简而言之，Skip List 与普通的 Linked List 数据结构非常相似，但是 Skip List 的每个节点都有几个额外的指向项目的指针，它们位于更远的位置（指针，“跳过”列表中的其他几个节点）。
因此，为了获得交集——需要维护所有被交集的Skip Lists中的指针。在 Skip Lists 的交集期间，指针会跳过项目，这些项目并不存在于所有相交的 Skip Lists 中。因此，通常交集操作的运行时复杂度比 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 中使用跳跃列表的额外 Whosebug 问题：how lucene use skip list in inverted index?