Find top n items in a unordered list

test.erl

-module(test).
-compile(export_all).
%% API

-compile({inline, [  insert/2
                   , merge/2
                  ]}).

insert(E, []) -> [E];
insert(E, [E2|_] = H) when E =< E2 -> [E, H];
insert(E, [E2|H]) -> [E2, [E]|H].

merge(H1, []) -> H1;
merge([E1|H1], [E2|_]=H2) when E1 =< E2 -> [E1, H2|H1];
merge(H1, [E2|H2]) -> [E2, H1|H2].

merge_pairs([]) -> [];
merge_pairs([H]) -> H;
merge_pairs([A, B|T]) -> merge(merge(A, B), merge_pairs(T)).

run_pheap(List, Num) ->
    run_pheap(List, Num, []).

run_pheap(List, 0, Heap) ->
    pheap_full(List, Heap);
run_pheap([], 0, Heap) ->
    finish(Heap, []);
run_pheap([{Y, X, _} = H|T], N, Heap) ->
    run_pheap(T, N-1, insert({{X, Y}, H}, Heap)).

pheap_full([], Heap) ->
    finish(Heap, []);
pheap_full([{Y, X, _} = H|T], [{K, _}|HeapT] = Heap) ->
    case {X, Y} of
        N when N > K ->
            pheap_full(T, insert({N, H}, merge_pairs(HeapT)));
        _ -> 
            pheap_full(T, Heap)
    end.

finish([], Acc) -> Acc;
finish([{_, H}|T], Acc) ->
    finish(merge_pairs(T), [H|Acc]).

run_all_sorted_sublist(List, Num) ->
    L = [ {{X, Y}, Z} || {Y, X, _} = Z <- List],
    [ X || {_, X} <- lists:sublist(lists:reverse(lists:sort(L)), Num) ].

run_gb_trees(List, Num) ->
    run_gb_trees(List, Num, gb_trees:empty()).

run_gb_trees([], _Num, Acc) ->
  lists:foldl(fun({Key1, Key2, Key3}, Sum) -> [{Key2, Key1, Key3}|Sum] end, [], gb_trees:keys(Acc));
run_gb_trees([{Key1, Key2, Key3}|List], Num, Acc) ->
    NewKey = {Key2, Key1, Key3},
    NewAcc =
        case gb_trees:size(Acc) < Num of
            true ->
                gb_trees:insert(NewKey, 0, Acc);
            false ->
                {Smallest,_} = gb_trees:smallest(Acc),
                case Smallest < NewKey of
                    true ->
                        Acc2 = gb_trees:delete(Smallest, Acc),
                        gb_trees:insert(NewKey, 0, Acc2);
                    false ->
                        Acc
                end
        end,
    run_gb_trees(List, Num, NewAcc).
    
run_ordered_set_ets(List, Num) ->
    T = ets:new(t, [ordered_set, private, {keypos, 2}]),
    try
        fill_set(List, Num, T),
        lists:reverse(ets:tab2list(T))
    after
        ets:delete(T)
    end.


fill_set([], _, _) -> ok;
fill_set(L, 0, T) -> full_set(L, T);
fill_set([H | T], N, Table) ->
    ets:insert(Table, H),
    fill_set(T, N - 1, Table).

full_set([], _) -> ok;
full_set([{_, K, _} = H | T], Table) ->
    case ets:first(Table) of
        S when S < K ->
            ets:delete(Table, S),
            ets:insert(Table, H);
        _ -> ok
    end,
    full_set(T, Table).

run_small_to_big_order_list_v2(List, Num) ->
    run_small_to_big_order_list_v2(List, Num, fun({X2, X1, _}, {Y2, Y1, _})
                                                  -> {X1, X2} =< {Y1, Y2} end, 0, []).

run_small_to_big_order_list_v2([], _, _, _, Acc) ->
    lists:reverse(Acc);
run_small_to_big_order_list_v2([NewKey|List], Num, Fun, Len, Acc) ->
    {NewLen, NewAcc} =
        if Len < Num -> {Len + 1, insert(NewKey, Acc, Fun)};
           true ->
                [Smallest|Acc2] = Acc,
                case Fun(Smallest,NewKey) of
                    true -> {Len, insert(NewKey, Acc2, Fun)};
                    false -> {Len, Acc}
                end
        end,
    run_small_to_big_order_list_v2(List, Num, Fun, NewLen, NewAcc).

