用hadoop计算PI值，hadoop计算PI值

用hadoop计算PI值，hadoop计算PI值

      摘要：最近研究hadoop的一个例子，计算PI值，本以为hadoop不适合这种密集型的计算，却发现了在hadoop自带的examples里，竟然有PiEstimator这个例子，于是深入研究一下，首先感谢博主http://thinkinginhadoop.iteye.com/blog/710847。

一、计算PI值的方式与原理

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

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

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

      我这里将那篇文章的重要部分截了个图： 



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


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

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

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

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

      有人总结了一下，这个实际上叫做蒙特卡洛算法，我们取一个单位的正方形（1×1） 里面做一个内切圆（单位圆），则 单位正方形面积 ： 内切单位圆面积 = 单位正方形内的飞镖数 : 内切单位圆内的飞镖数 ，通过计算飞镖个数就可以把单位圆面积算出来， 通过面积，在把圆周率计算出来。 
注意 ，精度和你投掷的飞镖次数成正比。

二，运行hadoop估算PI的命令

<span style="white-space:pre">	</span>hadoop jar $HADOOP_HOME/hadoop-*-examples.jar pi 100 100000000

     后面2个数字参数的含义： 
     第1个100指的是要运行100次map任务 
     第2个数字指的是每个map任务，要投掷多少次 

     2个参数的乘积就是总的投掷次数。 

     我运行的结果： 

三，总结

      hadoop的examples中的计算PI的方法属于是采用大量采样的统计学方法，还是属于数据密集型的工作。 

      转载请注明出处： http://www.ming-yue.cn/hadoop-pi/

作单位圆，再作其内接正N边形（N为2的正整数次方）
先计算其内接正N边形周长，可用公式C=N*2R*sin（180/N）计算，其中R为单位圆半径1。
sin（180/N）可以连用N次半角公式计算（因为N为2的正整数次方）
最后用C/2便可得出圆周率的近似值（因为N可以无限大的取值，所以我们可以无限接近圆周率）
 

主要针对大块的数据文件，最好是数据规模上G、T级别的，hadoop把大块数据进行切割并进行分布式存储，对小块数据由于系统开销等原因处理速度并不一定比单个串行程序明显。
此外，hadoop的mapreduce计算模型通过map任务会产生中间结果文件，reduce任务在处理这些中间结果文件形成最终结果文件并输出。由于中间结果文件是存储在各个分布式计算节点本地内存或磁盘上的，如果计算产生的中间结果文件非常巨大，reduce过程需要通过远程过程调用来取得这些中间结果文件，会加大网络传输的开销，则不适合采用hadoop处理。
所以对于是否何时采用hadoop来处理数据，上面讲的两点是必须考虑的问题，对于大规模数据的统计分析，例如求期望方差、或者对海量数据的分布式查询适合用hadoop来做。
呵呵~~不知是否解答清楚了你的问题