Summary of methods for finding intersection of ordered linked list sets

 - 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

Per second 10W Sub word segmentation search , The product manager raised another demand ！！！（ Collection ）