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