专栏首页灯塔大数据每周学点大数据 | No.37字数统计

每周学点大数据 | No.37字数统计

No.37期

字数统计

Mr. 王:我们来看几个 MapReduce 应用的实际例子,这样更有助于你对它的认识。

小可:我也迫不及待地想试试 MapReduce 的应用了。

Mr. 王:先讲一个最基本的应用——字数统计。这个例子与前面的字母计数是非常相似的,只不过这里要统计的是单词数目。现在我们来更具体地说说,它的 Map 和 Reduce 是如何进行设计的。

Mr.王拿出一块白板,在上面写下了一段代码,说:这里有一段代码,它实现的就是字数统计的 Map 和 Reduce,它并不复杂。

可以看出,这个 Map 函数的输入是文档编号和相应的文档; Reduce 函数的输入是文档中出现的某一个单词和其频度统计。在这个算法中, Map 和 Reduce 的执行逻辑其实也是很简单的。

Map 函数将一个文档打开,每遇到一个单词,就发送 < 单词 ,1> 这样的一个元组。也就是说,每当 Map 函数发现了某个单词时,它就报告自己发现的这个单词是什么,同时希望 Reduce 函数在这个单词的计数上加 1。

而 Reduce 函数将整理来自所有 Map 的结果,并将相同的单词对应的这些“ 1”进行累和,输出该单词和统计频度。

你来说说,这个算法的缺陷在哪里?

小可看了看面前的白板,说:我觉得这个 Map 函数太简单了,发现一个单词就传输一个 1出去,这样就会有大量的时间都消耗在了传输这些 1 上面,每有一个单词就要传输一次,效率太差了。

Mr. 王:应怎么改进?

小可:能不能让 Mapper 在内部对某个单词的频度进行一个统计,使其可以存储一些中间结果,而不是急着把它们发送出去呢?

Mr. 王开始擦除白板上的算法,说:我们来看一个改进版本。

小可:这个改进版本多了一个数组 H,可以对单词 t 进行内部统计,在输出结果之前,将相同的单词在这篇文章里出现的次数进行了合并。

原来是出现 100 次单词就要发送 100 条记录,现在只需要发送 1 条记录就可以了,这样的确极大地减小了在网络中传输的数据量。

Mr. 王:这里有一个问题,当我们采用了这个改进版本的 Mapper 时,是不是还需要使用combiner 呢?

小可:我觉得不需要了吧,统计工作已经由 Mapper 做了。

Mr. 王:不对, combine 依然是需要的。我们注意看这个版本 Mapper 的描述,它中间有一句是“ for all term t ∈ doc d”,这意味着它运行时虽然会将来自一个文档的相同词汇及时合并。

但是一个 Mapper 可能会去处理很多个文档,而我们定义的这个 Mapper 是不能将来自多个文档的相同词汇进行合并的,比如在 doc1 中,我们发现单词 t 出现了 100 次,在 doc2 中出现了200 次,这个 Mapper 就会发出 2 条记录。

不难发现,对于一个单词 t 最终还是发出多条记录,当文档非常多时,发出的记录也就非常多,这对于通信来说依然会造成很大的力。

所以我们还要继续改进:

Mr. 王:我们来看看这个最终版本,这里有什么不同呢? Mapper 把数组声明成了一个全局的量, Mapper 在其整个运行过程中,不论它在处理哪一个文档,都能访问到这个数组。

也就是说,在 Mapper 运行的过程中,只要对应的是一个单词,不论它来自哪一个文档,都可以将其加入到单词在数组中的频度记录中去,这就实现了 Mapper 在其处理的所有文档中对单词统计量的合并。

最后,当 close 函数被执行时, Mapper 会将整理好的数据发送出去。

小可:那么这个时候,是不是可以彻底地取消 combiner 了呢?

