如何简单解释 MapReduce算法
原文地址:如何简单解释 MapReduce 算法
在Hackbright做导师期间,我被要求向技术背景有限的学生解释MapReduce算法,于是我想出了一个有趣的例子,用以阐释它是如何工作的。
例子
你想数出一摞扑克牌中有多少黑桃。直观方式是一张一张检查并且数出有多少张是黑桃。
MapReduce方法规则是:
- 给在座的所有玩家中分配这摞牌
- 让每个玩家数自己手中有几张是黑桃,然后把这个数目汇报给你
- 你把所有玩家告诉你的数字加起来,得到最后的结论.
背景
谷歌在2004年发表了可以分析大量数据的MapReduce算法. 每当你听到"大数据"这个词时,它指的是因为太大而让仅仅一台机器难以有效存储或分析的问题。MapReduce通过把计算量分配给不同的计算机群,能够解决大部分和大数据有关的分析问题。Hadoop提供了最受欢迎的利用MapReduce算法来管理大数据的开源方式。先进MapReduce是主流。
所以通常来说,每当你听到“大数据”,那也许意味着Hadoop被用来存储数据,也通常意味着数据的抽取和检索是用的MapReduce。
拆分
MapReduce合并了两种经典函数:
- 映射(Mapping) 对集合里的每个目标应用同一个操作。即,如果你想把表单里每个单元个乘以二,那么把这个函数单独地应用在每个单元格上的操作就属于mapping。
- 化简(Reducing) 遍历集合中的元素来返回一个综合的结果。即,输出表单里一列数字的和这个任务属于reducing。
重新审视上面的列子
重新审视我们原来那个分散纸牌的例子,我们有MapReduce数据分析的基本算法。友情提示:这不是个严谨的例子。在这个例子里,人代表计算机,因为他们同时工作,所以他们是个集群。在大多数实际应用中,我们假设数据已经在每台计算机上了 —— 也就是说把牌分出去并不是MapReduce的一步。(事实上,在计算机集群中如何存储文件是Hadoop的真正核心。)
通过把牌分给多个玩家并且让他们各自数数,你就在并行执行运算,因为每个玩家都在同时计数。这同时把这项工作变成了分布式的,因为多个不同的人在解决同一个问题的过程中并不需要知道他们的邻居在干什么。
通过告诉每个人去数数,你对一项检查每张牌的任务进行了映射。你不会让他们把黑桃牌递给你,而是让他们把你想要的东西化简为一个数字。
另外一个有意思的情况是牌分配得有多均匀。MapReduce假设数据是洗过的(shuffled) — 如果所有黑桃都分到了一个人手上,那他数牌的过程可能比其他人要慢的很多。
如果有足够的人的话,问一些更有趣的问题就相当简单了 —— 比如“一摞牌的平均值(二十一点算法)是什么”。你可以通过合并“所有牌的值的和是什么”以及“我们有多少张牌”这两个问题来得到答案。用这个和初一牌的账单就得到了平均值。
结论
MapReduce算法的机制要远比这复杂得多,但是主体思想是一致的 —— 通过分散计算来分析大量数据。无论是Facebook、NASA,还是小创业公司,MapReduce都是目前分析互联网级别数据的主流方法。有趣的是,MapReduce在多于10PB数据时趋向于变慢,所以谷歌在他们今年的IO大会上报告称MapReduce已经不够他们用了。
最新文章
- sublime text 3 配置php开发环境
- iOS 学习 - 17.Socket
- 为什么数据库有时候不能定位阻塞(Blocker)源头的SQL语句
- SQL--存储过程
- Servlet/JSP-02 Servlet相关类
- JMeter之JDBC接口测试
- nutch简介
- 专注于提高“人肉测试”效率,Bugtags已完成600万元天使轮融资
- Python核心编程--学习笔记--7--字典和集合
- mysql 服务器ip连接统计
- 用C++试着完成Python简明教程后面的练习
- mac上安装redis
- JAVA List<;T>; 如何初始化
- vuex 使用文档
- String(Java版本)
- [BZOJ1814]Formula 1
- 【Linux高级驱动】linux设备驱动模型之平台设备驱动机制
- Java 9 模块化(Modularity)
- Es6 类class的关键 super、static、constructor、new.target
- honeyd蜜罐配置和web监听脚本
热门文章
- 洛谷 P4556 [Vani有约会]雨天的尾巴 解题报告
- LruCache:从网络加载图片缓存实例
- [nginx]proxy_pass&;rewrite知识点
- c++模板类编译错误
- C++派生类继承的理解
- 清除windows系统垃圾文件简易脚本(bat)
- Kafka消息delivery可靠性保证(Message Delivery Semantics)
- mysql Innodb索引
- 数学:BSGS
- 2015/9/17 Python基础(13):函数