[erlang-questions] [ANN] Priority Queue Implementation

Michael Truog mjtruog@REDACTED
Thu Nov 10 09:12:46 CET 2011


I previously added code that took care of that case, where two nodes needed to be merged that both have queues.  However, I convinced myself at the time, that the case would never happen.  So, the code probably needs to be thought-through a bit more with more testing, but my hope is that merging the queues isn't necessary.  I haven't been able to crash the data structure without that case while using many priorities, but it still requires investigation.

On 11/10/2011 12:01 AM, Ulf Wiger wrote:
>
> Always nice when the simplest approaches prove to be among the fastest. :)
>
> You don't have a case for merging two trees where the roots are the same and both are queues. I guess there isn't any perfect way to merge the queues, unless you put timestamps on each entry…
>
> BR,
> Ulf W
>
> On 10 Nov 2011, at 08:45, Michael Truog wrote:
>
>> I modified the example to extend it with queues and it does compare very well, being slightly faster.  I still believe it needs to be tested more, but the implementation becomes simpler and you don't need the static priority limitations, which is nice.  The link is:
>> https://github.com/okeuday/pqueue/blob/master/src/pqueue2.erl
>>
>> with erlbench results here ((with R14B02, without HiPE) on an AMD Phenom 9950 Quad-Core (64 bit) running Linux 2.6.32-23-generic (Ubuntu)):
>> TEST run_priority_queue
>> N == 1000000 (10 runs)
>>               pqueue get:   481774.3 µs (  1.4), set:   525589.1 µs (  1.0)
>>              pqueue2 get:   332711.2 µs (  1.0), set:   680209.0 µs (  1.3)
>>       priority_queue get:   362588.9 µs (  1.1), set:  1443674.2 µs (  2.7)
>>
>>
>> On 11/09/2011 08:58 AM, Michael Truog wrote:
>>> I think the skew heap I have needs some work, because it seems to come only from Okasaki's code example, so it doesn't take into consideration his suggestions/exercises.  So, only insert is O(1), and the min would need to be stored separately to get O(1) instead of O(log(N)). He had a suggestion for making the merge of two heaps O(1), but I wasn't as concerned about that operation.  It seems hard to get an "out" operation that is O(1) amortized, that is removing the min from the heap (hopefully O(log(N)) worst case).  I will look at testing a heap implementation to see how it might work out.  Thanks for the information.
>>>
>>> On 11/09/2011 01:00 AM, Ulf Wiger wrote:
>>>>
>>>> Yeah, obviously, mine was just a sketch, thrown down as an executable comment and optimized for brevity. :)
>>>>
>>>> (Although I'm not convinced, from reading, that Michael's implementation is faster than mine. Anyone who cares deeply enough could of course measure. I am currently not shopping for a faster priority queue, so I will pass on that.)
>>>>
>>>> As an aside, it was a simple skew heap exercise, presented by Chris Okasaki, that made me invite Quviq to Ericsson for the first Erlang QuickCheck pilots. 
>>>>
>>>> The task was to reverse-engineer the insertion order of a particular skew heap. John Hughes solved it with a "brute force approach", using QuickCheck to test his assumptions. Watching him do exploratory hacking with QuickCheck was so much fun that, once he ported QuickCheck to Erlang, I had to try to find out if it could be put to use in a commercial project.
>>>>
>>>> Unfortunately - or fortunately - for Quviq, the only candidate for a useful pilot was stateful, and QuickCheck had no support for that. For lesser minds, that might have been a problem, but John and Thomas quickly invented the statem model. :)
>>>>
>>>> BR,
>>>> Ulf W
>>>>
>>>> On 9 Nov 2011, at 09:45, Zabrane Mickael wrote:
>>>>
>>>>> Hi Ulf,
>>>>>
>>>>> Michael Truog already has a SkewBinHeap impelmentation here:
>>>>> https://github.com/okeuday/skewbinheap
>>>>>
>>>>> Regards,
>>>>> Zabrane
>>>>>
>>>>> On Nov 9, 2011, at 9:42 AM, Ulf Wiger wrote:
>>>>>
>>>>>> I'm partial to skew heaps, mainly because they are so elegant.
>>>>>>
>>>>>> http://www.cse.yorku.ca/~andy/courses/4101/lecture-notes/LN5.pdf <http://www.cse.yorku.ca/%7Eandy/courses/4101/lecture-notes/LN5.pdf>
>>>>>>
>>>>>> Something like this (although I've done only basic testing):
>>>>>>
>>>>>> -module(skew).
>>>>>> -export([new/0, in/2, out/1]).
>>>>>>
>>>>>> new() ->
>>>>>>     [].
>>>>>>
>>>>>> in(X, Heap) ->
>>>>>>     merge({X,[],[]}, Heap).
>>>>>>
>>>>>> out([]) ->
>>>>>>     error;
>>>>>> out({X, L, R}) ->
>>>>>>     {X, merge(L, R)}.
>>>>>>
>>>>>> merge({P0,Pl,Pr}, {Q0,_,_} = Q) when P0 < Q0 ->
>>>>>>     {P0, Pr, merge(Pl,Q)};
>>>>>> merge({P0,_,_} = P, {Q0,Ql,Qr}) when P0 > Q0 ->
>>>>>>     {Q0, Qr, merge(Ql,P)};
>>>>>> merge({P0,Pl,Pr} = P,{P0,Ql,Qr}) ->   % equal roots
>>>>>>     merge(P, merge(merge(Pl,Pr), merge(Ql,Qr)));
>>>>>> merge([], Q) -> Q;
>>>>>> merge(P, []) -> P.
>>>>>>
>>>>>> The cost is amortized O(log N) for in/2 and out/1. For peeking at the min, it's O(1).
>>>>>>
>>>>>> BR,
>>>>>> Ulf W
>>>>>>
>>>>>> On 9 Nov 2011, at 04:33, Michael Truog wrote:
>>>>>>
>>>>>>> I was looking at Erlang priority queue implementations and the Riak/RabbitMQ one seemed a bit slow.  I have a different implementation with the same API here: https://github.com/okeuday/pqueue/blob/master/src/pqueue.erl
>>>>>>>
>>>>>>> The results from my test are here: http://okeuday.livejournal.com/19187.html
>>>>>>>
>>>>>>> The implementation has "in" operations that are roughly 3 times faster (300%), however, the "out" operation became roughly 30% slower.  So, as long as the priority queue is storing a decent amount of items, this data structure should provide better speed.  The implementation is limited to a specific priority range: -20 (high) to 20 (low).
>>>>>>> _______________________________________________
>>>>>>> erlang-questions mailing list
>>>>>>> erlang-questions@REDACTED <mailto:erlang-questions@REDACTED>
>>>>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>>>
>>>>>> Ulf Wiger, CTO, Erlang Solutions, Ltd.
>>>>>> http://erlang-solutions.com <http://erlang-solutions.com/>
>>>>>>
>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> erlang-questions mailing list
>>>>>> erlang-questions@REDACTED <mailto:erlang-questions@REDACTED>
>>>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>>
>>>>>
>>>>>
>>>>
>>>> Ulf Wiger, CTO, Erlang Solutions, Ltd.
>>>> http://erlang-solutions.com <http://erlang-solutions.com/>
>>>>
>>>>
>>>>
>>>
>>>   
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questions@REDACTED <mailto:erlang-questions@REDACTED>
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>
> Ulf Wiger, CTO, Erlang Solutions, Ltd.
> http://erlang-solutions.com
>
>
>

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


More information about the erlang-questions mailing list