Erlang里实现MapReduce

参考： http://weblambdazero.blogspot.com/2008/08/mapreduce-in-erlang.html
MapReduce的主要原理是将一个数据集上的计算分发到许多单独的进程上(map)，然后收集它们的结果(reduce)。

在Erlang里实现MapReduce非常细节也十分简单，例如Erlang的作者Joe Armstrong发表了一段代码来表示MapReduce版本的Erlang标准lists:map/2方法：
pmap.erl

-module(pmap).
-export([pmap/2]).

pmap(F, L) -> 
  S = self(),
  Pids = lists:map(fun(I) -> 
    spawn(fun() -> do_fun(S, F, I) end)
  end, L),
  gather(Pids).

gather([H|T]) ->
  receive
    {H, Result} -> [Result|gather(T)]
  end;
gather([]) ->
  [].

do_fun(Parent, F, I) ->					    
    Parent ! {self(), (catch F(I))}.

pmap的原理也很简单，对List的每项元素的Fun调用都spawn一个process来实际处理，然后再调用gather来收集结果。

如此简洁的代码就实现了基本的MapReduce，不得不服Erlang！

下面是一个fib的示例调用：
fib.erl

-module(fib).
-export([fib/1]).

fib(0) -> 0;
fib(1) -> 1;
fib(N) when N > 1 -> fib(N-1) + fib(N-2).

编译好之后比较一下lists:map/2和pmap:pmap/2的执行效率：

Eshell > L = lists:seq(0,35).
Eshell > lists:map(fun(X) -> fib:fib(X) end, L).
Eshell > pmap:pmap(fun(X) -> fib:fib(X) end, L).

测试结果lists:map执行时间大概4s，pmap:pmap执行时间大概2s，节约了一半的时间，呵呵。

评论

3 楼 lzy.je 2009-02-01  

最近在想把map分布到多台物理机器上，以及更优化的分布到各个核上。

楼主是否了解有同类的lib，学习了解下先。

2 楼 hideto 2008-08-19  

在双核的机器上，在Windows任务管理器里查看CPU使用：
1）调用lists:map时CPU持续50%，CPU波形显示左边的居高不下而右边的一直处于低谷，说明只用了一个核
2）调用pmap:pmap时CPU持续100%，CPU波形显示两个核都居高不下，说明两个核都充分用了，调用时间减少一半

1 楼 hideto 2008-08-18  

节约一半的时间应该是因为我在双核的机器上做的测试，如果有更多核的机器或者分布计算到不同的机器，应该会快更多