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

mapreduce的一些算法设计,优化等(1)

阅读更多

本系列是根据书籍《Data-Intensive Text Processing with MapReduce.pdf》和工作中的一些mapreduce使用做的笔记:

本篇针对《Data-Intensive Text Processing with MapReduce》第三章:

 

1. local aggregation(局部合并)

 

IN-MAPPER COMBINING,也就是说,在map端进行合并。在hadoop的mapreduce过程中,map端在将中间数据传递到reduce端之前,

会先将数据写到本地磁盘。要知道,相对其他操作来说,读写磁盘和网络的延迟会带来较大的性能损耗。因此,尽可能减少

传递到reduce端的数据是能提高性能的。

 

以word count统计为例,增加local aggregation的伪码如下:

 

class Mapper
	method Initialize
		H <- new AssociativeArray
	method Map(docid a; doc d)
		for all term t in doc d do
			H{t} <- H{t} + 1
	method Close
	for all term t in H do
		Emit(term t; count H{t})
 

 

如果是一个完整的mapper的实现,继承自Mapper类,在setup方法中,初始化数据结构,在最后cleanup中输出结果

 

缺点:(1). 这破坏了函数式编程的特性

      (2). 算法不能假定输入数据的顺序,例如,用户的日志顺序,正常情况下,都是按照时间顺序打印的,但是在分布式系统上,

你不能假定你获得的输入顺序也是这样的(这个是个通用的原理,例如在写hive的udf或者udaf统计相关数据时,若要记录状态时,

也要记住这一点);

      (3). in-mapper combining需要内存足够大,能够容纳一个map任务的所有数据;其实一旦遇到内存问题后,也存在通用的解决

方案,可以使用block或者计数器的方式,block的意思是,使用内存进行统计,超过一个block的大小先将数据flush;计数器的意思

是,放入内存的对象可以设置一个阈值,超过这个值,则执行flush动作。不管是block还是计数器的方式,都要要预估一下。

 

 

2.对(pairs)与带(stripes)

 

以nlp中的词语共现作为例子,例如w12表示词语w1和词语w2共同出现测次数。共现矩阵的空间是O(n^2),其中n是单词的数量,从给定的文档

中统计结果

 

(1)使用pairs算法,伪码:

 

class Mapper
	method Map(docid a; doc d)
		for all term w in doc d do
			for all term u in Neighbors(w) do
				Emit(pair (w; u); count 1) // 输出每次共现的结果
class Reducer
	method Reduce(pair p; counts [c1; c2; : : :])
		s<-0
		for all count c in counts [c1; c2; : : :] do
			s <-  s + c // 共现次数累加
		Emit(pair p; count s)
 

 

(2)使用stripes算法

 

class Mapper
	method Map(docid a; doc d)
		for all term w in doc d do
			H <- new AssociativeArray
			for all term u in Neighbors(w) do
				H{u} <-  H{u} + 1 // 计算本文档中共现词的次数
			Emit(Term w; Stripe H)
class Reducer
	method Reduce(term w; stripes [H1;H2;H3; : : :])
		Hf <- new AssociativeArray
		for all stripe H in stripes [H1;H2;H3; : : :] do
			Sum(Hf;H) // 累积每个文档里同一个词对应的共现
		Emit(term w; stripe Hf)
 

 

两个算法对区别在于,使用的key,value不同。简单来说,pair是一个词与另一个词共现就输出一个key-value,但是stripe输出的key-value的key是本词,而value是所有与他共现的词

一些结论:

(1)pair的输出产生更多的中间数据,排序时间也多;

(2)stripe方式的value则是序列化和反序列化需要耗时相对较多,同时value值很大的时候,可能出现oom现象,的那是pair算法则不会有这个问题

(3)两者都可以使用local aggregation的方式优化

 

(4)根据实际测试,stripe算法的性能较好

 

分享到:
评论

