[erlang-questions] fast tuple sorting

[Dmitry Kolesnikov]

I’ve used a normal heap but it does not differ to much from gb_tree as you said. 
Insert is log(N) as gb_tree but actually run-time was faster about 79ms vs 132ms but I think this is due re-balance.

I can try binomial_heap but I am really doubt it would be fast enough.

- Dmitry

On 30 May 2014, at 19:03, Sean Cribbs <sean@REDACTED> wrote:

> Not sure it's going to be any better than ets or gb_trees, but I implemented Okasaki's binomial heap: https://github.com/seancribbs/eunit_formatters/blob/master/src/binomial_heap.erl
> 
> It has cheap insertion, and you can adjust the comparator function to convert it between min/max forms.
> 
> 
> On Fri, May 30, 2014 at 10:35 AM, Bob Ippolito <bob@REDACTED> wrote:
> Why does it have to be a list? Why not store it in a gb_tree instead, this way it's sorted as you build it. Another alternative would be to use an ordered_set ets table.
> 
> 
> 
> On Fri, May 30, 2014 at 8:15 AM, Dmitry Kolesnikov <dmkolesnikov@REDACTED> wrote:
> Hello,
> 
> I need to sort a list of tuples {integer(), float()} within 6 ms. the lists:keysort(1, X) is not fast enough for me. I am able to meet the hard requirement only if the list size about 10K tuples. However, my application needs to sort lists of 50K tuples or so.
> 
> I doubt that any other sort algorithm implemented in Erlang would solve my issue. Parallel sort would not help at all because production system would run parallel requests of lists sorting. I am starting to think of offloading the sorting to NIF.
> 
> Any thought?
> 
> Best Regards,
> Dmitry
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
> 
> 
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
> 
> 
> 
> 
> -- 
> Sean Cribbs <sean@REDACTED>
> Software Engineer
> Basho Technologies, Inc.
> http://basho.com/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20140530/d4f15092/attachment.htm>