hadoop估算π

一、hadoop不适合计算密集型的工作 

以前看过一个PPT&＃xff1a; Hadoop In 45 Minutes or Less &＃xff0c;记得上面说hadoop不适合计算密集型的工作&＃xff0c;比如计算PI后100000位小数。 

但是&＃xff0c;前几天&＃xff0c;我却发现了在hadoop自带的examples里&＃xff0c;竟然有PiEstimator这个例子&＃xff01;&＃xff01;它是怎么做到的&＃xff1f;&＃xff1f; 


二、通过扔飞镖也能得出PI的值&＃xff1f; 

百度一下&＃xff0c;计算PI的方法还真不少。但在hadoop examples代码中的注释写的是&＃xff1a;是采用 Quasi-Monte Carlo 算法来估算PI的值。 

维基百科中对Quasi-Monte Carlo的描述比较理论&＃xff0c;好多难懂的公式。 

好在google了一把&＃xff0c;找到了斯坦福大学网站上的一篇文章&＃xff1a;《通过扔飞镖也能得出PI的值&＃xff1f;》&＃xff0c;文章很短&＃xff0c;图文并茂&＃xff0c;而且很好理解。 

我这里将那篇文章的重要部分截了个图&＃xff1a; 



对上面的图再稍微解释一下&＃xff1a; 
1、Figure2是Figure1的右上角的部分。 
2、向Figure2中投掷飞镖若干次&＃xff08;一个很大的数目&＃xff09;&＃xff0c;并且每次都仍在不同的点上。 
3、如果投掷的次数非常多&＃xff0c;Figure2将被刺得“千疮百孔”。 
4、这时&＃xff0c;“投掷在圆里的次数”除以“总投掷次数”&＃xff0c;再乘以4&＃xff0c;就是PI的值&＃xff01;&＃xff08;具体的推导过程参见原文&＃xff09; 

这样也能算出PI的值&＃xff1f;相当强悍吧&＃xff0c;呵呵。 


在这个算法中&＃xff0c;很重要的一点是&＃xff1a;如何做到“随机地向Figure2投掷”&＃xff0c;就是说如何做到Figure2上的每个点被投中的概率相等。 

hadoop examples代码中&＃xff0c;使用了Halton sequence保证这一点&＃xff0c;关于Halton sequence&＃xff0c;大家可以参考维基百科。 

我这里再总结一下Halton sequence的作用&＃xff1a; 
在1乘1的正方形中&＃xff0c;产生不重复&＃xff0c;并且均匀的点。每个点的横坐标和纵坐标的值都在0和1之间。 

正是这样&＃xff0c;保证了能够做到“随机地向Figure2投掷”。 

这个实际上叫做蒙特卡洛算法 

我们取一个单位的正方形&＃xff08;1×1&＃xff09; 里面做一个内切圆&＃xff08;单位圆&＃xff09; 
&＃xff09;
则 &＃xff08;单位正方形面积 &＃xff1a; 内切单位圆面积&＃xff09; &＃61; &＃xff08;单位正方形内的飞镖数 : 内切单位圆内的飞镖数 &＃xff09;

通过计算飞镖个数就可以把单位圆面积算出来&＃xff0c; 通过面积&＃xff0c;在把圆周率计算出来。 

注意 

精度和你投掷的飞镖次数成正比

Java代码  

1. public void map(LongWritable offset,  
2.                 LongWritable size,  
3.                 OutputCollector out,  
4.                 Reporter reporter) throws IOException {  
5.   
6.   final HaltonSequence haltonsequence &＃61; new HaltonSequence(offset.get());  
7.   long numInside &＃61; 0L;  
8.   long numOutside &＃61; 0L;  
9.   
10.   for(long i &＃61; 0; i < size.get(); ) {  
11.     //generate points in a unit square  
12.     final double[] point &＃61; haltonsequence.nextPoint();  
13.     // 1、point就是取样点&＃xff0c;即飞镖投中的部位。这是一个x和y都是0到1的值&＃xff08;Halton sequence保证这一点&＃xff09;。此时的坐标原点在A&＃xff08;见Figure1&＃xff09;。  
14.   
15.     //count points inside/outside of the inscribed circle of the square  
16.     final double x &＃61; point[0] - 0.5;  
17.     final double y &＃61; point[1] - 0.5;  
18.     // 2、横纵坐标各减去0.5以后&＃xff0c;我们就可以理解成&＃xff1a;将坐标原点从A移到了B&＃xff08;见Figure1&＃xff09;。  
19.     if (x*x &＃43; y*y > 0.25) { // 3、根据勾股定理&＃xff1a;x*x&＃43;y*y > 0.5*0.5&＃xff08;见Figure2&＃xff09;&＃xff0c;判断这个point是否在圆里。  
20.       numOutside&＃43;&＃43;;  
21.     } else {  
22.       numInside&＃43;&＃43;;  
23.     }  
24.   
25.     //report status  
26.     i&＃43;&＃43;;  
27.     if (i % 1000 &＃61;&＃61; 0) {  
28.       reporter.setStatus("Generated " &＃43; i &＃43; " samples.");  
29.     }  
30.   }  
31.   
32.   //output map results  
33.   out.collect(new BooleanWritable(true), new LongWritable(numInside));  
34.   out.collect(new BooleanWritable(false), new LongWritable(numOutside));  
35. }  

Java代码  

1. //output map results  
2.       out.collect(new BooleanWritable(true), new LongWritable(numInside));  // 投中的次数  
3.       out.collect(new BooleanWritable(false), new LongWritable(numOutside));  

Java代码  

1. //compute estimated value  
2.       return BigDecimal.valueOf(4) // 上面图中公式中的4  
3.       .setScale(20)     //精度  
4.           .multiply(BigDecimal.valueOf(numInside.get()))    // 投中的次数  
5.           .divide(BigDecimal.valueOf(numMaps))          // mapper的数量  
6.           .divide(BigDecimal.valueOf(numPoints));       // 每个mapper投掷多少次  

Java代码  

1. hadoop jar $HADOOP_HOME/hadoop-*-examples.jar pi 100 100000000  

Estimated value of Pi is 3.14159266720000000000 

转载出处&＃xff1a;http://thinkinginhadoop.iteye.com/blog/710847