相关推荐

    基于MapReduce实现决策树算法

    6. 决策树算法在MapReduce中的实现细节:在基于MapReduce实现决策树算法中,需要对决策树算法的实现细节进行详细的设计和实现,例如对树的节点进行实现、对决策树的分裂和叶节点的计算等。 7. MapReduce框架在决策...

    基于MapReduce的商品推荐算法.zip

    在Hadoop生态系统中,我们可以通过Apache Mahout或者Spark MLlib等库实现基于MapReduce的推荐算法。Mahout提供了丰富的推荐算法实现,包括基于用户和物品的协同过滤,而Spark的并行计算能力则使得实时推荐成为可能。...

    基于MapReduce分布式连接算法优化技术研究.pdf

    综上所述,文件内容展示了MapReduce分布式连接算法的相关理论和技术优势,以及并行计算技术、QR树索引、集群技术的重要性,它们在分布式系统中的应用和优化对于解决大规模数据集的并行计算问题提供了实际的参考和...

    MapReduce实现矩阵相乘算法

    - **优化策略**:可以通过调整MapReduce的配置参数,如减少shuffle的数据传输量,提高并行度,优化磁盘I/O等,来提升计算效率。 最后,`AlgorithmProject`可能是该项目的源代码或者文档,里面可能包含了具体的实现...

    基于mapreduce的并行算法的设计 课件

    基于MapReduce的并行算法设计是大数据处理领域的一个核心课题。MapReduce是一种由Google提出的大规模数据处理模型,它将计算任务分解为两个阶段:Map和Reduce。Map阶段将输入数据映射成一系列中间键值对;Reduce阶段...

    MapReduce 设计模式

    1. MapReduce设计模式:涉及MapReduce编程模型的多种使用场景和应用,旨在为开发者提供各种数据处理问题的解决方案。 2. MapReduce和Hadoop:介绍了MapReduce的历史及其与Hadoop的关系。Hadoop是一个开源框架,支持...

    基于哈希技术与MapReduce的大数据集K-近邻算法实现代码

    哈希技术是一种数据结构和算法设计方法,它通过哈希函数将任意大小的数据映射到固定长度的哈希值。在大数据场景下,哈希技术常用于快速查找、去重和分布式存储。哈希碰撞(两个不同的输入得到相同的哈希值)是哈希表...

    用MapReduce实现KMeans算法

    总之,用MapReduce实现KMeans算法是一项挑战,但通过合理的设计和优化,可以在大规模数据集上有效地执行聚类任务。实际应用中,应根据数据规模、硬件资源以及特定需求,灵活调整算法参数和实现策略,以达到最佳性能...

    MapReduce下的Dijkstra并行算法研究.pdf

    为了解决这个问题,可以引入Combiner来减少数据通信量,或者采用更复杂的并行算法设计,比如基于内存的分布式数据结构(如分布式堆或布隆过滤器)来加速查找和更新过程。 此外,为了优化性能,可以考虑以下几个方面...

    云计算之mapreduce算法

    学习MapReduce不仅需要理解其基本概念,还要掌握如何设计和优化Map和Reduce函数,以及如何处理数据分片和分区策略。通过深入学习和实践,可以更好地利用云计算平台提供的MapReduce服务,有效处理和分析大规模数据。

    大数据挖掘中的MapReduce并行聚类优化算法研究.pdf

    在大数据环境下,为了进一步提高聚类效率,研究者将该优化算法在Hadoop的MapReduce框架下进行了并行化设计。Hadoop是一个由Apache基金会开发的开源分布式存储和计算平台,它允许开发者通过MapReduce模型并行处理大量...

    Hadoop课程设计-基于Java和mapreduce实现的贝叶斯文本分类器设计

    在本Hadoop课程设计中,我们将探讨如何使用Java编程语言和MapReduce框架来实现一个贝叶斯文本分类器。这个项目旨在让学生理解大数据处理的基本原理,以及如何利用Hadoop生态系统来解决实际问题,特别是文本分类任务...

    基于MapReduce框架一种文本挖掘算法的设计与实现

    这主要得益于MapReduce框架的并行处理能力和算法设计的优化策略。通过对比不同规模数据集的处理时间,可以看出算法的效率随数据量的增加而保持稳定,验证了其在实际应用中的可行性与优势。 #### 结论与展望 综上所...

    天津工业大学《算法设计与分析》期末复习题(含答案).pdf

    - 大数据处理中的算法优化,如MapReduce框架中的算法设计。 由于给定的文件内容重复且无实际算法内容,以上知识点是根据“算法设计与分析”这一课程的常规内容整理而来。期末复习时,学生应当重点回顾这些知识点,...

    面向MapReduce的大数据分类模型及算法.pdf

    在本文档中,作者柯建波主要探讨了面向MapReduce的大数据分类模型及算法,旨在解决传统大数据分类模型及算法处理数据时间长的问题。 首先,MapReduce是互联网领域中的一种分布式计算模型,它被广泛应用于大规模数据...

    MapReduce算法

    ### MapReduce算法详解 #### 一、概述 MapReduce是一种编程模型,用于处理大规模数据集(通常是TB到PB级别的数据)的并行计算任务。它最初由谷歌工程师Jeff Dean和Sanjay Ghemawat设计实现,并在《MapReduce: ...

    基于Apriori算法的频繁项集Hadoop mapreduce

    然而,需要注意的是,由于MapReduce的通信开销,对于某些特定数据结构和算法,可能有更优化的分布式解决方案,如Spark的FP-Growth等。 总结起来,"基于Apriori算法的频繁项集Hadoop mapreduce"是一个利用大数据处理...

    基于hadoop的apriori算法设计于实现

    本文介绍了一种基于Hadoop平台优化的Apriori算法设计方案。通过利用Hadoop的分布式计算能力和HBase的高效存储特性,有效解决了传统Apriori算法存在的问题。实验结果证明了该方案的有效性和优越性,对于大规模GIS数据...

Global site tag (gtag.js) - Google Analytics