iou*_*vxz 4 algorithm intersection time-complexity set-operations data-structures
随机选择两个集合,两个集合都包含不同的密钥(一个密钥可能属于多个集合,一个集合永远不能包含重复的密钥).
返回一个整数,表示属于两个组的键数.
例如,intersect({1,2,3,4},{3,4,5})返回2.
我只需要交叉点的大小.我不需要确切地知道交叉点中哪些键.
是否有任何数据结构在不到O(n)的时间内支持这种操作？
编辑:
读取数据确实需要O(n)时间,但这不会导致您不能在少于O(n)时间内完成交叉操作的结论.
想象这个场景:
我有N套,每套包含100把钥匙.我读了它们,那是N*100次操作.现在我想知道女巫对有最大的交集,即O(N²)交叉操作.所以我想减少交叉操作的复杂性.我不是真的关心读取和构建集合所花费的时间,最多为N*100,这与O(N²)交叉操作无关.
请注意,通过执行少于O(N²)交叉操作,您无法找到具有最大交点的一对集合,我可以证明这一点.您必须执行所有交叉操作.
(他的基本思想是,让我们想象一个完整的图,有N个顶点,每个顶点代表一个集合,Nx(N-1)/ 2个边,每个代表连接对的交集.现在给每个边不为所有你想要的negetive weight(代表交叉点大小),我总是可以构造N个满足那些Nx(N-1)/ 2边缘权重.这证明了我的主张.)
我建议你看看两种可能的替代方案,它们在实践中特别有效(特别是在大型套装的情况下).
布隆过滤器是一种节省空间的(基于位阵列)概率数据结构,用于测试元素是否是集合的成员.可能存在误报匹配,但假阴性则不然.
假阳性率与布隆过滤器的内存占用之间存在折衷.因此,可以针对不同的用例估计布隆过滤器的适当大小.
每个集合都可以与自己的Bloom过滤器相关联.获得布隆过滤器非常容易,布隆过滤器对应于不同集合的交集:所有位阵列(对应于不同的布隆过滤器)可以使用按位AND运算进行组合.
具有对应于交叉点的布隆过滤器,可以快速找到存在于所有相交集中的项目.
除此之外,可以在没有实际迭代的情况下估计交叉点的基数: https ://en.wikipedia.org/wiki/Bloom_filter#The_union_and_intersection_of_sets
跳过列表是一种数据结构,允许在有序的元素序列中快速搜索和交叉.通过维护子序列的链接层次结构,每个跳过较少的元素,可以实现快速搜索和交叉.
简洁地说,Skip List与普通的Linked List数据结构非常相似,但是Skip List的每个节点都有一些额外的指向项目的指针,这些指针位于更远的位置(指针,"跳过"其他几个节点)列表).
因此,为了获得交集 - 需要将指针保持在所有正在相交的跳过列表中.在跳过列表的交集期间,指针跳过项目,这些项目不存在于所有相交的跳过列表中.因此,通常交叉操作的运行时复杂性更快O(N).
Skip Lists的交集算法在"信息检索简介"(由Christopher D. Manning,Prabhakar Raghavan,HinrichSchütze编写)一书中描述:http: //nlp.stanford.edu/IR-book/html/ htmledition /更快的贴子一览交叉点通过跳过指针-1.HTML
跳过列表主要用于高性能,功能齐全的文本搜索引擎库:Apache Lucene(跳过列表在反向索引组件中使用).
这是关于Lucene中Skip Lists的使用的另一个Stackoverflow问题:lucene如何在倒排索引中使用跳过列表？