MapReduce主要應用於大規模數據處理，特別是在搜索引擎中各種鏈接的訪問統計，進而影響到頁面關鍵詞排名等等。今天這個例子卻是講的利用MapReduce來對圓周率Pi進行近似計算。考慮下面這張圖：

計算圓周率pi

我們知道，正方形的面積 As = (2r)2 也就是 4r2. 內嵌圓形的面積 Ac = pi * r2. 於是

pi = Ac / r2
As = 4r2
r2 = As / 4
pi = 4 * Ac / As

我們可以通過並行化算法來計算Pi的近似值。當然這其中涉及到一些概率問題。

  1. 在正方形內隨機生成一些點
  2. 有些點隨機生成在圓形內，有些點在圓形外面。統計在圓形內，點的個數
  3. h = 圓形內的點除以正方形內所有的點
  4. PI = 4 * h

下面的偽代碼可以解釋並行的過程：

NUMPOINTS = 100000; // some large number - the bigger, the closer the approximation
 
p = number of WORKERS;
numPerWorker = NUMPOINTS / p;
countCircle = 0;   // one of these for each WORKER
 
// each WORKER does the following:
for (i = 0; i < numPerWorker; i++) {
  generate 2 random numbers that lie inside the square;
  xcoord = first random number; 
  ycoord = second random number;
  if (xcoord, ycoord) lies inside the circle
  countCircle++;
}
 
MASTER:
  receives from WORKERS their countCircle values
  computes PI from these values: PI = 4.0 * countCircle / NUMPOINTS;

假設圓的半徑 r = 1, 則生成一系列隨機數 x, y ∈ [0, 1), 統計點 (x, y) 在圓內 (x2 + y2 < 1)的數量，除以總數，最後將結果乘以4即可。使用MapReduce方法，則為

Map:

pi_map(x,y) = 1,(x2+y2<1)
        或者0,(其他情況)

Reduce:

pi_reduce(a,b) = a + b

輸入N對隨機數(x, y)，h為reduce後得到的結果，那麼Pi的近似值即為 4h/N .

參考鏈接：

http://code.google.com/edu/parallel/mapreduce-tutorial.html#MRExamples