当前位置:网站首页>Summary of methods for finding intersection of ordered linked list sets
Summary of methods for finding intersection of ordered linked list sets
2022-07-05 16:30:00 【Software engineering Xiao Shi】
- double for Circulation , Time complexity O(n*n)
- Zipper method , Time complexity O(n)
- Divide the barrels horizontally , Multithreading parallel
- bitmap, Greatly improve the parallelism of operation , Time complexity O(n)
- Jump watch , The time complexity is O(log(n))
Scheme 1 :for * for, Earth way , Time complexity O(n*n)
Voice over : Stupid way .
Option two : Orderly list Find the intersection , Zipper method
Ordered set 1{1,3,5,7,8,9}
Ordered set 2{2,3,4,5,6,7}
Two pointers point to the first element , Compare the size of the elements :
(1) If the same , Put the result set , Move a pointer at will ;
(2) otherwise , Move a pointer with a smaller value , Until the end of the team ;
The advantage of this method is :
utilize “ Orderly ” This feature , The elements in the collection are compared at most once , The time complexity is O(n);
This method is like the gears on both sides of a zipper , One by one comparison is like a zipper , So it's called zipper method
Option three : Parallel optimization by buckets
give an example :
Ordered set 1{1,3,5,7,8,9, 10,30,50,70,80,90}
Ordered set 2{2,3,4,5,6,7, 20,30,40,50,60,70}
Find the intersection , Split the buckets first :
bucket 1 For the range of [1, 9]
bucket 2 For the range of [10, 100]
bucket 3 For the range of [101, max_int]
therefore :
aggregate 1 Split it into
aggregate a{1,3,5,7,8,9}
aggregate b{10,30,50,70,80,90}
aggregate c{}
aggregate 2 Split it into
aggregate d{2,3,4,5,6,7}
aggregate e{20,30,40,50,60,70}
aggregate e{}
The amount of data in each bucket is greatly reduced , And there is no repeating element in each bucket , You can use multithreaded parallel computing :
bucket 1 A collection within a And collection d The intersection of x{3,5,7}
bucket 2 A collection within b And collection e The intersection of y{30, 50, 70}
bucket 3 A collection within c And collection d The intersection of z{}
Final , aggregate 1 And collection 2 Intersection , yes x And y And z Union , I.e. set {3,5,7,30,50,70}.
Voice over : Multithreading 、 Horizontal segmentation is a common optimization method .
Option four :bitmap Optimize again
After the data is split horizontally , The data in each bucket must be in a range , If the set matches this characteristic , You can use bitmap To represent a set :
Pictured above , hypothesis set1{1,3,5,7,8,9} and set2{2,3,4,5,6,7} All of the elements in the bucket value [1, 16] Within the scope of , It can be used 16 individual bit To describe these two sets , The elements of the original collection x, In this 16bitmap No x individual bit by 1, Now two bitmap Find the intersection , Just put two bitmap Conduct “ And ” operation , Result set bitmap Of 3,5,7 Is it 1, Indicates that the intersection of the original set is {3,5,7}.
Divide the barrels horizontally ,bitmap After the optimization , Can greatly improve the efficiency of intersection , But time complexity is still O(n).bitmap It takes a lot of continuous space , Large memory footprint .
Voice over :bitmap Can represent a set , It's very fast to find the intersection of sets .
Option five : Jump watch skiplist
The intersection of the ordered list set , Jump table is the most commonly used data structure , It can get the complexity of intersection from O(n) It's close to O(log(n)).
aggregate 1{1,2,3,4,20,21,22,23,50,60,70}
aggregate 2{50,70}
Ask for intersection , If you use zipper method , Will find 1,2,3,4,20,21,22,23 All have to be traversed invalid once , Every element has to be compared , The time complexity is O(n), Can you compare each time “ Skip some elements ” Well ?
The jump watch appears :
aggregate 1{1,2,3,4,20,21,22,23,50,60,70} When creating a jump table , There is only one level {1,20,50} Three elements , The second level is the same as the common list .
aggregate 2{50,70} Because there are fewer elements , Only one level of common linked list has been established .
such , In implementation “ zipper ” In the process of finding intersection ,set1 The pointer of can be controlled by 1 Jump to the 20 Jump to 50, Can skip many elements in the middle , There is no need to compare one by one , The time complexity of finding intersection is approximate O(log(n)).
come from :https://mp.weixin.qq.com/s/6qU7yWKhMZUiyu7TlcuiSA
边栏推荐
- 漫画:什么是服务熔断?
- 给自己打打气
- Pspnet | semantic segmentation and scene analysis
- Apple 已弃用 NavigationView,使用 NavigationStack 和 NavigationSplitView 实现 SwiftUI 导航
- 利用GrayLog告警功能实现钉钉群机器人定时工作提醒
- 数据访问 - EntityFramework集成
- Explain in detail the functions and underlying implementation logic of the groups sets statement in SQL
- 超分辨率技术在实时音视频领域的研究与实践
- HiEngine:可媲美本地的云原生内存数据库引擎
- Which keywords will conflict with the abstract keyword
猜你喜欢
新春限定丨“牛年忘烦”礼包等你来领~
PSPNet | 语义分割及场景分析
Domestic API management artifact used by the company
Explain in detail the functions and underlying implementation logic of the groups sets statement in SQL
The visual experience has been comprehensively upgraded, and Howell group and Intel Evo 3.0 have jointly accelerated the reform of the PC industry
公司自用的国产API管理神器
Intel 13th generation Raptor Lake processor information exposure: more cores, larger cache
Win11提示无法安全下载软件怎么办?Win11无法安全下载软件
Spring Festival Limited "forget trouble in the year of the ox" gift bag waiting for you to pick it up~
Batch update in the project
随机推荐
英特尔第13代Raptor Lake处理器信息曝光:更多核心 更大缓存
yarn 常用命令
Research and development efficiency measurement index composition and efficiency measurement methodology
Quelques réflexions cognitives
不敢买的思考
Coding devsecops helps financial enterprises run out of digital acceleration
Flet教程之 09 NavigationRail 基础入门(教程含源码)
Apiccloud cloud debugging solution
CISP-PTE之PHP伪协议总结
《21天精通TypeScript-3》-安装搭建TypeScript开发环境.md
效果编辑器新版上线!3D渲染、加标注、设置动画,这次一个编辑器就够了
Flet教程之 11 Row组件在水平数组中显示其子项的控件 基础入门(教程含源码)
vant popup+其他组件的组合使用,及避坑指南
Flet教程之 12 Stack 重叠组建图文混合 基础入门(教程含源码)
Cs231n notes (medium) -- applicable to 0 Foundation
一键安装脚本实现快速部署GrayLog Server 4.2.10单机版
Win11如何给应用换图标?Win11给应用换图标的方法
Single merchant v4.4 has the same original intention and strength!
ES6深入—ES6 Class 类
异常com.alibaba.fastjson.JSONException: not match : - =