3
\$\begingroup\$

I'm doing a comparison of Erlang, Haskell, Elixir and ES6, and I'm less farmiliar with Erlang and Elixir, but I want to represent all of these languages fairly, so is this good Erlang code?

-module(mapreduce).
-export([map_reduce/1]).

add_to_key(KV, Sum) -> {Key, Value} = KV,
                       Tmp = proplists:get_value(Key, Sum, 0),
                       Newlist = proplists:delete(Key, Sum),
                       lists:append([{Key, Value + Tmp}], Newlist).

map_reduce(Pl) -> lists:foldl(fun add_to_key/2, [], Pl).

By the way, if you guys want to see, here's the Haskell version:

module MapReduce where
import qualified Data.Map as M

mapReduce :: [(String, Int)] -> [(String, Int)]
mapReduce = foldl addToKey []
    where addToKey hl (k, v) = M.toList . M.insertWith (+) k v $ M.fromList hl
\$\endgroup\$
0

3 Answers 3

2
\$\begingroup\$

I'd say the Haskell is slightly strange in that you're converting a Map back and forth to a list. Why not just keep it as a Map until the end? Otherwise, you're losing any asymptotic advantage a Map gives you.

module MapReduce where
import qualified Data.Map as M

mapReduce :: [(String, Int)] -> [(String, Int)]
mapReduce = M.toList . foldl addToKey M.empty
    where addToKey hl (k, v) = M.insertWith (+) k v hl

Your Erlang isn't really equivalent to your Haskell, as you're using a straight list (with \$O(n)\$ lookup) rather than a dictionary which has \$O(\log n)\$ lookup.

Switching to use an Erlang dictionary can fix that though, as well as simplifying the code:

-module(mapreduce).
-export([map_reduce/1]).

add_to_key({Key, Value}, Sums) ->
  dict:update(Key, fun (Old) -> Old + Value end, Value, Sums).

map_reduce(Pl) ->
  dict:to_list(lists:foldl(fun add_to_key/2, dict:new(), Pl)).
\$\endgroup\$
2
\$\begingroup\$

There are several aspect to your question.

Speaking about the language, but keeping the same algorithm, you will find more usage of pattern matching and high level function, like:

map_reduce(Pl) -> 
    Add_to_key = fun ({Key, Value}, Sum) ->
        % KV tuple is useless, you can decompose it in the function parameter
        Tmp = proplists:get_value(Key, Sum, 0),
        % do not create a list that will be destroyed immediately in the append function,
        % directly use the list constructor to prepend a single term
        [{Key, Value + Tmp} | proplists:delete(Key, Sum)]
    end,
    lists:foldl(Add_to_key, [], Pl).

But, when manipulating lists, it is important to avoid useless copy and "scanning", for long lists it can be really time consuming. In your code, for each term of the input list, you traverse the accumulator list Sum twice (get_value and delete) and make a copy of it. I wrote a small module to compare the execution time of 4 solution (yours, my proposal specialized for sum, my original solution with a generic reduce function, Hynek solution using an intermediate map). here is the code:

-module (mapreduce).

-export ([test/1,mr1/1,mr2/1,mr2/2,mr3/1]).

test(N) ->
    Red = fun(A,B) -> A+B end,
    L = randomkv(N),
    {T1,R1} = timer:tc(?MODULE,mr1,[L]),
    {T2,R2} = timer:tc(?MODULE,mr2,[L]),
    {T2_1,R2} = timer:tc(?MODULE,mr2,[L,Red]),
    {T3,R3} = timer:tc(?MODULE,mr3,[L]),
    R = lists:sort(R1),
    R = lists:sort(R2),
    R = lists:sort(R3),
    {T1,T2,T2_1,T3}.

add_to_key(KV, Sum) -> {Key, Value} = KV,
                       Tmp = proplists:get_value(Key, Sum, 0),
                       Newlist = proplists:delete(Key, Sum),
                       lists:append([{Key, Value + Tmp}], Newlist).

mr1(Pl) -> lists:foldl(fun add_to_key/2, [], Pl).

red([],L,_)-> L;
red([{K,V}|T],[{K,V1}|T1],Func) -> red(T,[{K,Func(V,V1)}|T1],Func);
red([{K,V}|T],L,Func) -> red(T,[{K,V}|L],Func).

mr2 (L,Func) -> red(lists:sort(L),[],Func).

red([],L)-> L;
red([{K,V}|T],[{K,V1}|T1]) -> red(T,[{K,V+V1}|T1]);
red([{K,V}|T],L) -> red(T,[{K,V}|L]).

mr2 (L) -> red(lists:sort(L),[]).


mr3(L) ->
    F = fun({K, V}, M) ->
            maps:put(K, V + maps:get(K, M, 0), M)
        end,
    maps:to_list(lists:foldl(F, #{}, L)).

randomkv(N) ->
    random:seed(erlang:now()),
    [{random:uniform(N div 5),random:uniform(N * 5)} || _X <- lists:seq(1,N)].

some results on my windows PC (using erlang OTP 18):

2> mapreduce:test(1000).
{15000,0,0,0}
3> mapreduce:test(10000). 
{983000,15000,0,0}
4> mapreduce:test(10000).
{952000,0,16000,15000}
5> mapreduce:test(100000).
{114349000,93000,110000,62000}
6> mapreduce:test(200000).
{479311724,218998,248997,156000}
7> mapreduce:test(400000).
{1850890408,577000,483000,344000}

You can see that the last 3 solutions are equivalent (with an advantage to intermediate map from hynek) but the one using proplists library is extremely slow, and almost not usable for lists bigger than 10000 terms (more than 1s), and it takes half an hour for 400000 terms when the other solutions need around half a second (I did the test for 10 000 000 {na,21231020,18533018,13494012} ).

Last remark, it is not obvious that the "reduce" behavior is a sum for a generic map_reduce function, it is why I prefer a solution where the behavior is passed as parameter.

\$\endgroup\$
1
\$\begingroup\$

More idiomatic Erlang would use pattern matching in function clause head add_to_key({Key, Value}, Sum) but when you are using Data.Map in Haskell you should use a similar key/value storage in Erlang as well. In pre R17 releases, it would be mostly dict but now we have maps as well. There is also not common to make extra function as add_to_key/2 (Personally, I would prefer it, but it is not idiomatic.):

map_reduce(L) ->
    F = fun({K, V}, M) ->
            maps:put(K, V + maps:get(K, M, 0), M)
        end,
    maps:to_list(lists:foldl(F, #{}, L)).

Anyway it would not be rare to use approach with sorting list as in Pascal's answer:

map_reduce(L) ->
    F = fun({K, V1}, [{K, V2}|Acc]) ->
            [{K, V1 + V2}|Acc];
           ({K, V}, Acc) ->
            [{K, V}|Acc]
        end,
    lists:foldl(F, [], lists:sort(L)).
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.