[erlang-questions] fast tuple sorting

Sean Cribbs sean@REDACTED
Fri May 30 18:39:00 CEST 2014


Yes, I doubt it as well, with 50K tuples it might become near-useless
simply from copying/memory pressure. The tradeoff with the binomial heap is
it is more expensive to take from it, but is cheap to merge. I have found
it most useful for "Top N" sorts of operations, where N is small but the
candidate set is somewhat larger.


On Fri, May 30, 2014 at 11:25 AM, Dmitry Kolesnikov <dmkolesnikov@REDACTED>
wrote:

> 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/
>
>
>


-- 
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/0a069599/attachment.htm>


More information about the erlang-questions mailing list