Find Intersection of Two Lists

在 triangle counting 裡面，有個顯而易見的方法^[1]
找任意兩個 node 的 adjacency list 的交集 (有交集表示有三角形)
找交集大概有幾種演算法

假設 list 1 有 n 個 elements、list 2 有 m 個 elements，n > m

I Algorithm

1. Naive

traverse list 1，對於每個 element 都到 list 2 用 linear searcy 看是否存在

時間複雜度 O(nm)
空間複雜度 O(n+m)

list 已經排序好的情況，時間複雜度 O(nm)

[優點]
- 好想又好寫
[缺點]
- 無論如何都很慢

2. Binary Search

先將 list 2 排序好 (prefer: 把 element 較少的 list 排序)
改進方法 1，在搜尋 list 2 時使用 binary searcy

時間複雜度 O(m lg m + n lg m)
空間複雜度 O(n+m)

list 已經排序好的情況，時間複雜度 O( m lg n)
此時 prefer 搜尋 element 較多的 list (list 1 in this case)

[優點]
- 很快
[缺點]
- 如果 list 已經排序好則無優勢

3. Sort and Find

(此方法假設兩 list 都沒有重複的 element)
把兩個 list 合併、排序、之後做 linear search
找出所有相鄰且相同的 element，即為交集

時間複雜度 O(n+m + (n+m) lg (n+m))
空間複雜度 O(n+m)

list 已經排序好的情況，時間複雜度 O(n+m)
採用 merge 的方法排序(和 merging 方法重覆性高，但此方法常數大)

[優點]
- 比 Naive 快
- 好寫
[缺點]
- element 必須不重複(triangle counting 沒有此問題)
- 要被排序的東西較多，比方法 2 稍慢一些

4. Merging

把兩個 list 排序後，用 merge sort 合併的方法找交集

時間複雜度 O(n lg n + m lg m + n+m) 
空間複雜度 O(n+m)

list 已經排序好的情況，時間複雜度 O(n+m)

[優點]
- 比 Naive 快
- 不難寫
[缺點]
想不到特殊的缺點

5. Hashing

traverse list 1，把每個 element 都塞到 hash 內 (hash size = O(n))
(prefer: 把 element 較少的 list 塞進 hash)
traverse list 2，檢查每個 element 是否有存在 hash 內，若有則該 element 屬於交集
(註^[4][5]：C++11 之後，有 build-in 的 hash 可用)

時間複雜度 average O(n+m)
空間複雜度 O(n+m)

list 已經排序好的情況，時間複雜度 O(n+m)
要 hash 會有一些 overhead

[優點]
- 最快(理論上來說)
[缺點]
- 需要較(最)多空間 (for hash table)
- hash function 沒設計好會撞的亂七八糟，導致時間趨近 O(mn)

II Implementation

0. input

隨機產生兩個沒有重複 element 的 list，element 為 [0, 2147483647] 區間內的隨機整數
Testcase size
1) n = 10⁴, m = 2*10⁴
2) n = 10⁶, m = 10⁶
3) n = 10⁶, m = 2*10⁶
4) n = 10⁶, m = 5*10⁶
一開始都存在 STL 的 list< int > container

1. Naive

用兩層 for 迴圈以及 list<int>::iterator traverse 所有 element

[平行的考慮]
兩層 for 很好平行，但需要考慮蒐集答案的問題

2. Binary Search

把 (size) 較小的 list 搬到 STL 的 vector< int > container 後，用 algorithm 的 sort 排序好
再用 traverse 較大的 list，對於每個 element 到較小的 list binary search，若找到則加入交集

[平行的考慮]
很好平行，binary search 的部份可以用 m-way search 取代，但需要考慮蒐集答案的問題

3. Sort and Find

用 splice 把兩個 list 接在一起之後，用 list::sort() 排序
之後 traverse 整個 list，如果發現下一個 element 的值和自己相同則加入交集

[平行的考慮]
可以使用平行版本的排序 (ex: bitonic sort)，traverse 的部份可以用 m+n-1 個 thread 看自己 index+1 的 element 是否和自己一樣，但需考慮蒐集答案的問題

4. Mergeing

用 list::sort() 分別將兩個 list 排序
之後用 list<int>::iterator 當 pointer，利用 merge 的方法找交集，直到任一個 pointer 走到 list.end() 為止

[平行的考慮]
可以使用平行版本的排序 (ex: bitonic sort)，但 merge 的部份想不到好的平行方法

5. Hashing

用 STL 的 unordered_set container 當 hash table，一開始 rehash^[6](n+m)
接著把 (size) 較小的 list 全部的 element 用 unsorted_set::insert() 塞進 hash 內
再用 unsorted_set::find() 依序尋找較大的 list 內所有 element 是否出現在 hash 內，有則加入交集

[平行的考慮]
insert 的時候可以平行，如果能做到幾乎沒有 collision，就不會 lock 到
尋找的時候一樣可以平行，但需考慮蒐集答案的問題

III Performance Comparison

理論上，
未排序時速度 5 > 2 > 4 > 3 > 1
已排序時速度 4 > 3 > 5 > 2 > 1

實驗結果，未排序速度 5 > 2 > 4 > 3 >> 1
naive 後面太慢了就沒有畫進圖裡
[把縱軸改成 log scale 圖待補]



[已排序實驗圖待補]

IV Triangle Counting

123
(尚未實作)

V Reference

[1] http://arrayfire.com/triangle-counting-in-graphs-on-the-gpu-part-1/
[2] http://www.geeksforgeeks.org/union-and-intersection-of-two-linked-lists/
[3] http://stackoverflow.com/questions/497338/efficient-list-intersection-algorithm
[4] http://www.cplusplus.com/reference/functional/hash/
[5] http://www.cplusplus.com/reference/unordered_set/unordered_set/
[6] http://www.cplusplus.com/reference/unordered_set/unordered_set/rehash/