关于在mapreduce框架上求近似Pi的值,hadoop源码包的example中源代码,在这里只是简单写写学习笔记
首先说下大概思路:
这个图大家在网上肯定见都见过
正方形的面积 As = (2r)*(2r)也就是 4r*r. 内切圆形的面积 Ac = pi * r*r.
pi = Ac / r*r
As = 4r*r
r*r= As / 4
pi = 4 * Ac / As
所以最后求pi 的近似值就可以通过求圆的面积与正方形的面积的比值即可,
hadoop中example的实现的思想就是 在整个正方形的内取随机点,然后计算出在内切圆内的点的个数比除以总体的随机点的个数。这个值在乘以4即可近似求出PI的近似值 ,
因为是随机点 有一定的概率行,所以是求近似值。
概算法一个重要难点就是这个随机点的如何生成,采用java自带的Random函数显然不合适,mapreduce采用的是Halton随机点生成算法,他就是才单位正方形内(1,1)内生若干个数据组,该算法需要一个基础值
比如,以2作为基数,那么得到的序列就是将(0,1)区段反复二分:
1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, 9/16
实现的伪代码如下:
FUNCTION (index, base)
BEGIN
result = 0;
f = 1 / base;
i = index;
WHILE (i > 0)
BEGIN
result = result + f * (i % base);
i = FLOOR(i / base);
f = f / base;
END
RETURN result;
END
这样就得到一组随机的点,
接下来mapreduce要做的工作就是分布这些生成的随机点到各个map任务中区,
而map要做的就是计算这些点实在圆内还是圆外:
final double x = point[0] - 0.5;
final double y = point[1] - 0.5;
if (x*x + y*y > 0.25) {
numOutside++;
} else {
numInside++;
}
(0.5,0.5)就是圆心的坐标,然后计算随机点到圆心点 两点之间的距离 与半径进行比较,最后计数圆内点的个数
然后用一个reduce任务对各个map产生的计数进行全局的统计,并作最后的计算。
分享到:
相关推荐
MapReduce求取行平均值 MapReduce小实例 数据有经过处理已经添加行号的 也有未添加的 行平均值的四种求法
Mincemeat-node 是使用Node.js实现的极简MapReduce框架,可以快速的部署投入工作,免去Hadoop繁琐的配置,享受随心大数据。Mincemeatpy实现的是一种非常简单的MapReduce模型,仅仅实现了任务的分布计算,并没有类似...
MapReduce求行平均值--标准差--迭代器处理--MapReduce案例
大数据,Spark,MapReduce 本资料共包含以下附件: MALK:一种高效处理大规模键值的MapReduce框架.pdf
MapReduce求平均值示例程序,并且程序里利用了logger类,可以将调试信息输出到mapreduce的日志,可以根据输出信息了解运行机制
为MapReduce框架对电话号码的上行流量和下行流量及总流量进行统计的模板数据
人工智能-hadoop
一次很好的mapreduce框架学习。复习了框架大部分组件,代码都是一个一个敲上去的,借鉴了视频中老师的讲解,只包含了7个代码中关键的java文件,其他包都需要自己导入。
针对海量数据背景下K-means聚类结果不稳定和收敛速度较慢的问题,提出了基于MapReduce框架下的K-means改进算法。首先,为了能获得K-means聚类的初始簇数,利用凝聚层次聚类法对数据集进行聚类,并用轮廓系数对聚类...
Hadoop中HDFS和MapReduce框架介绍pdf
基于Hadoop的MapReduce框架研究报告,开源云计算的一个基础框架
Hadoop正是基于谷歌的mapreduce-osdi04和gfs-sosp2003这两篇论文构建起来的。
一个实用的MapReduce框架
基于Hadoop的MapReduce框架研究报告.ppt
基于MapReduce框架的SQL引擎设计.pdf
利用k_means聚类算法的MapReduce并行化实现,为学习hadoop的同学提供参考
使用和学习过老Hadoop框架(0.20.0及之前版本)的同仁应该很熟悉如下的原MapReduce框架图:图1.Hadoop原MapReduce架构从上图中可以清楚的看出原MapReduce程序的流程及设计思路:可以看得出原来的map-reduce架构是...
基于MapReduce框架下的数据挖掘方法研究.pdf
Map-Reduce框架这是用Java实现的简化MapReduce框架。 该框架包含两种类型的节点: 一位大师主节点将任务分配给工作人员并在工作人员之间进行协调。 主服务器还具有一个状态页面,该页面显示当前在线的工作人员列表...
基于MapReduce框架一种文本挖掘算法的设计与实现