處理海量數據的常規思路
分而治之/Hash映射 + Hash_map統計 + 堆/快速/歸並排序
1、海量日誌數據，提取出某日訪問百度次數最多的那個IP
1.)分而治之/hash映射：把大文件化成(取模映射)小文件
2)hash_map統計：當大文件轉化了小文件，那麽我們便可以采用常規的hash_map(ip，value)來進行頻率統計O(n)復雜度
3)堆/快速排序：得到每個文件次數最多的IP,然後匯總這幾個文件排序取最大的ip次數
首先是這壹天，並且是訪問百度的日誌中的IP取出來，逐個寫入到壹個大文件中。註意到IP是32位的，最多有個2^32個IP。同樣可以采用 hash映射 的方法，比如%1000，把整個大文件映射為1000個小文件，再找出每個小文件中出現頻率最大的IP（可以采用 hash_map 對那1000個文件中的所有IP進行頻率統計，然後 依次找出各個文件中頻率最大的那個IP ）及相應的頻率。然後再在這 1000個最大的IP中 ，找出那個頻率 最大的IP ，即為所求。
2、尋找熱門查詢，300萬個查詢字符串中統計最熱門的10個查詢
1. hash映射 ：順序讀文件中，對於每個詞x，取hash(x)%5000，然後按照該值存到5000個小文件（記為x0,x1,...x4999）中
這樣每個文件大概是200k左右。如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續往下分，直到分解得到的小文件的大小都不超過1M
2. hash_map統計 ：對每個小文件，采用trie樹/hash_map等統計每個文件中出現的詞以及相應的頻率
3. 堆/歸並排序 ：取出出現頻率最大的100個詞（可以用含100個結點的 最小堆 ）後，再把100個詞及相應的頻率存入文件，這樣又得到了5000個文件。最後就是把這5000個文件進行 歸並（類似於歸並排序） 的過程了
5、有10個文件，每個文件1G，每個文件的每壹行存放的都是用戶的query，每個文件的query都可能重復。要求妳按照query的頻度排序
hash映射/取模->hashMap統計->單文件堆排序->多文件歸並
6、 給定a、b兩個文件，各存放50億個url，每個url各占64字節，內存限制是4G，讓妳找出a、b文件***同的url？
1. 分而治之/hash映射 ：遍歷文件a，對每個url求取，然後根據所取得的值將url分別存儲到1000個小文件。這樣每個小文件的大約為300M。遍歷文件b，采取和a相同的方式將url分別存儲到1000小文件中（記為）。這樣處理後，所有可能相同的url都在對應的小文件（
O（N） + N' * O（logK），（N為1萬，N’為hashmap的key的元素 算1萬吧,K=10）
用壹個含100個元素的最小堆完成。復雜度為O(100w*lg100)
13、2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。
/writer#/notebooks/45731388/notes/70253940/preview
對於這道題，順序讀取這 5 億個數字，對於讀取到的數字 num，如果它對應的二進制中最高位為 1，則把這個數字寫到 f1 中，否則寫入 f0 中。通過這壹步，可以把這 5 億個數劃分為兩部分，而且 f1 中的數都大於 f0中的數。
劃分之後，可以非常容易地知道中位數是在 f0 還是 f1 中。假設 f0中有 1 億個數，那麽中位數壹定在 f1 中，且是在 f1 中，從小到大排列的第 1.5 億個數與它後面的壹個數的平均值。
對於 f1可以用次高位的二進制繼續將文件壹分為二，如此劃分下去，直到劃分後的文件可以被加載到內存中，把數據加載到內存中以後直接排序或使用快排或堆排序(小頂堆) 找出第K大的數，從而找出中位數。
/s/rdz4pfTCeX1ahOM4KAi3oQ
/s/VXGtJ9Miwfc1yD3v44kvnw