当前位置:网站首页>有序链表集合求交集 方法 总结
有序链表集合求交集 方法 总结
2022-07-05 15:48:00 【软件工程小施同学】
- 二重for循环法,时间复杂度O(n*n)
- 拉链法,时间复杂度O(n)
- 水平分桶,多线程并行
- bitmap,大大提高运算并行度,时间复杂度O(n)
- 跳表,时间复杂度为O(log(n))
方案一:for * for,土办法,时间复杂度O(n*n)
画外音:比较笨的方法。
方案二:有序list求交集,拉链法
有序集合1{1,3,5,7,8,9}
有序集合2{2,3,4,5,6,7}
两个指针指向首元素,比较元素的大小:
(1)如果相同,放入结果集,随意移动一个指针;
(2)否则,移动值较小的一个指针,直到队尾;
这种方法的好处是:
利用“有序”这个特性,集合中的元素最多被比较一次,时间复杂度为O(n);
这个方法就像一条拉链的两边齿轮,一一比对就像拉链,故称为拉链法
方案三:分桶并行优化
举例:
有序集合1{1,3,5,7,8,9, 10,30,50,70,80,90}
有序集合2{2,3,4,5,6,7, 20,30,40,50,60,70}
求交集,先进行分桶拆分:
桶1的范围为[1, 9]
桶2的范围为[10, 100]
桶3的范围为[101, max_int]
于是:
集合1就拆分成
集合a{1,3,5,7,8,9}
集合b{10,30,50,70,80,90}
集合c{}
集合2就拆分成
集合d{2,3,4,5,6,7}
集合e{20,30,40,50,60,70}
集合e{}
每个桶内的数据量大大降低了,并且每个桶内没有重复元素,可以利用多线程并行计算:
桶1内的集合a和集合d的交集是x{3,5,7}
桶2内的集合b和集合e的交集是y{30, 50, 70}
桶3内的集合c和集合d的交集是z{}
最终,集合1和集合2的交集,是x与y与z的并集,即集合{3,5,7,30,50,70}。
画外音:多线程、水平切分都是常见的优化手段。
方案四:bitmap再次优化
数据进行了水平分桶拆分之后,每个桶内的数据一定处于一个范围之内,如果集合符合这个特点,就可以使用bitmap来表示集合:
如上图,假设set1{1,3,5,7,8,9}和set2{2,3,4,5,6,7}的所有元素都在桶值[1, 16]的范围之内,可以用16个bit来描述这两个集合,原集合中的元素x,在这个16bitmap中的第x个bit为1,此时两个bitmap求交集,只需要将两个bitmap进行“与”操作,结果集bitmap的3,5,7位是1,表明原集合的交集为{3,5,7}。
水平分桶,bitmap优化之后,能极大提高求交集的效率,但时间复杂度仍旧是O(n)。bitmap需要大量连续空间,占用内存较大。
画外音:bitmap能够表示集合,用它求集合交集速度非常快。
方案五:跳表skiplist
有序链表集合求交集,跳表是最常用的数据结构,它可以将有序集合求交集的复杂度由O(n)降至接近O(log(n))。
集合1{1,2,3,4,20,21,22,23,50,60,70}
集合2{50,70}
要求交集,如果用拉链法,会发现1,2,3,4,20,21,22,23都要被无效遍历一次,每个元素都要被比对,时间复杂度为O(n),能不能每次比对“跳过一些元素”呢?
跳表就出现了:
集合1{1,2,3,4,20,21,22,23,50,60,70}建立跳表时,一级只有{1,20,50}三个元素,二级与普通链表相同。
集合2{50,70}由于元素较少,只建立了一级普通链表。
如此这般,在实施“拉链”求交集的过程中,set1的指针能够由1跳到20再跳到50,中间能够跳过很多元素,无需进行一一比对,跳表求交集的时间复杂度近似O(log(n))。
来自:https://mp.weixin.qq.com/s/6qU7yWKhMZUiyu7TlcuiSA
边栏推荐
猜你喜欢
Use of RLOCK lock
17. [stm32] use only three wires to drive LCD1602 LCD
Why should we learn mathematical modeling?
通过的英特尔Evo 3.0整机认证到底有多难?忆联科技告诉你
迁移/home分区
Research and development efficiency measurement index composition and efficiency measurement methodology
PSPNet | 语义分割及场景分析
Defining strict standards, Intel Evo 3.0 is accelerating the upgrading of the PC industry
List de duplication and count the number
五种常见的咨询公司谈判策略以及如何维护自己的利益
随机推荐
StarkWare:欲构建ZK“宇宙”
The new version of effect editor is online! 3D rendering, labeling, and animation, this time an editor is enough
16.[STM32]从原理开始带你了解DS18B20温度传感器-四位数码管显示温度
ES6深入—ES6 Generator 函数
今日睡眠质量记录79分
漫画:什么是分布式事务?
助力数字经济发展,夯实数字人才底座—数字人才大赛在昆成功举办
Mongodb getting started Tutorial Part 04 mongodb client
How difficult is it to pass the certification of Intel Evo 3.0? Yilian technology tells you
Example project: simple hexapod Walker
DataArts Studio数据架构——数据标准介绍
ES6 deep - ES6 class class
【毕业季】作为一名大二计科在校生,我有话想说
Seaborn draws 11 histograms
sql中set标签的使用
Boost the development of digital economy and consolidate the base of digital talents - the digital talent competition was successfully held in Kunming
服务器的数据库连不上了2003,10060“Unknown error“【服务已起、防火墙已关、端口已开、netlent 端口不通】
Relationship between objects and classes
写单元测试的时候犯的错
Which keywords will conflict with the abstract keyword