- 1、本文档共51页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
大数据存储与理-第二讲
Google三大法宝之一:MapReduce 矩阵乘法串行实现 1: for i=1;i=N;i++ 2: for j=1;j=N;j++ 3: 4: 5: 6: for k=1;k=N;k++ C[i][j] += A[i][k]*B[k][j] end for end for 7: end for ? 算法复杂度:O(N3) ? 以1次乘法需要1个时钟周期,计算10亿维度矩阵为 例,使用1G的CPU,需要的计算时间为: t = 10亿×10亿×10亿 / 10亿 = 317年! 是否OK? 想办法解决大规模矩阵相乘问题:我拆 ? Cm = Am ⅹ B ? M台服务器并行计算,时间降低为1/M C A B C1 Cm CM A1 Am AM = ⅹ 想办法解决大规模矩阵相乘问题:我再拆 ? Cm,n = Am ⅹ Bn ? M ⅹM台服务器并行计算,时间降低为1/M2 C A B A1 Am AM = ⅹ C1,1 Cm,1 CM,1 B1 Bn BM 子任务 子任务 子任务 … 拆的本质- 分而治之 ? 分而治之 – Divide and Conquer – 一个大的计算任务分解为若干小计算任务 – 子任务计算结果合并后获得最终结果 计算任务 Divide Conquer 计算结果 MapReduce的来源 ? 编程模型: – 1956年John McCarthy(图灵奖获得者)提出的Lisp语言中的 Map/Reduce方法 – Map输入是一个函数和n个列表,输出是一个新的列表,列表中的元素是 将输入函数作用在n个输入列表中每个对应元素获得的计算结果。 – Reduce输入是一个函数和一个列表,输出是将函数依次作用于列表的每 个元素后获得的计算结果 (map vector #* #(1 2 3 4 5) #(5 4 3 2 1) - #(5 8 9 8 5) (reduce #+ #(5 8 9 8 5)) - 35 Lisp中的Map和Reduce操作 MapReduce原理 Source:sun.fim.uni-passau.de/cl/MapReduceFoundation/ MapReduce机制 ? 主控程序(Master):将Map和Reduce分配到合适的工作机上 ? 工作机(Worker):执行Map或Reduce任务 MapReduce不仅仅是编程模型! ? 让程序员在使用MapReduce时面对以下细节问题? – 大数据如何分割为小数据块? – 如何调度计算任务并分配和调度map和reduce任务节点? – 如何在任务节点间交换数据? – 如何同步任务? – 相互依赖的任务是否执行完成? – 任务节点失效时该如何处理? ? Google的MapReduce是一个完整的计算框架 – 程序员只需要编写少量的程序实现应用层逻辑 程序示例:WordCount #include mapreduce/mapreduce.h class WordCounter : public Mapper { public: virtual void Map(const MapInput input) { const string text = input.value(); const int n = text.size(); for (int i = 0; i n; ) { while ((i n) isspace(text[i])) i++; int start = i; while ((i n) !isspace(text[i])) i++; if (start i) Emit(text.substr(start,i-start),1); }}}; REGISTER_MAPPER(WordCounter); class Adder : public Reducer { virtual void Reduce(ReduceInput* input) { int64 value = 0; while (!input-done()) { value += StringToInt(input-value()); input-NextValue(); } Emit(IntToString(value)); }}; REGISTER_REDUCER(Adder); int main(int argc, char
您可能关注的文档
- 大众汽车品牌展历程.ppt
- 大型主机操作统概述.ppt
- 大型主机操作统1.ppt
- 大型商铺租赁同.doc
- 大型医疗设备训记录.doc
- 大型广告牌方.doc
- 大型市场活动划方案.doc
- 大型小区闭路控系统_修改.doc
- 大型同步电动使用维护说明书.doc
- 大型群聚会活游戏类节目策划.doc
- 中国行业标准 DB/T 100-2024区域性地震安全性评价.pdf
- 《GM/T 0138-2024C-V2X车联网证书策略与认证业务声明框架》.pdf
- GM/T 0138-2024C-V2X车联网证书策略与认证业务声明框架.pdf
- DB/T 100-2024区域性地震安全性评价.pdf
- 中国行业标准 GM/T 0138-2024C-V2X车联网证书策略与认证业务声明框架.pdf
- 校园周边书店阅读氛围对初中生阅读素养提升的影响研究教学研究课题报告.docx
- 初中校园餐饮卫生监管与食品安全教育创新模式研究教学研究课题报告.docx
- 《文化遗产保护与旅游开发平衡机制的法律法规完善研究》教学研究课题报告.docx
- 《农作物病虫害生物防治技术的经济效益与社会影响分析》教学研究课题报告.docx
- 1 剖宫产术后子宫瘢痕憩室治疗中的并发症预防与护理措施教学研究课题报告.docx
最近下载
- 药事管理学药品注册管理课件.ppt VIP
- 《肩袖损伤与肩周炎》课件.ppt VIP
- 2024年重庆市巴蜀中学初升高自主招生语文试卷真题(含答案).docx VIP
- 中介新房培训课件内容.ppt VIP
- 2024年重庆渝中区重庆市巴蜀中学自主招生数学试卷(初升高保送)(详解版).pdf VIP
- 2025年西藏自治区公务员录用考试面试真题试卷(结构化小组)题型分析.docx VIP
- 药品注册管理课件.ppt VIP
- 击剑基础理论知识单选题100道及答案解析.docx VIP
- 《未成年人保护法》课件ppt.pptx VIP
- (高清版)B-T 19363.1-2022 翻译服务 第1部分:笔译服务要求.pdf VIP
文档评论(0)