insert(K, [], _) -> [K];
insert(K, [H|T], Fun) ->
    case Fun(K, H) of
        true -> [K, H|T];
        false -> [H|insert(K, T, Fun)]
    end.

test() ->
    [ test(TotalNum, TotalNum div Div)
     || TotalNum <- [5000, 10000, 15000, 20000, 25000],
        Div   <- [1000, 100, 10, 5, 2]].

test_big() ->
    [ test(TotalNum, TopNum)
     || TotalNum <- [25000],
        TopNum   <- [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200]].

%% Test
test(TotalNum, TopNum) ->
    List = prepared_random_list(TotalNum),
    %io:format("~p~n", [List]),
    Self = self(),
    L = lists:keysort(2,
          [ receive {Pid, X} -> X end
          || {F, Type} <-
             [{run_all_sorted_sublist,         all_sorted_sublist________},
              {run_gb_trees,                   gb_tree___________________},
              {run_pheap,                      pheap_____________________},
%              {run_small_to_big_order_list_v2, run_small_to_big_order_list_v2},
              {run_ordered_set_ets,            ordered_set_ets___________}],
          Pid <- [spawn_opt(fun() ->
                                     {Time, Result} = timer:tc(?MODULE, F, [List, TopNum]),
                                     Self ! {self(), {Type, Time, Result}}
                             end,
                            [link])]
          ]),
    [{_, Time1, _}|_] = L,
    [_] = lists:ukeysort(3, L),
    {{TotalNum, TopNum}, [{Type,  Time, Time/Time1*100}
                          || {Type,  Time, _} <- L]}.

prepared_random_list(TotalNum) ->
    [ {X, X+1, X+2}
      || {_, X} <- lists:sort(
                     [ {rand:uniform(), X}
                       || X <- lists:seq(1, TotalNum) ])
    ].

