CODEWITHSUNDEEP
algorithmlisterlang
danechkin
danechkin

Reputation: 1306

effective key/value lists merge in erlang

I have a couple of key/value propper lists, like that:

    L1 = [{k1, 1}, {k2, 2}, ... {k32, 32}],
    L2 = [{k32, 0.1}, {k31, 0.2}, ... {k1, 0.32}].

What is effective way to merge it by key? Currently I do like that:

    MergeFun = fun(_, X, Y) -> X+Y end,
    D1 = dict:from_list(L1),
    D2 = dict:from_list(L2),
    Res = dict:to_list(dict:merge(MergeFun, D1, D2)).

But that is pretty slow. I assume that input lists not so big, maybe 32-64 elements and elements could be in any order.

Upvotes: 2

Views: 2022

Answers (2)

KrHubert
KrHubert

Reputation: 1030

I would sort these two lists and then merge with one simple function.I don't see faster way to do this, for now.

test() ->
    L1 = [{k1, 1}, {k2, 2}, {k32, 32}],
    L2 = [{k32, 0.1}, {k2, 0.2},  {k1, 0.32}],
    MergeFun = fun(X, Y) -> X+Y end,    
    merge(MergeFun, L1, L2).

merge(Fun, L1, L2) ->
    my_marge(Fun, lists:keysort(1, L1), lists:keysort(1, L2), []).

my_marge(Fun, [{Key, V1} | L1], [{Key, V2} | L2], Acc) ->
    my_marge(Fun, L1, L2, [{Key, Fun(V1, V2)} | Acc]);

my_marge(Fun, [], [{Key, V} | L], Acc) ->
    my_marge(Fun, [], L, [{Key, V} | Acc]);

my_marge(Fun, [{Key, V} | L], [], Acc) ->
    my_marge(Fun,L,[], [{Key, V} | Acc]);

my_marge(Fun, [{Key1, V1} | L1], [{Key2, V2} | L2], Acc) when Key1 < Key2 ->
    my_marge(Fun, L1, [{Key2, V2} | L2], [{Key1, V1} | Acc]);

my_marge(Fun, L1, [{Key, V} | L2], Acc) ->
    my_marge(Fun, L1, L2, [{Key, V} | Acc]);

my_marge(_Fun, [], [], Acc) ->
    Acc.

Upvotes: 1

RichardC
RichardC

Reputation: 10557

Use the orddict module, which explicitly works on lists of pairs:

orddict:merge(fun(_,X,Y) -> X+Y end, orddict:from_list(L1), orddict:from_list(L2)).

Even better, if you ensure that L1 and L2 are always kept ordered by key, you don't need to call from_list(L) before you merge.

Upvotes: 6

Related Questions