知识卡片

普通读书笔记卡 · 1776.d

MapReduce能解决与不能解决问题的边界:子问题独立性判据

理解等级:未标注

判断一个问题是否适合用MapReduce解决,重要判据之一是:这个问题能不能被拆解成多个相对独立、彼此不互相依赖的子问题,让这些子问题先各自并行处理完,再汇总得到最终结果。书中给出的可以解决的例子横跨简单到复杂:分布式grep、URL访问频率统计、倒排索引构建这类”天然可切分”的问题自不必说;更复杂的Top K问题(统计最热门的K个查询词)可以拆成两个有依赖关系的MapReduce作业串联完成(先做词频统计,再从各Map任务局部Top K中汇总出全局Top K);K-means聚类通过”计算每个点到当前中心点的最近距离”这一步作为Map、”重新计算各簇均值中心”作为Reduce,靠多轮MapReduce作业迭代逼近收敛;贝叶斯分类的训练阶段甚至由三个各自独立的MapReduce作业组成一条流水线(抽取特征→计算类别先验概率→计算单词条件概率),分类阶段再用一个作业完成预测。但书中特意举出反例来划清边界:直接按前项递推的Fibonacci数值计算不适合用单轮独立Map/Reduce任务高效表达,因为后一步依赖前一步结果;这说明书中所述直接递推实现存在顺序依赖,并不能证明所有重构或分解方法都无法处理这一计算。可迁移启发:评估一个计算问题是否该往MapReduce(或任何批处理并行框架)上靠拢时,先问”这个问题的计算步骤之间是否存在强顺序依赖(后一步必须等前一步的具体结果才能算)”——如果直接实现存在强依赖链,应评估多轮迭代、任务拆分与通信开销,再选择合适的计算模型,不能仅凭原问题名称否定所有并行方案。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《大数据技术体系详解:原理、架构与实践》第10章《批处理引擎MapReduce》之"10.5 MapReduce应用实例"(源文件:_epub-src/OEBPS/text00083.html) - 结论依据:原文说明"MapReduce能够解决的问题有一个共同特点:任务可以被分解为多个子问题,且这些子问题相对独立,彼此之间不会有牵制,待并行处理完这些子问题后,总的问题便被解决……Fibonacci数值计算时,下一个结果需要依赖于前面的计算结果,也就是说,无法将该问题划分成若干个互不相干的子问题,因而不能够用MapReduce解决", 支撑书中对直接递推任务的适用边界分析;不把该例扩展为对所有算法分解的不可行性证明。 - 原始内容:该问题可分解成两个MapReduce作业,分别完成统计词频和找出词频最高的前K个查询词的功能,这两个作业存在依赖关系,第二个作业需要依赖前一个作业的输出结果。