簡(jiǎn)述 hadoop 怎么樣實(shí)現(xiàn)二級(jí)排序？

在Reduce階段，先對(duì)Key排序，再對(duì)Value排序
最常用的方法是將Value放到Key中，實(shí)現(xiàn)一個(gè)組合Key，然后自定義Key排序規(guī)則(為Key實(shí)現(xiàn)一個(gè)WritableComparable)

如何使用MapReduce實(shí)現(xiàn)兩個(gè)表join，可以考慮一下幾種情況:(1)一個(gè)表大，一個(gè)表小(可放到內(nèi)存中) (2)兩個(gè)表都是大表

第一種情況比較簡(jiǎn)單，只需將小表放到DistributedCache中即可；
第二種情況常用的方法有：map-side join(要求輸入數(shù)據(jù)有序，通常用戶Hbase中的數(shù)據(jù)表連接)，reduce-side join，semi join(半連接)

給定 a、b 兩個(gè)文件，各存放 50 億個(gè) url，每個(gè) url 各占 64 字節(jié)，內(nèi)存限制是 4G，讓你找出 a、b 文件共同的 url？

方案 1：將大文件分成能夠被內(nèi)存加載的小文件。
可以估計(jì)每個(gè)文件安的大小為 50G×64=320G，遠(yuǎn)遠(yuǎn)大于內(nèi)存限制的 4G。
所以不可能將其完全加載到內(nèi)存中處理?？紤]采取分而治之的方法。
s遍歷文件a，對(duì)每個(gè)url求取 ，然后根據(jù)所取得的值將url分別存儲(chǔ)到 1000 個(gè)小文件(記為)中
這樣每個(gè)小文件的大約為300M。
s遍歷文件b，采取和a相同的方式將url分別存儲(chǔ)到1000各小文件(記為)
這樣處理后，所有可能相同的url都在對(duì)應(yīng)的小文件()中，不對(duì)應(yīng)的小文件不可能有相同的url
然后我們只要求出1000對(duì)小文件中相同的url即可
s 求每對(duì)小文件中相同的url時(shí)，可以把其中一個(gè)小文件的url存儲(chǔ)到 hash_set中
然后遍歷另一個(gè)小文件的每個(gè)url，看其是否在剛才構(gòu)建的hash_set中，
如果是，那么就是共同的url，存到文件里面就可以了。

方案 2：內(nèi)存映射成 BIT 最小存儲(chǔ)單元。
如果允許有一定的錯(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ò)誤率)。

有10個(gè)文件，每個(gè)文件1G，每個(gè)文件的每一行存放的都是用戶的query，每個(gè)文件的query都可能重復(fù)。要求你按照query的頻度排序

方案 1：
s順序讀取10個(gè)文件，按照 hash(query)%10 的結(jié)果將 query 寫入到另外10個(gè)文件(記為)中
這樣新生成的文件每個(gè)的大小大約也1G(假設(shè) hash 函數(shù)是隨機(jī)的)
s找一臺(tái)內(nèi)存在2G左右的機(jī)器，依次對(duì)用hash_map(query,query_count)來(lái)統(tǒng)計(jì)每個(gè)query出現(xiàn)的次數(shù)。
利用快速/堆/歸并排序按照出現(xiàn)次數(shù)進(jìn)行排序。
將排序好的 query 和對(duì)應(yīng)的 query_cout 輸出到文件中。
這樣得到了 10 個(gè)排好序的文件(記為)
s 對(duì) 這 10 個(gè)文件進(jìn)行歸并排序(內(nèi)排序與外排序相結(jié)合)

方案 2：
一般query的總量是有限的，只是重復(fù)的次數(shù)比較多而已，可能對(duì)于所有的query，一次性就可以加入到內(nèi)存了
這樣，我們就可以采用 trie樹(shù)/hash_map 等直接來(lái)統(tǒng)計(jì)每個(gè) query 出現(xiàn)的次數(shù)，然后按出現(xiàn)次數(shù)做快速/堆/歸并排序就可以了。

方案 3：
與方案1類似，但在做完 hash，分成多個(gè)文件后，可以交給多個(gè)文件來(lái)處理，
采用分布式的架構(gòu)來(lái)處理（比如 MapReduce），最后再進(jìn)行合并。
//一般在大文件中找出出現(xiàn)頻率高的，先把大文件映射成小文件，模 1000，在小文件中找到高頻的

有一個(gè) 1G 大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過(guò) 16 字節(jié)，內(nèi)存限制大小是 1M。返回頻數(shù)最高的 100 個(gè)詞

