原文:
http://stevekrenzel.com/finding-friends-with-mapreduce
关于MapReduce的运用,最近阅读到的一篇文章,写的很不错,搬过来分享下。
MapReduce是一种编程模型,用于大数据(>1TB)的并行运算。对于原理可以简化为两个步骤:map(映射)方法和reduce(归约)方法。Map方法是将一个值输出为key-value的对应。比如统计一篇英文文章中某个长度有几个单词。具体思路是输入一个目标句子,那么输出就可以是以目标字符串中的一个单词长度为key,单词本身为value的map。这个map的方法没什么其它的依赖,只需要输入一个单词就可以完成map方法的输出。这样可以进行并行运算。具体如下:
3 : the
3 : and
3 : you
4 : then
4 : what
4 : when
5 : steve
5 : where
8 : savannah
8 : research
分组整理后:
3 : [the, and, you]
4 : [then, what, when]
5 : [steve, where]
8 : [savannah, research]
每行数据会进行reduce方法,即一个特定长度的key会对应一个value的list。再往深入点,我们可能会计算每个特定长度的词有多少个,于是reduce方法将会整理出如下对应关系:
3:3
4:3
5:2
8:2
综上所述就是map方法和reduce方法都可以分N个机器进行并行运算,这样在时间上的优势是很大的。经过以上步骤就分析出某个长度的词汇在文章中出现的次数了。
另一个关于MapReduce的类似例子是统计词语在文章中出现的次数。
首先要做的就是将文章中的词汇逐个转成map,key是这个词汇本身,value默认为1。然后进行分组整理,此时key还是这个词语本身,value是次数为1的集合(list),最后的reduce要做的就是合计value,即将所有的1相加,最终的输出结果就是词语-次数的map。
看起来好像很容易,以上的例子就是MapReduce的“Hello World”。来说说现实生活中的运用MapReduce的例子吧:
社交平台(例如Facebook)会有一个好友的列表(假设这个朋友关系是双向的,即A是B的好友,那么B也必须是A的好友)。平台的优势是大公司不差钱存储空间多,平台每天有几百万次的点击量,所以他们决定提前计算,从而减少请求的时间。比如你和Joe有230个共同好友,当Joe访问你的主页时,他可以看到一个共同好友的列表,这个列表可能不经常改动,所以如果每次访问都实时统计一遍实属浪费资源和时间(当然另一种解决方案是Cache)。这时候可以用mapreduce每天计算朋友之间的共同朋友,并保存下来,这样每次请求的时候就特别方法,虽然占用空间,但便宜。
Assume the friends are stored as Person->[List of Friends], our friends list is then:
假投朋友关系存储是按key-value:某个人->[朋友集合],如下:
A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D
每一行都是一个mapper,但是上面的键值是一个朋友的List,而我们要的是两个好友之间的共同朋友,所以基于这个需求,需要将值重新拆成单个key-value的配对(当前这个人与他朋友之间的两两配对),这样就可以变成某个人和特定的朋友之间的关系了。这个健值是有顺序的(便于双向访问的时候用同一个键值,即A访问B的时候是(A B),B访问A的时候也是(A B)),按这个逻辑来重新组合,就变成了如下结果:
For map(A -> B C D) :
(A B) -> B C D:具体说下意思:(A B) -> B C D的意思是A和B是共同好朋友->A的所有的好朋友,下同。
(A C) -> B C D
(A D) -> B C D
For map(B -> A C D E) : (注意键值是有顺序的,即A在B的前面)
(A B) -> A C D E
(B C) -> A C D E
(B D) -> A C D E
(B E) -> A C D E
For map(C -> A B D E) :
(A C) -> A B D E
(B C) -> A B D E
(C D) -> A B D E
(C E) -> A B D E
For map(D -> A B C E) :
(A D) -> A B C E
(B D) -> A B C E
(C D) -> A B C E
(D E) -> A B C E
And finally for map(E -> B C D):
(B E) -> B C D
(C E) -> B C D
(D E) -> B C D
在将结果交给reducer进行reduce前,我们先把以上值进行分组(group):
(A B) -> (A C D E) (B C D)
(A C) -> (A B D E) (B C D)
(A D) -> (A B C E) (B C D)
(B C) -> (A B D E) (A C D E)
(B D) -> (A B C E) (A C D E)
(B E) -> (A C D E) (B C D)
(C D) -> (A B C E) (A B D E)
(C E) -> (A B D E) (B C D)
(D E) -> (A B C E) (B C D)
再进行reduce,这个reduce方法就是取两个集合中的交集。比如reduce((A B) -> (A C D E) (B C D))将输出(A B) : (C D),这意味着A和B的共同朋友有C和D。
(A B) -> (C D)
(A C) -> (B D)
(A D) -> (B C)
(B C) -> (A D E)
(B D) -> (A C E)
(B E) -> (C D)
(C D) -> (A B E)
(C E) -> (B D)
(D E) -> (B C)
当D访问B的主页时,我们可以迅速的查询键值为(B D)对应的值,即(A C E)。
参考:
维基百科MapReduce主页
https://en.wikipedia.org/wiki/MapReduce
分享到:
相关推荐
对Google第一版的mapreduce相关文献进行的翻译。结合了的知秋的相关文章翻译的,不收费
mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce mapreduce ...
关于mapreduce最早的文章,英文原文和中文翻译!!
社交媒体网络在人们的日常生活中发挥着越来越重要的作用。 社区结构是社交媒体网络的显着特征之一,已经被应用到推荐系统和网络营销等实际应用中。 随着社交媒体规模的Swift扩大和信息量的激增,如何在大数据场景中...
MapReduce中文翻译,MapReduce是一个编程模型、和处理,产生大数据集的相关实现。用户指定一个map函数处理一个key/value对,从而产生中间的key/value对集。然后再指定一个reduce函数合并所有的具有相同中间key的中间...
4 分别在自编 MapReduce 程序 WordCount 运行过程中和运行结束后查看 MapReduce Web 界面。 5. 分别在自编 MapReduce 程序 WordCount 运行过程中和运行结束后练习 MapReduce Shell 常用命令。 。。
简单的在MapReduce中实现两个表的join连接简单的在MapReduce中实现两个表的join连接简单的在MapReduce中实现两个表的join连接
MapReduce发明人关于MapReduce的介绍
MapReduce_Online译文PDF,把英文翻译过来了,大家尽情了解!
运用java实现MapReduce对文本文件进行数据处理与分析
MapReduce中英文,MapReduce是一种编程模型,用于大规模数据集(大于1TB)的并行运算,中文和英文,两个文件。Word
在本实验中,我们将实现一个 MapReduce Java 程序来查找每对用户的共同朋友。 比如我们这里有五个用户:A、B、C、D、E。他们的好友列表存储为Person:[好友列表],像这样 A: BCDB: ACDEC: ABDED: ABCEE: BCD 所有用户...
对中文进行分词的java代码,分别在map reduce中实现。
在前述数值概要的运用中,加入不同的combiner,测试不同环境下系统的性能,并给出分析、说明。 检查在内存优化模式下系统性能的区别。 (实践二)计算器计数 模式描述、计数器结构及性能分析。 示例:计算每个州的...
图解MapReduce,系统介绍Hadoop MapReduce工作过程原理
google云计算三大论文之MapReduce
MapReduce求取行平均值 MapReduce小实例 数据有经过处理已经添加行号的 也有未添加的 行平均值的四种求法
使用MyEclipse实现MapReduce
MapReduce简单程序示例
但是有一些时候,我们需要在MapReduce程序中使用C语言、C++以及其他的语言,比如项目的开发人员更熟悉Java之外的语言,或者项目已经有部分功能用其他语言实现等。针对这些情况,我们需要研究如何在基于Java的...