(1 條消息)如何設計兩組數據量上億的集合求交集的演算法？

02-19

給定兩個整數集合A和B，每個集合都包含20億個不同整數，請給出快速計算A∩B的演算法，演算法可使用外存，但是要求佔用內存不能超過4GB

輸入有4G個數，每個至少4 byte，所以說（非外部）排序的，這真的做不到啊。哈希表同理，你肯定得要點什麼外存來過一下的。

不過，如果輸入確實是32 bit integer的話，直接用bit set就搞定了，空間佔用是512MB。

如果這裡的整數是32位整數，那麼每個集合用一個大小2^32位的bitmap表示，分別遍歷集合算出對應bitmap後，直接遍歷每一位元組取交即可。

每個bitmap的大小是2^32bit / 2^3(bits per Byte) = 512MB，一共使用1GB內存。

構造bitmap的時候，除去bitmap還有3GB可以使用，一共可以存儲3 * 2^30 / 4 = 3 * 2 ^28 = 8億個整數。那每個集合要按每8億個切分到外存中，分成3個部分。這樣構造的時候每個集合讀取3次外存，一共讀取6次。然後如果結果交集很大而且要得到具體整數，也要對結果做切分，最多存儲3次外存。

主要瓶頸應該在讀取外存的部分，但是應該很難做改進了orz

要速度，內存小的話可以考慮布隆過濾器，只是有誤差，給的Hash函數正確的話，內存用的越多誤差越小。

基礎面試題。

對於超大數據集的問題，上來就先看看hash+分治能不能行吧:

1. 選一個hash函數，能將數據集範圍的整數分到若干個桶中，每個桶中落入的數的個數能夠內存處理即可

2. 每個桶內進行常規求交集即可

這個方法不需要用到外存

將20億個數映射到一個包含20億bit的二進位的文件中（238M），將這兩個二進位文件進行操作即可。具體自己看《編程珠璣》。

兩個集合風別用A和B表徵。

$out=AB\ A,Bin {0,...,2^{2^{31}}-1}$

都是整數的話，放一起sort一下然後去除重複元素？