方案 1：
順序讀文件中，對(duì)于每個(gè)詞x,取 ，然后按照該值存到5000個(gè)小文件(記為 )中。
這樣每個(gè)文件大概是 200k 左右。
如果其中的有的文件超過(guò)了 1M 大小，還可以按照類似的方法繼續(xù)往下分
知道分解得到的小文件的大小都不超過(guò) 1M。 
對(duì)每個(gè)小文件，統(tǒng)計(jì)每個(gè)文件中出現(xiàn)的詞以及相應(yīng)的頻率(可以采用trie樹(shù)/hash_map等)，
并取出出現(xiàn)頻率最大的100個(gè)詞(可以用含100個(gè)結(jié) 點(diǎn)的最小堆)，
并把100詞及相應(yīng)的頻率存入文件，這樣又得到了 5000 個(gè)文件。
下一步就是把這 5000 個(gè)文件進(jìn)行歸并(類似與歸并排序)的過(guò)程了。

方案2:
1 將文件逐行讀寫到另一個(gè)文件中，并將每行單詞全變成小寫
2 十六次循環(huán)執(zhí)行，將每行單詞按照a-z寫到不同文件里
3 最后相同的單詞都寫在了通一個(gè)文件里
4 再將文件讀寫到各自另一個(gè)文件里，內(nèi)容是“單詞 個(gè)數(shù)”
5 定義一個(gè)treemap，大小是100，依次插入大的，移除小的
6 最后得出結(jié)果

海量日志數(shù)據(jù)，提取出某日訪問(wèn)百度次數(shù)最多的那個(gè) IP

1 先根據(jù)日期在日志文件中提取出ip，根據(jù)ip哈希進(jìn)行分寫N個(gè)文件。
2 采用mapreduce的word cont

方案 1：
首先是這一天，并且是訪問(wèn)百度的日志中的 IP 取出來(lái)，逐個(gè)寫入到一個(gè)大文件中。
注意到 IP是 32 位的，最多有 個(gè) IP。同樣可以采用映射的方法，比如模 1000，
把整個(gè)大文件映射為1000個(gè)小文件，
再找出每個(gè)小文中出現(xiàn)頻率最大的IP(可以采用hash_map進(jìn)行頻率統(tǒng)計(jì)，然后再找出頻率最大的幾個(gè))及相應(yīng)的頻率。
然后再在這1000個(gè)最大的IP中，找出那個(gè)頻率最大的IP，即為所求。

在 2.5 億個(gè)整數(shù)中找出不重復(fù)的整數(shù)，內(nèi)存不足以容納這 2.5 億個(gè)整數(shù)

方案 1：
采用 2-Bitmap(每個(gè)數(shù)分配 2bit,00表示不存在,01表示出現(xiàn)一次,10表示多次,11無(wú)意義)進(jìn)行，
共需內(nèi)存 內(nèi)存，還可以接受。
然后掃描這 2.5 億個(gè)整數(shù)，查看 Bitmap 中相對(duì)應(yīng)位，
如果是00變 01，01變10，10保持不變。
所描完事后，查看 bitmap，把對(duì)應(yīng)位是 01 的整數(shù)輸出即可。

方案 2：
也可采用上題類似的方法，進(jìn)行劃分小文件的方法
然后在小文件中找出不重復(fù)的整數(shù)，并排序
然后再進(jìn)行歸并，注意去除重復(fù)的元素。

方案3：
1 將2.5億個(gè)整數(shù)重寫到一個(gè)文件里，內(nèi)個(gè)整數(shù)占一行。
2 進(jìn)行對(duì)半排序重寫到新的文件里，這樣最后2.5億個(gè)整數(shù)在文件里便是有序的了
3 讀取文本，將不重復(fù)的寫到一個(gè)新的文件里即可。

一個(gè)文本文件，大約有一萬(wàn)行，每行一個(gè)詞，要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前 10 個(gè)詞，請(qǐng)給出思想，給出時(shí)間復(fù)雜度分析

方案 1：
這題是考慮時(shí)間效率。用trie 樹(shù)統(tǒng)計(jì)每個(gè)詞出現(xiàn)的次數(shù)，時(shí)間復(fù)雜度是 O(n*le)(le表示單詞的平準(zhǔn)長(zhǎng)度)
然后是找出出現(xiàn)最頻繁的前 10 個(gè)詞，可以用堆來(lái)實(shí)現(xiàn)，時(shí)間復(fù)雜度是 O(n*lg10)。
所以總的時(shí)間復(fù)雜度，是 O(n*le)與 O(n*lg10)中較大的哪一個(gè)