这里的日志均为读书时转载的,再次澄清说明~~~

Map/Reduce算法的过程

上一篇 / 下一篇  2009-05-01 16:04:55 / 个人分类:FPGA设计

http://hi.baidu.com/wuxiaoming1733/blog/item/a860bcfbe1f1f92a4e4aeae8.html

Map/Reduce算法的过程是:

1、Partition(划分数据)
把数据划分为1000份,这个过程由Skynet自动完成

2、Map
除了划分数据,还需要把运算该数据的代码也Map到每个运算节点上面去并发执行。这1000个节点各自执行自己的任务,执行完毕以后把执行结果返回

3、Partition
这1000分执行结果需要归并,于是我们再次划分数据,比方说划分为10份,这个过程也是Skynet自动完成的

4、Reduce
把Reduce代码和Reduce数据分发到10个节点执行,每个节点执行完毕返回数据。如果需要再次Reduce可以再次执行。最终Reduce为一个总共的结果。

其 实Map/Reduce算法的原理是很简单的,好了,看看Skynet下面,我们怎么实现呢?其实我们需要编写的代码只有两个方法:一个map方法,告诉 skynet如何执行每份数据,一个reduce方法,告诉skynet如何归并每份数据,所以这个并行算法最终用Skynet来写的话,也非常简单:




Ruby代码 复制代码

  1. class MapreduceTest   
  2.    include SkynetDebugger   
  3.              
  4.   def self.map(datas)   
  5.      results = {}   
  6.      datas.each do |data|   
  7.        results[data] ||= 0   
  8.        results[data] += 1   
  9.     end                    
  10.      [results]         
  11.   end  
  12.      
  13.   def self.reduce(datas)   
  14.      results = {}   
  15.      datas.each do |hashes|   
  16.        hashes.each do |key,value|   
  17.          results[key] ||= 0   
  18.          results[key] += value   
  19.       end  
  20.     end  
  21.      results   
  22.   end  
  23. end  
class MapreduceTest include SkynetDebugger def self.map(datas) results = {} datas.each do |data| results[data] ||= 0 results[data] += 1 end [results] end def self.reduce(datas) results = {} datas.each do |hashes| hashes.each do |key,value| results[key] ||= 0 results[key] += value end end results end end

这个就是一个最简单、但是完整ruby版本的Map/Reduce代码了。我们需要编写一个map方法,告诉skynet去统计每个单词 的出现次数,我们还需要编写一个reduce方法告诉skynet去归并每个map的统计结果。好了,剩下所有的工作都归Skeynet接管了,是不是很 简单!


map/reduce的思想是非常简单的,换句话说,任何语言都能实现。google的map/reduce之所以出名,不是因为这个思想多巧 妙,而是因为它把分布式计算用一种非常简易的方式总结了出来。任何分布式计算,最核心的任务都是:1 任务划分 2 数据归并,如果不能对任务划分,那么用什么分布式框架都是没用的。比如对超大型矩阵的聚类计算,如果算法本身无法划分,那么根本没办法分布式。所以一切涉 及到分布式的问题,划分是最重要的。

TAG: 算法 Map Reduce

 

评分:0

我来说两句

显示全部

:loveliness: :handshake :victory: :funk: :time: :kiss: :call: :hug: :lol :'( :Q :L ;P :$ :P :o :@ :D :( :)

Open Toolbar