Mr. 王:是的。此时 combine 操作的所有工作都已经被 Mapper 实现了,能聚集的已经被Mapper 都聚集了。这种设计模式叫作本地聚合,或者叫作 In-Mapper。

这种做法就是希望将combine 操作都集成到 Mapper 中去,它保持了多个 Mapper 调用中的状态。

这样做的好处就是,如果 Mapper 不去做这种 In-Mapper 化处理,而是直接将大量的 <term,1> 输出出去,指望着 combiner 去完成聚合工作,那么每一个 Mapper 就会有大量的数据输出。

可以想象,这个数据量会非常大,是很容易超过内存缓冲区大小的,一旦内存空间被占满,数据就不得不被缓冲到磁盘上,当 combiner 要调用这部分内容时,就要从磁盘上把这部分缓冲数据取出来,这就造成了两次磁盘 I/O。

我们也知道,磁盘 I/O 的速度相比内存读写慢得太多了,这是非常影响系统运行效率的。通过引入这种 In-Mapper 模式,可以有效地将工作转变为内存操作,相比初始的版本效率高了很多。

小可:不过设计一个好的 In-Mapper 也是挺需要设计者功夫的啊。

内容来源:灯塔大数据

本文分享自微信公众号 - 灯塔大数据(DTbigdata)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-05-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 图解|一图读懂《检察大数据行动指南(2017—2020年)

    近年来,检察机关卯足了劲儿深挖"大数据"富矿,打造数据化、科学化、智能化的"智慧检务"。"十三五"时期,检察机关将继续稳步推进,拿出最强阵容来部署大数据工作。...

    灯塔大数据
  • 每周学点大数据 | No.46 MapReduce 平台的局限

    No.46期 MapReduce 平台的局限 Mr. 王:前面我们讲了许多基于MapReduce 的并行算法,现在我们讨论一个新话题——超越MapRedu...

    灯塔大数据
  • 技术 | Python从零开始系列连载(四)

    导读 上一期学习了Python的基本运算和表达式的一部分,相信大家都已经熟悉啦,我们这一期就来学习Python的基本运算和表达式剩下的部分吧! Python的基...

    灯塔大数据
  • 关于自然语言处理,数据科学家需要了解的 7 项技术

    现代公司要处理大量的数据。这些数据以不同形式出现,包括文档、电子表格、录音、电子邮件、JSON以及更多形式。这类数据最常用的记录方式之一就是通过文本,这类文本通...

    CDA数据分析师
  • 从手机到平板,华为凭啥总能超越苹果?

    京东公布的华为在618期间的数据表明:6月1日-10日,笔记本电脑成交额同比增长60%,平板电脑成交额同比增长270%,路由器成交额同比增长110%。

    刘旷
  • php内存泄漏,内存溢出,垃圾回收

    内存溢出 out of memory,是指程序在申请内存时,没有足够的内存空间供其使用,出现out of memory;比如申请了一个integer,但给它存了...

    程序员养成日记
  • 自然语言处理指南(第3部分)

    在阅读之前,请一定要查看第 1 部分和第 2 部分!

  • “adobe premiere中画面和声音不同步” 解决方法

    之前在segmentfault上过直播课,直播课有录制回播功能;尝试听了下直播课,发现视频太长了,感觉听起来非常花费学员的时间,在回放中其实有一些直播课里面的内...

    汤青松
  • RMAN 提示符下执行SQL语句

           在手动恢复数据库时,有时候需要在SQL*Plus提示符以及操作系统提示符,RMAN提示符下来回切换显得有些繁琐。实际上RMAN为我们提供了命令行下...

    Leshami
  • Python爬虫入门教程 36-100 酷安网全站应用爬虫 scrapy

    2018年就要结束了,还有4天,就要开始写2019年的教程了,没啥感动的,一年就这么过去了,今天要爬取一个网站叫做酷安,是一个应用商店,大家可以尝试从手机APP...

    梦想橡皮擦

扫码关注云+社区

领取腾讯云代金券