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