雞蛋挺住體:及MapReduce矩陣分析
今日面試題：雞蛋挺住體
兩個(gè)雞蛋：兩個(gè)軟硬程度一樣但未知的雞蛋，它們有可能都在一樓就摔碎，也可能從一百層樓摔下來(lái)沒(méi)事。有座100層的建筑，要你用這兩個(gè)雞蛋以最少的次數(shù)確定哪一層是雞蛋可以安全落下的最高位置?？梢运に閮蓚€(gè)雞蛋。
MapReduce矩陣的分析
題目：
一個(gè)很大的2D矩陣，如果某點(diǎn)的值，由它周?chē)承c(diǎn)的值決定，例如下一時(shí)刻(i,j) 的值取當(dāng)前時(shí)刻它的8鄰點(diǎn)的平均，那么怎么用MapReduce來(lái)實(shí)現(xiàn)。
分析：
首先，讓我們以WordCount為例來(lái)解釋MapReduce是怎么工作的。
原始狀態(tài)下，輸入–Map — Shuffle — Reduce — 輸出
假設(shè)有如下的兩個(gè)文本文件來(lái)運(yùn)行WorkCount程序：
- Hello World Bye World
- Hello Hadoop GoodBye Hadoop
map數(shù)據(jù)輸入
Hadoop針對(duì)文本文件缺省使用LineRecordReader類(lèi)來(lái)實(shí)現(xiàn)讀取，一行一個(gè)key/value對(duì)，key取偏移量，value為行內(nèi)容。
如下是map1的輸入數(shù)據(jù)：
- Key1 Value1
- 0 Hello World Bye World
如下是map2的輸入數(shù)據(jù)：
- Key1 Value1
- 0 Hello Hadoop GoodBye Hadoop
map輸出/combine輸入
如下是map1的輸出結(jié)果
- Key2 Value2
- Hello 1
- World 1
- Bye 1
- World 1
如下是map2的輸出結(jié)果
- Key2 Value2
- Hello 1
- Hadoop 1
- GoodBye 1
- Hadoop 1
combine輸出 Combiner類(lèi)實(shí)現(xiàn)將相同key的值合并起來(lái)，它也是一個(gè)Reducer的實(shí)現(xiàn)。
如下是combine1的輸出
- Key2 Value2
- Hello 1
- World 2
- Bye 1
如下是combine2的輸出
- Key2 Value2
- Hello 1
- Hadoop 2
- GoodBye 1
combiner視業(yè)務(wù)情況來(lái)用，減少M(fèi)AP->REDUCE的數(shù)據(jù)傳輸，提高shuffle速度，就是在map中再做一次reduce操作。combiner使用的合適，可以在滿足業(yè)務(wù)的情況下提升job的速度，如果不合適，則將導(dǎo)致輸出的結(jié)果不正確。
對(duì)于wordcount來(lái)說(shuō)，value就是一個(gè)疊加的數(shù)字，所以map一結(jié)束就可以進(jìn)行reduce的value疊加，而不必要等到所有的map結(jié)束再去進(jìn)行reduce的value疊加。
reduce輸出
Reducer類(lèi)實(shí)現(xiàn)將相同key的值合并起來(lái)。
如下是reduce的輸出
- Key2 Value2
- Hello 2
- World 2
- Bye 1
- Hadoop 2
- GoodBye 1
即實(shí)現(xiàn)了WordCount的處理。
下圖是官方的流程圖：
有了這個(gè)基礎(chǔ)知識(shí)，我們來(lái)看如何用MapReduce來(lái)解決上述問(wèn)題。
以下標(biāo)對(duì)作為map的key，遇到（i，j），生成（i-1，j-1），（i-1，j），etc，然后在reduce時(shí)merge相同的key，并計(jì)算value。
當(dāng)你理解了MapReduce的工作原理，是不是很簡(jiǎn)單？
