6 Set Intersection

• Merge-based Set intersection (merge_intersection.hpp)
• Binary-search-based Set intersection (binary_search.hpp)
• Mutual Partitioning Set intersection (mutual_partitioning.hpp)
• Doubling Search Set intersection (doubling_search.hpp)

Benchmark

Intersection between two sets A and B, M = |A| < N = |B|

Complexities:

• STL O(M+N)
• Merge-based O(M+N)
• Binary Search O(M*log(N))
• Mutual Partitioning O(M(1+log(N/M)))
• Doubling Search O(M(1+log(N/M)))

Execution times (avg of 10):

M	N	STL	Merge-based	Binary Search	Mutual Partitioning	Doubling Search
100	10000	0.000008s	0.000006s	0.000004s	0.000004s	0.000003s
1000	10000	0.000014s	0.000011s	0.000032s	0.000034s	0.000015s
10000	10000	0.000044s	0.000043s	0.000224s	0.000115s	0.000070s
100	100000	0.000082s	0.000054s	0.000016s	0.000017s	0.000015s
1000	100000	0.000085s	0.000058s	0.000053s	0.000065s	0.000037s
10000	100000	0.000134s	0.000105s	0.000331s	0.000312s	0.000156s
100000	100000	0.000438s	0.000430s	0.002406s	0.001115s	0.000647s
100	1000000	0.001113s	0.000822s	0.000305s	0.000295s	0.000276s
1000	1000000	0.000886s	0.000567s	0.000377s	0.000380s	0.000315s
10000	1000000	0.000853s	0.000585s	0.000753s	0.000926s	0.000560s
100000	1000000	0.001366s	0.001189s	0.004491s	0.003848s	0.001989s
1000000	1000000	0.004345s	0.004270s	0.027922s	0.011657s	0.006956s
100	10000000	0.008053s	0.005829s	0.005781s	0.005788s	0.005749s
1000	10000000	0.008230s	0.005504s	0.005879s	0.005881s	0.005910s
10000	10000000	0.008607s	0.005892s	0.007228s	0.007550s	0.006874s
100000	10000000	0.008461s	0.005992s	0.011398s	0.011987s	0.008643s
1000000	10000000	0.011870s	0.009745s	0.044436s	0.036035s	0.019385s
10000000	10000000	0.044745s	0.043374s	0.310826s	0.123839s	0.073733s
100	100000000	0.081866s	0.055667s	0.053563s	0.052802s	0.053069s
1000	100000000	0.082238s	0.055888s	0.053079s	0.053388s	0.053290s
10000	100000000	0.081775s	0.056059s	0.054290s	0.054628s	0.054802s
100000	100000000	0.081698s	0.055859s	0.063282s	0.065006s	0.061456s
1000000	100000000	0.086038s	0.060308s	0.113153s	0.115882s	0.081410s
10000000	100000000	0.118154s	0.096964s	0.458785s	0.352282s	0.187888s
100000000	100000000	0.444470s	0.432639s	3.227976s	1.208441s	0.731032s