> rp(test:test()).
[{{5000,5},
  [{pheap_____________________,199,100.0},
   {ordered_set_ets___________,549,275.8793969849246},
   {gb_tree___________________,806,405.0251256281407},
   {all_sorted_sublist________,3837,1928.1407035175878}]},
 {{5000,50},
  [{pheap_____________________,299,100.0},
   {ordered_set_ets___________,617,206.35451505016724},
   {gb_tree___________________,729,243.81270903010034},
   {all_sorted_sublist________,2482,830.1003344481605}]},
 {{5000,500},
  [{ordered_set_ets___________,1267,100.0},
   {pheap_____________________,2203,173.8752959747435},
   {all_sorted_sublist________,2704,213.4175217048145},
   {gb_tree___________________,4552,359.2738752959748}]},
 {{5000,1000},
  [{ordered_set_ets___________,1676,100.0},
   {pheap_____________________,2307,137.6491646778043},
   {gb_tree___________________,3381,201.73031026252985},
   {all_sorted_sublist________,4473,266.8854415274463}]},
 {{5000,2500},
  [{ordered_set_ets___________,2535,100.0},
   {all_sorted_sublist________,2768,109.19132149901381},
   {pheap_____________________,4257,167.92899408284023},
   {gb_tree___________________,7752,305.7988165680473}]},
 {{10000,10},
  [{pheap_____________________,414,100.0},
   {gb_tree___________________,1008,243.47826086956525},
   {ordered_set_ets___________,1019,246.13526570048307},
   {all_sorted_sublist________,8795,2124.3961352657007}]},
 {{10000,100},
  [{pheap_____________________,891,100.0},
   {ordered_set_ets___________,1258,141.18967452300785},
   {gb_tree___________________,2389,268.1257014590348},
   {all_sorted_sublist________,6321,709.4276094276095}]},
 {{10000,1000},
  [{ordered_set_ets___________,2604,100.0},
   {pheap_____________________,4766,183.02611367127497},
   {gb_tree___________________,5024,192.93394777265743},
   {all_sorted_sublist________,6974,267.81874039938555}]},
 {{10000,2000},
  [{ordered_set_ets___________,3388,100.0},
   {pheap_____________________,7044,207.91027154663516},
   {all_sorted_sublist________,7198,212.45572609208972},
   {gb_tree___________________,7759,229.01416765053128}]},
 {{10000,5000},
  [{ordered_set_ets___________,5084,100.0},
   {all_sorted_sublist________,8111,159.53973249409913},
   {pheap_____________________,9741,191.6011014948859},
   {gb_tree___________________,15121,297.42328874901654}]},
 {{15000,15},
  [{pheap_____________________,598,100.0},
   {ordered_set_ets___________,1539,257.3578595317726},
   {gb_tree___________________,1586,265.2173913043478},
   {all_sorted_sublist________,18330,3065.2173913043475}]},
 {{15000,150},
  [{pheap_____________________,1158,100.0},
   {ordered_set_ets___________,1860,160.6217616580311},
   {gb_tree___________________,2548,220.03454231433506},
   {all_sorted_sublist________,13784,1190.3281519861832}]},
 {{15000,1500},
  [{ordered_set_ets___________,3943,100.0},
   {pheap_____________________,4946,125.43748414912503},
   {gb_tree___________________,9093,230.61120973877757},
   {all_sorted_sublist________,11640,295.20669540958664}]},
 {{15000,3000},
  [{ordered_set_ets___________,5226,100.0},
   {pheap_____________________,10102,193.3027171833142},
   {gb_tree___________________,12723,243.45579793340985},
   {all_sorted_sublist________,14112,270.03444316877153}]},
 {{15000,7500},
  [{ordered_set_ets___________,7627,100.0},
   {all_sorted_sublist________,12213,160.12849088763602},
   {pheap_____________________,16367,214.59289366723482},
   {gb_tree___________________,24052,315.35334994099907}]},
 {{20000,20},
  [{pheap_____________________,1422,100.0},
   {ordered_set_ets___________,2280,160.33755274261603},
   {gb_tree___________________,2494,175.38677918424753},
   {all_sorted_sublist________,15228,1070.886075949367}]},
 {{20000,200},
  [{pheap_____________________,2070,100.0},
   {ordered_set_ets___________,2520,121.73913043478262},
   {gb_tree___________________,3583,173.09178743961354},
   {all_sorted_sublist________,17632,851.7874396135265}]},
 {{20000,2000},
  [{ordered_set_ets___________,5308,100.0},
   {pheap_____________________,11278,212.47174076865107},
   {gb_tree___________________,12154,228.97513187641297},
   {all_sorted_sublist________,18679,351.90278824415975}]},
 {{20000,4000},
  [{pheap_____________________,15581,100.0},
   {all_sorted_sublist________,15878,101.9061677684359},
   {ordered_set_ets___________,17219,110.51280405622232},
   {gb_tree___________________,22418,143.88036711379243}]},
 {{20000,10000},
  [{ordered_set_ets___________,13103,100.0},
   {all_sorted_sublist________,16735,127.71884301305046},
   {pheap_____________________,29619,226.04747004502786},
   {gb_tree___________________,31976,244.03571701137145}]},
 {{25000,25},
  [{pheap_____________________,1109,100.0},
   {ordered_set_ets___________,2700,243.4625788999098},
   {gb_tree___________________,4067,366.726780883679},
   {all_sorted_sublist________,32554,2935.4373309287644}]},
 {{25000,250},
  [{pheap_____________________,2203,100.0},
   {ordered_set_ets___________,3519,159.73672265093055},
   {gb_tree___________________,4356,197.73036768043576},
   {all_sorted_sublist________,28157,1278.1207444394008}]},
 {{25000,2500},
  [{ordered_set_ets___________,6393,100.0},
   {pheap_____________________,9901,154.8725168152667},
   {gb_tree___________________,15658,244.92413577350226},
   {all_sorted_sublist________,24525,383.62271234162364}]},
 {{25000,5000},
  [{ordered_set_ets___________,10598,100.0},
   {pheap_____________________,17809,168.04113983770523},
   {gb_tree___________________,25581,241.37573127005095},
   {all_sorted_sublist________,27615,260.5680317040951}]},
 {{25000,12500},
  [{ordered_set_ets___________,14232,100.0},
   {all_sorted_sublist________,26378,185.34288926363126},
   {pheap_____________________,34690,243.74648679033166},
   {gb_tree___________________,40964,287.83024170882516}]}]
ok