<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;">I’ve used a normal heap but it does not differ to much from gb_tree as you said. <div>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.<br><div><br></div><div>I can try binomial_heap but I am really doubt it would be fast enough.</div><div><br></div><div>- Dmitry</div><div><br><div><div>On 30 May 2014, at 19:03, Sean Cribbs <<a href="mailto:sean@basho.com">sean@basho.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div dir="ltr">Not sure it's going to be any better than ets or gb_trees, but I implemented Okasaki's binomial heap: <a href="https://github.com/seancribbs/eunit_formatters/blob/master/src/binomial_heap.erl">https://github.com/seancribbs/eunit_formatters/blob/master/src/binomial_heap.erl</a><div>
<br></div><div>It has cheap insertion, and you can adjust the comparator function to convert it between min/max forms.</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, May 30, 2014 at 10:35 AM, Bob Ippolito <span dir="ltr"><<a href="mailto:bob@redivi.com" target="_blank">bob@redivi.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">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.<div>
<br></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra">
<br><br><div class="gmail_quote">On Fri, May 30, 2014 at 8:15 AM, Dmitry Kolesnikov <span dir="ltr"><<a href="mailto:dmkolesnikov@gmail.com" target="_blank">dmkolesnikov@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hello,<br>
<br>
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.<br>
<br>
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.<br>
<br>
Any thought?<br>
<br>
Best Regards,<br>
Dmitry<br>
_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
</blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br>Sean Cribbs <<a href="mailto:sean@basho.com" target="_blank">sean@basho.com</a>><div>Software Engineer</div><div>Basho Technologies, Inc.</div><div><a href="http://basho.com/" target="_blank">http://basho.com/</a></div>
</div>
</blockquote></div><br></div></div></body></html>