給定a、b兩個文件，各存放50億個url，每個url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url?
可以估計(jì)每個文件安的大小為5G×64=320G，遠(yuǎn)遠(yuǎn)大于內(nèi)存限制的4G。所以不可能將其完全加載到內(nèi)存中處理。考慮采取分而治之的方法。
分而治之/hash映射: 遍歷文件a，對每個url求取，然后根據(jù)所取得的值將url分別存儲到1000個小文件(記為，這里漏寫個了a1)中。這樣每個小文件的大約為300M。遍歷文件b，采取和a相同的方式將url分別存儲到1000小文件中(記為)。這樣處理后，所有可能相同的url都在對應(yīng)的小文件()中，不對應(yīng)的小文件不可能有相同的url。然后我們只要求出1000對小文件中相同的url即可。
hash_set統(tǒng)計(jì): 求每對小文件中相同的url時，可以把其中一個小文件的url存儲到hash_set中。然后遍歷另一個小文件的每個url，看其是否在剛才構(gòu)建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
如果允許有一定的錯誤率，可以使用Bloom filter，4G內(nèi)存大概可以表示340億bit。將其中一個文件中的url使用Bloom filter映射為這340億bit，然后挨個讀取另外一個文件的url，檢查是否與Bloom filter，如果是，那么該url應(yīng)該是共同的url(注意會有一定的錯誤率)。”
京公網(wǎng)安備 11010802030320號