Find top n items in unordered list function. about recon

[ferd]

That's cool. And yeah, I don't think I ever optimized that bit of code, but it can yield good results for debugging.

I think the small_to_big and big_to_small implementations by far give the best performance on all large-ish data sets with a smaller selection being kept, whereas gb_trees tend to get better as the selection length is the one thing that increases.

I think the small_to_big implementation could be made better by performing an insertion step on the accumulator rather than just re-sorting the full accumulator, which would reduce the overall cost (n/2 per run on average rather than nlogn where n is the accumulator size I think). I tried it for fun and here's the difference in runtime between both tries:

28> test:test(50000, 100).
{{50000,100},
 [{gb_tree________________,12949,100},
  {small_to_big_order_list,17939,138.5357942698278},
  {big_to_small_order_list,42346,327.02139161325204},
  {all_sorted_sublist_____,46114,356.1201637192061}]}
29> c(test).
{ok,test}
30> test:test(50000, 100).
{{50000,100},
 [{small_to_big_order_list,20091,100},
  {gb_tree________________,23022,114.58862177094223},
  {big_to_small_order_list,42949,213.77233587178338},
  {all_sorted_sublist_____,54879,273.15215768254444}]}

goes from being 39% slower than gb_trees to 15% faster.

Here's the diff:

43c43
<                 {Len + 1, lists:sort([NewKey|Acc])};
---
>                 {Len + 1, insert(NewKey, Acc)};
48c48
<                         {Len, lists:sort([NewKey|Acc2])};
---
>                         {Len, insert(NewKey, Acc2)};
54a55,60
> insert(K, []) -> [K];
> insert(K, [H|T]) ->
>     if K =< H -> [K,H|T];
>        K  > H -> [H|insert(K,T)]
>     end.
>
129d134
<

[zhongwencool]

ping @ferd :)

[zhongwencool]

Wow! Your version is really great!
I can send a PR for this.

[ferd]

Yeah that would be appreciated :)