Benchmark map creation and the proposed lists:uniq/1

mbench.erl

-module(mbench).
%%-compile(export_all).
-export([run/0]).

run() ->
    Limit = 2_000_000,
    Data = gen_data(0, Limit, []),
    io:format("generated ~p data items\n", [Limit]),
    %%io:format("~P\n", [Data,10]),
    Tests = [{"one_by_one/1",fun one_by_one/1},
             {"all_at_once/1",fun all_at_once/1},
             {"uniq_one_by_one/1",fun uniq_one_by_one/1},
             {"uniq_by_sofs/1",fun uniq_by_sofs/1},
             {"uniq_indexes/1",fun uniq_indexes/1},
             {"uniq_by_usort/1",fun uniq_by_usort/1}],
    run(Tests, Data).

gen_data(Limit, Limit, Acc) ->
    Acc;
gen_data(N, Limit, Acc) ->
    %% Item = N,
    Item = erlang:phash2(N),
    gen_data(N+1, Limit, [Item|Acc]).

run([{Name,Test}|Ts], Data) ->
    {Pid,Ref} = spawn_monitor(fun() ->
                                      {Time,_Res} = timer:tc(Test, [Data]),
                                      %% io:format("~P\n", [_Res,10]),
                                      exit(Time)
                              end),
    receive
        {'DOWN',Ref,process,Pid,Time} ->
            io:format("~.20ts: ~p\n", [Name,Time / 1_000_000]),
            run(Ts, Data)
    end;
run([], _Data) ->
    ok.

one_by_one(Data) ->
    one_by_one(Data, #{}).

one_by_one([Key|T], Map) ->
    one_by_one(T, Map#{Key => {Key, Key+1}});
one_by_one([], Map) ->
    Map.

all_at_once(Data) ->
    all_at_once(Data, []).

all_at_once([Key|T], Acc) ->
    all_at_once(T, [{Key, Key+1}|Acc]);
all_at_once([], Acc) ->
    maps:from_list(Acc).

uniq_one_by_one(L) ->
    uniq_one_by_one(L, #{}).

uniq_one_by_one([X|Xs], M) ->
    case is_map_key(X, M) of
        true ->
            uniq_one_by_one(Xs, M);
        false ->
            [X|uniq_one_by_one(Xs, M#{X => true})]
    end;
uniq_one_by_one([], _) ->
    [].

uniq_by_usort(L) ->
    lists:usort(L).

uniq_by_sofs(L0) ->
    L = number(L0, 0),
    S0 = sofs:relation(L),
    S1 = sofs:relation_to_family(S0),
    S2 = sofs:converse(S1),
    S3 = sofs:to_external(S2),
    [E || {_,E} <- S3].

number([H|T], N) ->
    [{H,N}|number(T, N+1)];
number([], _) ->
    [].

uniq_indexes(L0) ->
    L1 = add_index(L0, 0, []),
    L2 = lists:usort(fun([_|A], [_|B]) -> A =< B end, L1),
    L3 = lists:sort(L2),
    take_indexed(L0, 0, L3).

add_index([H1 | T], I, [[_ | H2] | _]=Acc) when H1 == H2 ->
    add_index(T, I + 1, Acc);
add_index([H | T], I, Acc) ->
    add_index(T, I + 1, [[I | H] | Acc]);
add_index([], _I, Acc) ->
    Acc.

take_indexed([H | T], I, [[I | _] | Is]) ->
    [H | take_indexed(T, I + 1, Is)];
take_indexed([_ | T], I, [_ | _]=Is) ->
    take_indexed(T, I + 1, Is);
take_indexed([_ | _], _I, []) ->
    [];
take_indexed([], _I, []) ->
    [].