[erlang-questions] [ANN] Priority Queue Implementation

[Ulf Wiger]

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
>> 
>> 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
>>> http://erlang.org/mailman/listinfo/erlang-questions
>> 
>> Ulf Wiger, CTO, Erlang Solutions, Ltd.
>> http://erlang-solutions.com
>> 
>> 
>> 
>> _______________________________________________
>> erlang-questions mailing list
>> 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/20111109/d30f31e2/attachment.htm>