`
yunsamzhang
  • 浏览: 70056 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

用hadoop估算圆周率PI(3.1415926)的值

阅读更多
一、hadoop不适合计算密集型的工作

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

但是,前几天,我却发现了在hadoop自带的examples里,竟然有PiEstimator这个例子!!它是怎么做到的??


二、通过扔飞镖也能得出PI的值?

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

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

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

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



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

这样也能算出PI的值?相当强悍吧,呵呵。


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

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

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

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


三、一定要用hadoop吗?

在《通过扔飞镖也能得出PI的值?》一文中,网页中自带了一个Flash,用ActionScript来计算PI的值。

用这种算法来估算PI值,其实是一个统计学的方法。如果要估算正确,首先要保证取样足够多(即投掷次数足够多)。但是如果是单机上运行程序,取太多的样,很容易crash your computer.

所以,这里用hadoop的原因可以在集群上并行运行多个map任务,同时集群上的节点又非常多,这样就能够保证取到足够多的样了!


四、hadoop examples代码解读

上代码:
    public void map(LongWritable offset,
                    LongWritable size,
                    OutputCollector<BooleanWritable, LongWritable> out,
                    Reporter reporter) throws IOException {

      final HaltonSequence haltonsequence = new HaltonSequence(offset.get());
      long numInside = 0L;
      long numOutside = 0L;

      for(long i = 0; i < size.get(); ) {
        //generate points in a unit square
        final double[] point = haltonsequence.nextPoint();
        // 1、point就是取样点,即飞镖投中的部位。这是一个x和y都是0到1的值(Halton sequence保证这一点)。此时的坐标原点在A(见Figure1)。

        //count points inside/outside of the inscribed circle of the square
        final double x = point[0] - 0.5;
        final double y = point[1] - 0.5;
        // 2、横纵坐标各减去0.5以后,我们就可以理解成:将坐标原点从A移到了B(见Figure1)。
        if (x*x + y*y > 0.25) { // 3、根据勾股定理:x*x+y*y > 0.5*0.5(见Figure2),判断这个point是否在圆里。
          numOutside++;
        } else {
          numInside++;
        }

        //report status
        i++;
        if (i % 1000 == 0) {
          reporter.setStatus("Generated " + i + " samples.");
        }
      }

      //output map results
      out.collect(new BooleanWritable(true), new LongWritable(numInside));
      out.collect(new BooleanWritable(false), new LongWritable(numOutside));
    }


还需要说明的是:
1、mapper的输出:
//output map results
      out.collect(new BooleanWritable(true), new LongWritable(numInside));	// 投中的次数
      out.collect(new BooleanWritable(false), new LongWritable(numOutside));

2、reducer,简单的对numInside进行sum操作。

3、最后,PI的值等于:

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


总共投掷的次数 = mapper的数目*每个mapper投掷的次数

PI = 4 * 投中的次数 / 总共投掷的次数


五、小结

hadoop(mapreduce)确实不适合做计算密集型的工作,尤其是下一步计算依赖于上一步的计算结果的时候。

但是hadoop的examples中的计算PI的方法并不属于这一类,而是采用大量采样的统计学方法,还是属于数据密集型的工作。

回到本文开头提到的PPT中,里面写的是“hadoop不适合计算PI小数点后1000000位小数”,而hadoop的example只是“估算PI的值”,二者并不是同一项任务。



附:运行hadoop估算PI的命令

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

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

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

我运行的结果:
Job Finished in 7492.442 seconds
Estimated value of Pi is 3.14159266720000000000


*** THE END ***

  • 大小: 68.4 KB
分享到:
评论
5 楼 hpuyancy 2015-08-05  
你好,如果使用Hadoop读取一个小文件(10KB),文件中有N行的数据,每一行数据都需要和其余N-1行数据进行计算,就是会产生N*N次计算,该如何将N*N次计算分配到Map中呢?由于一个Map只能读取一个文件?
4 楼 chenyulong1 2010-07-13  
这个算法非常棒,这世上最美的终不是女人,而是数学呐。
3 楼 conservatism 2010-07-13  
用hadoop+蒙特卡罗算过pi,效率并不高
2 楼 yunsamzhang 2010-07-12  
mikewang 写道
这个实际上叫做蒙特卡洛算法

我们取一个单位的正方形(1×1) 里面做一个内切圆(单位圆)

则 单位正方形面积 : 内切单位圆面积 = 单位正方形内的飞镖数 : 内切单位圆内的飞镖数

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

注意

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



总结的非常棒!谢谢你的补充。
1 楼 mikewang 2010-07-12  
这个实际上叫做蒙特卡洛算法

我们取一个单位的正方形(1×1) 里面做一个内切圆(单位圆)

则 单位正方形面积 : 内切单位圆面积 = 单位正方形内的飞镖数 : 内切单位圆内的飞镖数

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

注意

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

相关推荐

    hadoop-lzo-0.4.20.jar

    hadoop2 lzo 文件 ,编译好的64位 hadoop-lzo-0.4.20.jar 文件 ,在mac 系统下编译的,用法:解压后把hadoop-lzo-0.4.20.jar 放到你的hadoop 安装路径下的lib 下,把里面lib/Mac_OS_X-x86_64-64 下的所有文件 拷到 ...

    hadoop-2.7.1.tar.gz.zip

    在Linux或Mac系统中,通常会先使用`unzip`命令解压最外层的zip文件,然后用`tar -zxvf`命令解压内层的tar.gz文件。Windows用户可以使用类似WinRAR或7-Zip的工具来完成解压过程。 解压后,你将获得Hadoop的源代码、...

    Apache Hadoop (hadoop-3.3.3.tar.gz)

    Apache Hadoop 软件库是一个框架,它允许使用简单的编程模型跨计算机集群分布式处理大型数据集。它旨在从单个服务器扩展到数千台机器,每台机器都提供本地计算和存储。库本身不是依靠硬件来提供高可用性,而是设计...

    Hadoop下载 hadoop-3.3.3.tar.gz

    Hadoop是一个由Apache基金会所开发的分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进 Hadoop是一个由Apache基金会所开发的分布式系统基础架构。用户可以在不...

    hadoop-2.6.0-hadoop.dll-winutils.exe

    windows上eclipse运行hadoop程序报NullPointerException错 log4j:WARN No appenders could be found for logger (org.apache....3,创建环境变量HADOOP_HOME,然后把winutils.exe文件拷贝到${HADOOP_HOME}/bin目录下

    hadoop-2.7.3.tar.gz 下载 hadoop tar 包下载

    Hadoop是Apache软件基金会开发的一个开源分布式计算框架,它允许在廉价硬件上处理大量数据,是大数据处理领域的重要工具。2.7.3是Hadoop的一个稳定版本,提供了可靠的分布式存储系统HDFS(Hadoop Distributed File ...

    Hadoop下载 hadoop-2.9.2.tar.gz

    Hadoop 是一种分析和处理大数据的软件平台,是一个用 Java 语言实现的 Apache 的开源软件框架,在大量计算机组成的集群中实现了对海量数据的分布式计算。 Hadoop 采用 MapReduce 分布式计算框架,根据 GFS 原理开发...

    hadoop-2.6.0.tar.gz.mds

    hadoop-2.6.0.tar.gz.mds,hadoop的安装包,版本为2.6.0,适应操作系统为Linux。

    hadoop-3.3.1.tar.gz

    - **解压文件**:使用tar命令解压“hadoop-3.3.1.tar.gz”,例如:`tar -xzf hadoop-3.3.1.tar.gz`。 - **配置环境变量**:将Hadoop安装路径添加到PATH环境变量中。 - **配置Hadoop**:编辑`etc/hadoop/hadoop-...

    hadoop-3.1.4.tar.zip

    Hadoop是Apache软件基金会开发的一个开源分布式计算框架,它的核心设计是处理和存储大量数据,尤其适合大数据分析。Hadoop 3.1.4是该框架的一个稳定版本,提供了许多性能优化和新特性。这个压缩文件"hadoop-3.1.4....

    hadoop-3.1.3-src.tar.gz

    Hadoop是Apache软件基金会开发的一个开源分布式计算框架,它的核心设计思想是“大规模数据分布式处理”。这个名为“hadoop-3.1.3-src.tar.gz”的压缩包包含了Hadoop 3.1.3版本的源代码,对于开发者来说,这是一个...

    hadoop-3.1.4.tar.gz

    《Hadoop 3.1.4安装与使用详解》 Hadoop是Apache软件基金会开发的开源分布式计算框架,主要用于处理和存储大规模数据。Hadoop 3.1.4是其一个重要版本,它在Hadoop 3.x系列中提供了许多增强功能和性能优化,包括对大...

    hadoop2.7.7对应的hadoop.dll,winutils.exe

    在Hadoop生态系统中,Hadoop 2.7.7是一个重要的版本,它为大数据处理提供了稳定性和性能优化。Hadoop通常被用作Linux环境下的分布式计算框架,但有时开发者或学习者在Windows环境下也需要进行Hadoop相关的开发和测试...

    hadoop-3.1.3.tar.gz

    下载后,使用`tar -zxvf hadoop-3.1.3.tar.gz`命令进行解压,解压后的目录结构包含Hadoop的各种组件和配置文件。 三、配置Hadoop环境 为了方便使用Hadoop,我们需要设置环境变量。在用户的.bashrc文件中添加以下...

    hadoop-3.2.2.tar.gz

    3. **配置环境**:设置JAVA_HOME环境变量指向已安装的JDK路径,因为Hadoop是用Java编写的,需要Java环境支持。 4. **配置Hadoop**:使用`./configure`脚本来配置Hadoop,可以指定安装目录、编译选项等。此过程会...

    hadoop2lib.tar.gz

    例如,使用Hadoop的InputFormat和OutputFormat接口,开发者可以定义自定义的数据输入和输出格式。同时,Hadoop的Configuration类使得配置参数变得简单,而FileSystem API则允许开发者操作HDFS上的文件。 在实际开发...

    hadoop-2.7.1.tar.gz

    3. **Hadoop安装与配置**: - 解压`hadoop-2.7.1.tar.gz`后,用户需要配置环境变量,包括`HADOOP_HOME`,并将`bin`目录添加到`PATH`中。 - 配置`etc/hadoop/core-site.xml`以指定HDFS的默认名称节点和临时目录。 ...

    hadoop的hadoop.dll和winutils.exe下载

    3. 安装过程中,确保正确配置Hadoop的环境变量,包括`HADOOP_HOME`、`HADOOP_COMMON_HOME`、`HADOOP_HDFS_HOME`等,以便系统能够找到必要的库文件和可执行文件。 在Windows上运行Hadoop可能会比在Linux上复杂一些,...

Global site tag (gtag.js) - Google Analytics