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