程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 網頁編程 >> PHP編程 >> 關於PHP編程 >> 給定a、b兩個文件,各存放50億個url,每個url各占用64字節,內存限制是4G,如何找出a、b文件共同的url?,50億4g

給定a、b兩個文件,各存放50億個url,每個url各占用64字節,內存限制是4G,如何找出a、b文件共同的url?,50億4g

編輯:關於PHP編程

給定a、b兩個文件,各存放50億個url,每個url各占用64字節,內存限制是4G,如何找出a、b文件共同的url?,50億4g


可以估計每個文件的大小為5G*64=300G,遠大於4G。所以不可能將其完全加載到內存中處理。考慮采取分而治之的方法。 
遍歷文件a,對每個url求取hash(url)%1000,然後根據所得值將url分別存儲到1000個小文件(設為a0,a1,...a999)當中。這樣每個小文件的大小約為300M。遍歷文件b,采取和a相同的方法將url分別存儲到1000個小文件(b0,b1....b999)中。這樣處理後,所有可能相同的url都在對應的小文件(a0 vs b0, a1 vs b1....a999 vs b999)當中,不對應的小文件(比如a0 vs b99)不可能有相同的url。然後我們只要求出1000對小文件中相同的url即可。 
比如對於a0 vs b0,我們可以遍歷a0,將其中的url存儲到hash_map當中。然後遍歷b0,如果url在hash_map中,則說明此url在a和b中同時存在,保存到文件中即可。 
如果分成的小文件不均勻,導致有些小文件太大(比如大於2G),可以考慮將這些太大的小文件再按類似的方法分成小小文件即可

 

昨天百度面試官問道的 今天研究一下

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved