Skip to content

Instantly share code, notes, and snippets.

@pichi

pichi/test.erl

Forked from zhongwencool/test.erl
Last active July 27, 2016 03:25
Show Gist options
  • Save pichi/4d01443dc65e3fd6cc3784ec6998c16b to your computer and use it in GitHub Desktop.
Save pichi/4d01443dc65e3fd6cc3784ec6998c16b to your computer and use it in GitHub Desktop.
Download ZIP
Find top n items in a unordered list
Raw
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_small_to_big_order_list(List, Num) ->
run_small_to_big_order_list(List, Num, 0, []).
run_small_to_big_order_list([], _Num, _, Acc) ->
lists:foldl(fun({Key1, Key2, Key3}, Sum) -> [{Key2, Key1, Key3}|Sum] end, [], Acc);
run_small_to_big_order_list([{Key1, Key2, Key3}|List], Num, Len, Acc) ->
NewKey = {Key2, Key1, Key3},
{NewLen, NewAcc} =
case Len < Num of
true ->
{Len + 1, lists:sort([NewKey|Acc])};
false ->
[Smallest|Acc2] = Acc,
case Smallest < NewKey of
true ->
{Len, lists:sort([NewKey|Acc2])};
false ->
{Len, Acc}
end
end,
run_small_to_big_order_list(List, Num, NewLen, NewAcc).
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.
run_big_to_small_order_list(List, Num) ->
run_big_to_small_order_list(List, Num, 0, []).
run_big_to_small_order_list([], _Num, _, Acc) ->
Acc;
run_big_to_small_order_list([Key|List], Num, Len, Acc) ->
{NewLen, NewAcc} =
case Len < Num of
true ->
{Len + 1, lists:sort(fun({X2, X1, _}, {Y2, Y1, _}) -> {X1, X2} > {Y1, Y2} end, [Key|Acc])};
false ->
Smallest = lists:last(Acc),
case Smallest < Key of
true ->
Acc2 = lists:sublist(Acc, Len - 1),
{Len, lists:sort(fun({X2, X1, _}, {Y2, Y1, _}) -> {X1, X2} > {Y1, Y2} end, [Key|Acc2])};
false ->
{Len, Acc}
end
end,
run_big_to_small_order_list(List, Num, NewLen, NewAcc).
test() ->
[ test(TotalNum, TopNum)
|| TotalNum <- [5000, 10000, 15000, 20000, 25000],
TopNum <- [20, 30, 40, 50, 60, 70]].
%% 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_small_to_big_order_list, small_to_big_order_list___},
{run_big_to_small_order_list, big_to_small_order_list___},
{run_small_to_big_order_list_v2, small_to_big_order_list_v2},
{run_pheap, pheap_____________________}],
Pid <- [spawn_link(fun() ->
{Time, Result} = timer:tc(?MODULE, F, [List, TopNum]),
Self ! {self(), {Type, Time, Result}}
end)]
]),
[{_, 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) ])
].
@pichi
Copy link
Author

pichi commented Jul 25, 2016

Pairing heap implementation is significantly faster.

1> c(test).
{ok,test}
2> rp(test:test()).
[{{5000,20},
  [{pheap_____________________,103,100.0},
   {small_to_big_order_list_v2,236,229.126213592233},
   {small_to_big_order_list___,491,476.6990291262136},
   {gb_tree___________________,518,502.91262135922335},
   {big_to_small_order_list___,1024,994.1747572815533},
   {all_sorted_sublist________,2183,2119.4174757281553}]},
 {{5000,30},
  [{pheap_____________________,143,100.0},
   {small_to_big_order_list_v2,561,392.30769230769226},
   {gb_tree___________________,569,397.9020979020979},
   {small_to_big_order_list___,797,557.3426573426573},
   {all_sorted_sublist________,1811,1266.4335664335665},
   {big_to_small_order_list___,1841,1287.4125874125873}]},
 {{5000,40},
  [{pheap_____________________,145,100.0},
   {small_to_big_order_list_v2,352,242.75862068965517},
   {gb_tree___________________,658,453.7931034482758},
   {small_to_big_order_list___,1781,1228.2758620689656},
   {all_sorted_sublist________,1806,1245.5172413793105},
   {big_to_small_order_list___,3747,2584.137931034483}]},
 {{5000,50},
  [{pheap_____________________,164,100.0},
   {small_to_big_order_list_v2,427,260.3658536585366},
   {gb_tree___________________,691,421.3414634146342},
   {small_to_big_order_list___,1595,972.5609756097562},
   {all_sorted_sublist________,1821,1110.3658536585365},
   {big_to_small_order_list___,3836,2339.0243902439024}]},
 {{5000,60},
  [{pheap_____________________,172,100.0},
   {small_to_big_order_list_v2,498,289.5348837209302},
   {gb_tree___________________,730,424.4186046511628},
   {all_sorted_sublist________,1794,1043.0232558139535},
   {small_to_big_order_list___,2091,1215.6976744186047},
   {big_to_small_order_list___,4703,2734.3023255813955}]},
 {{5000,70},
  [{pheap_____________________,185,100.0},
   {small_to_big_order_list_v2,641,346.4864864864865},
   {gb_tree___________________,822,444.3243243243243},
   {all_sorted_sublist________,1781,962.7027027027028},
   {small_to_big_order_list___,2563,1385.4054054054054},
   {big_to_small_order_list___,5993,3239.459459459459}]},
 {{10000,20},
  [{pheap_____________________,178,100.0},
   {small_to_big_order_list_v2,472,265.1685393258427},
   {small_to_big_order_list___,874,491.0112359550562},
   {gb_tree___________________,1065,598.314606741573},
   {big_to_small_order_list___,1893,1063.4831460674156},
   {all_sorted_sublist________,3968,2229.2134831460676}]},
 {{10000,30},
  [{pheap_____________________,198,100.0},
   {small_to_big_order_list_v2,515,260.1010101010101},
   {gb_tree___________________,1159,585.3535353535353},
   {small_to_big_order_list___,1301,657.070707070707},
   {big_to_small_order_list___,2607,1316.6666666666665},
   {all_sorted_sublist________,3975,2007.5757575757575}]},
 {{10000,40},
  [{pheap_____________________,219,100.0},
   {small_to_big_order_list_v2,607,277.1689497716895},
   {small_to_big_order_list___,1727,788.5844748858448},
   {big_to_small_order_list___,3916,1788.1278538812787},
   {gb_tree___________________,3957,1806.8493150684933},
   {all_sorted_sublist________,4145,1892.6940639269408}]},
 {{10000,50},
  [{pheap_____________________,243,100.0},
   {small_to_big_order_list_v2,677,278.6008230452675},
   {gb_tree___________________,1296,533.3333333333333},
   {small_to_big_order_list___,2221,913.9917695473251},
   {all_sorted_sublist________,3995,1644.0329218106995},
   {big_to_small_order_list___,5610,2308.641975308642}]},
 {{10000,60},
  [{pheap_____________________,268,100.0},
   {small_to_big_order_list_v2,900,335.82089552238807},
   {gb_tree___________________,1366,509.7014925373134},
   {small_to_big_order_list___,2918,1088.8059701492537},
   {all_sorted_sublist________,4084,1523.8805970149253},
   {big_to_small_order_list___,7235,2699.6268656716416}]},
 {{10000,70},
  [{pheap_____________________,328,100.0},
   {small_to_big_order_list_v2,1070,326.219512195122},
   {gb_tree___________________,1440,439.0243902439025},
   {small_to_big_order_list___,3603,1098.4756097560976},
   {all_sorted_sublist________,3961,1207.621951219512},
   {big_to_small_order_list___,8761,2671.0365853658536}]},
 {{15000,20},
  [{pheap_____________________,251,100.0},
   {small_to_big_order_list_v2,638,254.18326693227093},
   {small_to_big_order_list___,1026,408.7649402390438},
   {gb_tree___________________,1558,620.7171314741036},
   {big_to_small_order_list___,2383,949.4023904382469},
   {all_sorted_sublist________,7120,2836.6533864541834}]},
 {{15000,30},
  [{pheap_____________________,277,100.0},
   {small_to_big_order_list_v2,709,255.956678700361},
   {gb_tree___________________,1662,600.0},
   {small_to_big_order_list___,1709,616.9675090252707},
   {big_to_small_order_list___,4015,1449.4584837545126},
   {all_sorted_sublist________,6527,2356.317689530686}]},
 {{15000,40},
  [{pheap_____________________,297,100.0},
   {small_to_big_order_list_v2,783,263.6363636363636},
   {gb_tree___________________,1705,574.074074074074},
   {small_to_big_order_list___,2213,745.1178451178451},
   {big_to_small_order_list___,5417,1823.9057239057238},
   {all_sorted_sublist________,6553,2206.3973063973062}]},
 {{15000,50},
  [{pheap_____________________,323,100.0},
   {small_to_big_order_list_v2,900,278.63777089783287},
   {gb_tree___________________,1835,568.1114551083591},
   {small_to_big_order_list___,2794,865.0154798761611},
   {all_sorted_sublist________,6448,1996.2848297213623},
   {big_to_small_order_list___,7317,2265.325077399381}]},
 {{15000,60},
  [{pheap_____________________,367,100.0},
   {small_to_big_order_list_v2,986,268.66485013623975},
   {gb_tree___________________,1969,536.5122615803815},
   {small_to_big_order_list___,3358,914.9863760217985},
   {all_sorted_sublist________,6718,1830.517711171662},
   {big_to_small_order_list___,8747,2383.3787465940054}]},
 {{15000,70},
  [{pheap_____________________,371,100.0},
   {small_to_big_order_list_v2,1225,330.188679245283},
   {gb_tree___________________,1887,508.6253369272237},
   {small_to_big_order_list___,4555,1227.7628032345015},
   {all_sorted_sublist________,6716,1810.242587601078},
   {big_to_small_order_list___,10947,2950.6738544474397}]},
 {{20000,20},
  [{pheap_____________________,625,100.0},
   {small_to_big_order_list_v2,1077,172.32},
   {small_to_big_order_list___,1789,286.24},
   {gb_tree___________________,2265,362.40000000000003},
   {big_to_small_order_list___,3233,517.28},
   {all_sorted_sublist________,10209,1633.4399999999998}]},
 {{20000,30},
  [{pheap_____________________,1237,100.0},
   {small_to_big_order_list_v2,1736,140.33953112368633},
   {small_to_big_order_list___,2164,174.93936944219888},
   {gb_tree___________________,2432,196.6046887631366},
   {big_to_small_order_list___,4648,375.7477768795473},
   {all_sorted_sublist________,10602,857.0735650767988}]},
 {{20000,40},
  [{pheap_____________________,1197,100.0},
   {small_to_big_order_list_v2,1804,150.71010860484543},
   {small_to_big_order_list___,2505,209.2731829573935},
   {gb_tree___________________,2654,221.72096908939017},
   {big_to_small_order_list___,6320,527.9866332497911},
   {all_sorted_sublist________,9890,826.2322472848789}]},
 {{20000,50},
  [{pheap_____________________,1278,100.0},
   {small_to_big_order_list_v2,1992,155.86854460093898},
   {gb_tree___________________,2422,189.51486697965572},
   {small_to_big_order_list___,3104,242.87949921752738},
   {big_to_small_order_list___,8652,676.9953051643192},
   {all_sorted_sublist________,10109,791.001564945227}]},
 {{20000,60},
  [{pheap_____________________,1065,100.0},
   {small_to_big_order_list_v2,1817,170.61032863849766},
   {gb_tree___________________,2726,255.96244131455398},
   {small_to_big_order_list___,3881,364.4131455399061},
   {big_to_small_order_list___,10609,996.150234741784},
   {all_sorted_sublist________,10753,1009.6713615023473}]},
 {{20000,70},
  [{pheap_____________________,1329,100.0},
   {small_to_big_order_list_v2,2229,167.72009029345372},
   {gb_tree___________________,2651,199.47328818660648},
   {small_to_big_order_list___,4747,357.1858540255831},
   {all_sorted_sublist________,9556,719.0368698269375},
   {big_to_small_order_list___,12866,968.0963130173062}]},
 {{25000,20},
  [{pheap_____________________,427,100.0},
   {small_to_big_order_list_v2,1010,236.53395784543326},
   {small_to_big_order_list___,1630,381.73302107728335},
   {gb_tree___________________,2643,618.9695550351289},
   {big_to_small_order_list___,3544,829.976580796253},
   {all_sorted_sublist________,12161,2848.0093676814986}]},
 {{25000,30},
  [{pheap_____________________,446,100.0},
   {small_to_big_order_list_v2,1092,244.84304932735427},
   {small_to_big_order_list___,2482,556.5022421524664},
   {gb_tree___________________,2701,605.6053811659193},
   {big_to_small_order_list___,5456,1223.3183856502242},
   {all_sorted_sublist________,11576,2595.5156950672645}]},
 {{25000,40},
  [{pheap_____________________,446,100.0},
   {small_to_big_order_list_v2,1141,255.82959641255604},
   {gb_tree___________________,2691,603.3632286995517},
   {small_to_big_order_list___,3237,725.7847533632287},
   {big_to_small_order_list___,7148,1602.6905829596412},
   {all_sorted_sublist________,11395,2554.932735426009}]},
 {{25000,50},
  [{pheap_____________________,464,100.0},
   {small_to_big_order_list_v2,1288,277.58620689655174},
   {gb_tree___________________,2848,613.7931034482759},
   {small_to_big_order_list___,3435,740.301724137931},
   {big_to_small_order_list___,9916,2137.0689655172414},
   {all_sorted_sublist________,11612,2502.5862068965516}]},
 {{25000,60},
  [{pheap_____________________,505,100.0},
   {small_to_big_order_list_v2,1383,273.8613861386139},
   {gb_tree___________________,2986,591.2871287128713},
   {small_to_big_order_list___,4425,876.2376237623762},
   {all_sorted_sublist________,11465,2270.2970297029706},
   {big_to_small_order_list___,12051,2386.3366336633662}]},
 {{25000,70},
  [{pheap_____________________,540,100.0},
   {small_to_big_order_list_v2,1536,284.44444444444446},
   {gb_tree___________________,3074,569.2592592592592},
   {small_to_big_order_list___,5947,1101.2962962962963},
   {all_sorted_sublist________,11877,2199.4444444444443},
   {big_to_small_order_list___,14954,2769.259259259259}]}]
ok

@pichi
Copy link
Author

pichi commented Jul 26, 2016

When {X, Y} from {Y, X, _} used as comparing key used pairing heap is still fastest.

> rp(test:test()).
[{{5000,20},
  [{pheap_____________________,208,100.0},
   {small_to_big_order_list_v2,416,200.0},
   {small_to_big_order_list___,421,202.40384615384616},
   {gb_tree___________________,490,235.5769230769231},
   {big_to_small_order_list___,1266,608.6538461538462},
   {all_sorted_sublist________,2544,1223.076923076923}]},
 {{5000,30},
  [{pheap_____________________,241,100.0},
   {small_to_big_order_list_v2,534,221.5767634854772},
   {gb_tree___________________,577,239.41908713692945},
   {small_to_big_order_list___,889,368.87966804979254},
   {big_to_small_order_list___,2396,994.1908713692947},
   {all_sorted_sublist________,2553,1059.3360995850621}]},
 {{5000,40},
  [{pheap_____________________,264,100.0},
   {small_to_big_order_list_v2,657,248.86363636363637},
   {gb_tree___________________,697,264.0151515151515},
   {small_to_big_order_list___,1769,670.0757575757576},
   {all_sorted_sublist________,2588,980.3030303030303},
   {big_to_small_order_list___,3825,1448.8636363636363}]},
 {{5000,50},
  [{pheap_____________________,301,100.0},
   {gb_tree___________________,668,221.9269102990033},
   {small_to_big_order_list_v2,839,278.7375415282392},
   {small_to_big_order_list___,1677,557.1428571428571},
   {all_sorted_sublist________,3181,1056.810631229236},
   {big_to_small_order_list___,5570,1850.4983388704318}]},
 {{5000,60},
  [{pheap_____________________,319,100.0},
   {gb_tree___________________,708,221.9435736677116},
   {small_to_big_order_list_v2,929,291.22257053291537},
   {small_to_big_order_list___,2255,706.8965517241379},
   {all_sorted_sublist________,2429,761.4420062695925},
   {big_to_small_order_list___,6623,2076.175548589342}]},
 {{5000,70},
  [{pheap_____________________,348,100.0},
   {gb_tree___________________,773,222.1264367816092},
   {small_to_big_order_list_v2,1113,319.8275862068965},
   {all_sorted_sublist________,2421,695.6896551724138},
   {small_to_big_order_list___,2798,804.0229885057471},
   {big_to_small_order_list___,9017,2591.0919540229884}]},
 {{10000,20},
  [{pheap_____________________,537,100.0},
   {small_to_big_order_list_v2,893,166.29422718808195},
   {gb_tree___________________,1061,197.57914338919926},
   {small_to_big_order_list___,1213,225.88454376163872},
   {big_to_small_order_list___,2191,408.00744878957175},
   {all_sorted_sublist________,6821,1270.2048417132216}]},
 {{10000,30},
  [{pheap_____________________,467,100.0},
   {small_to_big_order_list_v2,1141,244.32548179871517},
   {gb_tree___________________,1151,246.46680942184153},
   {small_to_big_order_list___,1238,265.0963597430407},
   {big_to_small_order_list___,3297,705.9957173447538},
   {all_sorted_sublist________,6513,1394.646680942184}]},
 {{10000,40},
  [{pheap_____________________,512,100.0},
   {small_to_big_order_list_v2,1144,223.4375},
   {gb_tree___________________,1254,244.921875},
   {small_to_big_order_list___,1673,326.7578125},
   {big_to_small_order_list___,4833,943.9453125},
   {all_sorted_sublist________,7945,1551.7578125}]},
 {{10000,50},
  [{pheap_____________________,559,100.0},
   {gb_tree___________________,1276,228.26475849731662},
   {small_to_big_order_list_v2,1327,237.3881932021467},
   {small_to_big_order_list___,2078,371.7352415026834},
   {all_sorted_sublist________,6550,1171.7352415026835},
   {big_to_small_order_list___,7019,1255.6350626118067}]},
 {{10000,60},
  [{pheap_____________________,633,100.0},
   {gb_tree___________________,1373,216.9036334913112},
   {small_to_big_order_list_v2,1599,252.60663507109004},
   {small_to_big_order_list___,2942,464.77093206951025},
   {all_sorted_sublist________,6798,1073.9336492890995},
   {big_to_small_order_list___,8977,1418.1674565560822}]},
 {{10000,70},
  [{pheap_____________________,655,100.0},
   {gb_tree___________________,1404,214.3511450381679},
   {small_to_big_order_list_v2,1791,273.4351145038168},
   {small_to_big_order_list___,3504,534.9618320610687},
   {all_sorted_sublist________,7089,1082.290076335878},
   {big_to_small_order_list___,11657,1779.6946564885495}]},
 {{15000,20},
  [{pheap_____________________,625,100.0},
   {small_to_big_order_list___,1032,165.12},
   {small_to_big_order_list_v2,1413,226.08},
   {gb_tree___________________,1542,246.72},
   {big_to_small_order_list___,3128,500.48},
   {all_sorted_sublist________,10457,1673.1200000000001}]},
 {{15000,30},
  [{pheap_____________________,638,100.0},
   {small_to_big_order_list_v2,1412,221.31661442006268},
   {small_to_big_order_list___,1537,240.9090909090909},
   {gb_tree___________________,1611,252.50783699059562},
   {big_to_small_order_list___,4411,691.3793103448276},
   {all_sorted_sublist________,10565,1655.9561128526645}]},
 {{15000,40},
  [{pheap_____________________,692,100.0},
   {small_to_big_order_list_v2,1586,229.1907514450867},
   {gb_tree___________________,1616,233.52601156069363},
   {small_to_big_order_list___,1977,285.6936416184971},
   {big_to_small_order_list___,6200,895.9537572254336},
   {all_sorted_sublist________,10481,1514.5953757225434}]},
 {{15000,50},
  [{pheap_____________________,714,100.0},
   {small_to_big_order_list_v2,1808,253.22128851540614},
   {gb_tree___________________,1828,256.0224089635854},
   {small_to_big_order_list___,2724,381.51260504201684},
   {big_to_small_order_list___,8821,1235.4341736694678},
   {all_sorted_sublist________,10629,1488.655462184874}]},
 {{15000,60},
  [{pheap_____________________,768,100.0},
   {gb_tree___________________,1822,237.23958333333334},
   {small_to_big_order_list_v2,2080,270.83333333333337},
   {small_to_big_order_list___,3452,449.4791666666667},
   {all_sorted_sublist________,10152,1321.875},
   {big_to_small_order_list___,11040,1437.5}]},
 {{15000,70},
  [{pheap_____________________,758,100.0},
   {gb_tree___________________,1870,246.7018469656992},
   {small_to_big_order_list_v2,2185,288.2585751978892},
   {small_to_big_order_list___,3698,487.8627968337731},
   {all_sorted_sublist________,10733,1415.9630606860158},
   {big_to_small_order_list___,12817,1690.8970976253297}]},
 {{20000,20},
  [{pheap_____________________,1542,100.0},
   {small_to_big_order_list___,1652,107.13359273670558},
   {small_to_big_order_list_v2,2228,144.48767833981842},
   {gb_tree___________________,2297,148.96238651102465},
   {big_to_small_order_list___,4023,260.89494163424126},
   {all_sorted_sublist________,13749,891.6342412451362}]},
 {{20000,30},
  [{pheap_____________________,1577,100.0},
   {small_to_big_order_list___,2006,127.20355104629041},
   {small_to_big_order_list_v2,2299,145.78313253012047},
   {gb_tree___________________,2340,148.38300570703868},
   {big_to_small_order_list___,5309,336.65187064045654},
   {all_sorted_sublist________,12764,809.3849080532657}]},
 {{20000,40},
  [{pheap_____________________,1575,100.0},
   {small_to_big_order_list_v2,2403,152.57142857142858},
   {gb_tree___________________,2463,156.38095238095238},
   {small_to_big_order_list___,2564,162.7936507936508},
   {big_to_small_order_list___,7816,496.2539682539682},
   {all_sorted_sublist________,13601,863.5555555555555}]},
 {{20000,50},
  [{pheap_____________________,1627,100.0},
   {gb_tree___________________,2584,158.819913952059},
   {small_to_big_order_list_v2,2593,159.37307928703135},
   {small_to_big_order_list___,3209,197.23417332513827},
   {big_to_small_order_list___,10383,638.1684081130916},
   {all_sorted_sublist________,12997,798.8322065150584}]},
 {{20000,60},
  [{pheap_____________________,1517,100.0},
   {gb_tree___________________,2560,168.75411997363216},
   {small_to_big_order_list_v2,2729,179.8945286750165},
   {small_to_big_order_list___,3947,260.18457481872116},
   {big_to_small_order_list___,13099,863.4805537244562},
   {all_sorted_sublist________,13600,896.5062623599209}]},
 {{20000,70},
  [{pheap_____________________,1719,100.0},
   {gb_tree___________________,2711,157.70796974985458},
   {small_to_big_order_list_v2,2927,170.27341477603258},
   {small_to_big_order_list___,4466,259.8022105875509},
   {all_sorted_sublist________,14636,851.4252472367655},
   {big_to_small_order_list___,15626,909.0168702734148}]},
 {{25000,20},
  [{pheap_____________________,1022,100.0},
   {small_to_big_order_list___,1529,149.60861056751466},
   {small_to_big_order_list_v2,2107,206.16438356164383},
   {gb_tree___________________,2577,252.15264187866927},
   {big_to_small_order_list___,4458,436.2035225048924},
   {all_sorted_sublist________,20115,1968.1996086105673}]},
 {{25000,30},
  [{pheap_____________________,1185,100.0},
   {small_to_big_order_list___,2335,197.0464135021097},
   {small_to_big_order_list_v2,2561,216.11814345991561},
   {gb_tree___________________,2573,217.13080168776372},
   {big_to_small_order_list___,6899,582.1940928270042},
   {all_sorted_sublist________,21925,1850.2109704641348}]},
 {{25000,40},
  [{pheap_____________________,1153,100.0},
   {small_to_big_order_list_v2,2674,231.9167389418907},
   {gb_tree___________________,2743,237.90112749349524},
   {small_to_big_order_list___,2945,255.42064180398958},
   {big_to_small_order_list___,8707,755.160450997398},
   {all_sorted_sublist________,20801,1804.0763226366003}]},
 {{25000,50},
  [{pheap_____________________,1163,100.0},
   {small_to_big_order_list_v2,2777,238.77901977644024},
   {gb_tree___________________,2846,244.71195184866724},
   {small_to_big_order_list___,3738,321.4101461736887},
   {big_to_small_order_list___,12032,1034.5657781599311},
   {all_sorted_sublist________,21689,1864.9183147033532}]},
 {{25000,60},
  [{pheap_____________________,1192,100.0},
   {small_to_big_order_list_v2,2927,245.55369127516778},
   {gb_tree___________________,2945,247.06375838926172},
   {small_to_big_order_list___,4864,408.0536912751678},
   {big_to_small_order_list___,14562,1221.6442953020135},
   {all_sorted_sublist________,20155,1690.8557046979865}]},
 {{25000,70},
  [{pheap_____________________,1248,100.0},
   {gb_tree___________________,3106,248.8782051282051},
   {small_to_big_order_list_v2,3654,292.78846153846155},
   {small_to_big_order_list___,5396,432.3717948717949},
   {big_to_small_order_list___,19181,1536.9391025641025},
   {all_sorted_sublist________,19811,1587.4198717948718}]}]
ok

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment