`
yunsamzhang
  • 浏览: 69014 次
  • 性别: 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) 里面做一个内切圆(单位圆)

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

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

注意

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

相关推荐

    asp代码ASP家教信息管理系统(源代码+论文)

    asp代码ASP家教信息管理系统(源代码+论文)本资源系百度网盘分享地址

    基于ssm高校毕业选题管理系统.zip

    基于ssm高校毕业选题管理系统.zip

    基于旷视研究院领先的深度学习算法,提供满足多业务场景的预训练模型.zip

    人工智能毕业设计&课程设计

    tensorflow_model_optimization-0.1.3.dev0-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    tensorflow_model_analysis-0.15.0-py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    粒子群算法.docx 粒子群算法(Particle Swarm Optimization,PSO)是一种优化算法,受到鸟群或鱼

    粒子群算法 粒子群算法(Particle Swarm Optimization,PSO)是一种优化算法,受到鸟群或鱼群等群体行为的启发。该算法通过模拟群体中个体之间的合作和竞争来搜索最优解。粒子群算法通常用于解决连续优化问题。 ### 工作原理: 1. **初始化**:随机生成一群粒子(也称为个体),每个粒子代表搜索空间中的一个解,并随机初始化其位置和速度。 2. **评估**:根据每个粒子的位置,计算其对应的适应度值(目标函数值)。 3. **更新**:根据个体最优和全局最优的情况,更新每个粒子的速度和位置。粒子会根据自己历史最好的位置以及整个群体历史最好的位置进行调整,以期望更好的搜索方向。 4. **迭代**:重复评估和更新步骤,直到满足停止条件(如达到最大迭代次数、目标函数值足够接近最优解等)。 ### 主要参数: - 粒子数量(Population Size):群体中粒子的数量,通常越大越容易找到全局最优解,但计算成本也会增加。 - 惯性权重(Inertia Weight):控制粒子运动的惯性,平衡局部搜索和全局搜索能力。通常随着迭代次数增加而逐渐减小。

    20210327 AI-for-Drug-Discovery-2020.pdf

    20210327 AI-for-Drug-Discovery-2020

    tensorflow_model_optimization-0.1.2-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    Linux创建虚拟机的步骤

    Linux创建虚拟机的步骤

    基于SpringBoot的校园二手书交易管理系统设计源码

    这是一个基于SpringBoot开发的校园二手书交易管理系统,使用Java语言,包含102个文件。主要文件类型包括39个Java源文件、23个HTML文件、10个PNG图片文件、9个XML文件、9个JavaScript文件、4个CSS文件、2个Markdown文档、2个JPG图片文件、1个gitignore文件和1个SVG文件。该项目简洁易用,采用的技术经典,非常适合Java项目入门学习和企业级Java开发熟悉,提供了二手书交易管理、用户认证、数据统计等功能,旨在为校园内的二手书交易提供一个便捷、安全的平台。

    基于SSM的旅游管理系统.zip

    基于SSM的旅游管理系统.zip

    基于ssm框架网络财务设计与实现.zip

    基于ssm框架网络财务设计与实现.zip

    三菱PLC例程源码PLC同变频器通讯程序3

    三菱PLC例程源码PLC同变频器通讯程序3本资源系百度网盘分享地址

    基于ssm+jsp网上茶叶销售平台.zip

    基于ssm+jsp网上茶叶销售平台.zip

    通信专业毕业设计(论文)-企业网通信方案设计

    随着网络和科学技术的飞速发展,网络建设作为信息化建设的基础,也越来越受到企业的重视,网络结构和网络信息安全都是企业信息化建设中需要解决的重要问题。 本设计出于对众宇通讯公司长期稳定发展的考虑,针对公司的现状和发展需求,为公司设计了一个稳定的、相对安全的、可扩展并且可以支撑必要的网络应用的网络结构。在此次设计中,主要的运用到的技术与实现功能有:(1)汇聚交换机上使用DHCP技术,使各个接入层设备可自动获取相应的IP地址,也避免了IP地址的冲突;(2)运用VRRP技术,增强网络的连续性和稳定性,实现多链路备份冗余和网关备份冗余;(3)运用MSTP技术,将不同的VLAN与相应实例捆绑,避免了网络环路和广播风暴的产生;(4)通过防火墙技术,实现了企业内部与外部网络之间的信息交互安全。除此之外,还进行了VLAN的划分,端口安全设置,ACL访问限制,NAT地址转换,使用OSPF协议、静态路由等网络配置。 本论文基于华为ENSP仿真模拟软件,充分考虑到了整个公司网络今后的实用性、安全性以及可扩展性。利用所学的相关知识和网络技术,对众宇通讯公司的网络进行模拟设计。此设计根据三层网络结构来搭建网络拓扑,

    Gromacs中文手册5.0.2.pdf

    Gromacs中文手册5.0.2

    三菱PLC例程源码八层以下货梯通用程序(奥菱达)

    三菱PLC例程源码八层以下货梯通用程序(奥菱达)本资源系百度网盘分享地址

    seg.v

    seg.v

    ftqqzx.zip

    ftqqzx.zip

    基于tensorflow深度学习的中文机器阅读理解-完形填空.zip

    人工智能毕业设计&课程设计

Global site tag (gtag.js) - Google Analytics