[ANN] Priority Queue Implementation - Erlang Programming

The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion [ANN] Priority Queue Implementation
Received-SPF: pass (google.com: domain of erlang-questions-boun...@erlang.org designates 192.121.151.104 as permitted sender) client-ip=192.121.151.104;
Mime-Version: 1.0 (Apple Message framework v1084)
From: Ulf Wiger <ulf.wi...@erlang-solutions.com>
In-Reply-To: <3EF316E5-ADB4-4D50-AC04-A7F8B1EA9...@gmail.com>
Date: Wed, 9 Nov 2011 10:00:07 +0100
Message-Id: <AD5ABC43-3687-40DD-972E-E6FFF6996...@erlang-solutions.com>
References: <4EB9F477.9040...@gmail.com>
 <DBF1E381-27E6-412A-9887-8E5B41F1D...@erlang-solutions.com>
 <3EF316E5-ADB4-4D50-AC04-A7F8B1EA9...@gmail.com>
To: Zabrane Mickael <zabra...@gmail.com>
Cc: erlang-questions Questions <erlang-questi...@erlang.org>
Subject: Re: [erlang-questions] [ANN] Priority Queue Implementation
Precedence: list
Content-Type: multipart/mixed; boundary="===============3596171103179496351=="
Errors-To: erlang-questions-boun...@erlang.org
Sender: erlang-questions-boun...@erlang.org


--===============3596171103179496351==
Content-Type: multipart/alternative; boundary=Apple-Mail-17-1072107767


--Apple-Mail-17-1072107767
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii


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.=20

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,
>=20
> Michael Truog already has a SkewBinHeap impelmentation here:
> https://github.com/okeuday/skewbinheap
>=20
> Regards,
> Zabrane
>=20
> On Nov 9, 2011, at 9:42 AM, Ulf Wiger wrote:
>=20
>> I'm partial to skew heaps, mainly because they are so elegant.
>>=20
>> http://www.cse.yorku.ca/~andy/courses/4101/lecture-notes/LN5.pdf
>>=20
>> Something like this (although I've done only basic testing):
>>=20
>> -module(skew).
>> -export([new/0, in/2, out/1]).
>>=20
>> new() ->
>>     [].
>>=20
>> in(X, Heap) ->
>>     merge({X,[],[]}, Heap).
>>=20
>> out([]) ->
>>     error;
>> out({X, L, R}) ->
>>     {X, merge(L, R)}.
>>=20
>> merge({P0,Pl,Pr}, {Q0,_,_} =3D Q) when P0 < Q0 ->
>>     {P0, Pr, merge(Pl,Q)};
>> merge({P0,_,_} =3D P, {Q0,Ql,Qr}) when P0 > Q0 ->
>>     {Q0, Qr, merge(Ql,P)};
>> merge({P0,Pl,Pr} =3D P,{P0,Ql,Qr}) ->   % equal roots
>>     merge(P, merge(merge(Pl,Pr), merge(Ql,Qr)));
>> merge([], Q) -> Q;
>> merge(P, []) -> P.
>>=20
>> The cost is amortized O(log N) for in/2 and out/1. For peeking at the =
min, it's O(1).
>>=20
>> BR,
>> Ulf W
>>=20
>> On 9 Nov 2011, at 04:33, Michael Truog wrote:
>>=20
>>> 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
>>>=20
>>> The results from my test are here: =
http://okeuday.livejournal.com/19187.html
>>>=20
>>> 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-questi...@erlang.org
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>=20
>> Ulf Wiger, CTO, Erlang Solutions, Ltd.
>> http://erlang-solutions.com
>>=20
>>=20
>>=20
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questi...@erlang.org
>> http://erlang.org/mailman/listinfo/erlang-questions
>=20
>=20
>=20

Ulf Wiger, CTO, Erlang Solutions, Ltd.
http://erlang-solutions.com




--Apple-Mail-17-1072107767
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
	charset=us-ascii

<html><head></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space; =
"><div><br></div><div>Yeah, obviously, mine was just a sketch, thrown =
down as an executable comment and optimized for brevity. =
:)</div><div><br></div><div>(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.)</div><div><br></div><div>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.&nbsp;</div><div><br></div><div>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.</div><div><br></div><div>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. =
:)</div><div><br></div><div>BR,</div><div>Ulf =
W</div><div><br></div><div>On 9 Nov 2011, at 09:45, Zabrane Mickael =
wrote:</div><div><br class=3D"Apple-interchange-newline"><blockquote =
type=3D"cite"><div style=3D"word-wrap: break-word; -webkit-nbsp-mode: =
space; -webkit-line-break: after-white-space; ">Hi =
Ulf,<div><br></div><div>Michael Truog already has a SkewBinHeap =
impelmentation here:</div><div><a =
href=3D"https://github.com/okeuday/skewbinheap">https://github.com/okeuday=
/skewbinheap</a></div><div><br></div><div><div>Regards,</div><div>Zabrane<=
/div><div><br></div><div><div>On Nov 9, 2011, at 9:42 AM, Ulf Wiger =
wrote:</div><br class=3D"Apple-interchange-newline"><blockquote =
type=3D"cite"><div style=3D"word-wrap: break-word; -webkit-nbsp-mode: =
space; -webkit-line-break: after-white-space; "><div>I'm partial to skew =
heaps, mainly because they are so elegant.</div><div><br></div><div><a =
href=3D"http://www.cse.yorku.ca/~andy/courses/4101/lecture-notes/LN5.pdf">=
http://www.cse.yorku.ca/~andy/courses/4101/lecture-notes/LN5.pdf</a></div>=
<div><br></div><div>Something like this (although I've done only basic =
testing):</div><div><br></div><div><div>-module(skew).</div><div>-export([=
new/0, in/2, out/1]).</div><div><br></div><div>new() =
-&gt;</div><div>&nbsp; &nbsp; [].</div><div><br></div><div>in(X, Heap) =
-&gt;</div><div>&nbsp; &nbsp; merge({X,[],[]}, =
Heap).</div><div><br></div><div>out([]) -&gt;</div><div>&nbsp; &nbsp; =
error;</div><div>out({X, L, R}) -&gt;</div><div>&nbsp; &nbsp; {X, =
merge(L, R)}.</div><div><br></div><div>merge({P0,Pl,Pr}, {Q0,_,_} =3D Q) =
when P0 &lt; Q0 -&gt;</div><div>&nbsp; &nbsp; {P0, Pr, =
merge(Pl,Q)};</div><div>merge({P0,_,_} =3D P, {Q0,Ql,Qr}) when P0 &gt; =
Q0 -&gt;</div><div>&nbsp; &nbsp; {Q0, Qr, =
merge(Ql,P)};</div><div><div>merge({P0,Pl,Pr} =3D P,{P0,Ql,Qr}) -&gt; =
&nbsp; % equal roots</div><div>&nbsp; &nbsp; merge(P, =
merge(merge(Pl,Pr), merge(Ql,Qr)));</div></div><div>merge([], Q) -&gt; =
Q;</div><div>merge(P, []) -&gt; P.</div></div><div><br></div><div>The =
cost is amortized O(log N) for in/2 and out/1. For peeking at the min, =
it's O(1).</div><div><br></div><div>BR,</div><div>Ulf =
W</div><br><div><div>On 9 Nov 2011, at 04:33, Michael Truog =
wrote:</div><br class=3D"Apple-interchange-newline"><blockquote =
type=3D"cite"><div>I was looking at Erlang priority queue =
implementations and the Riak/RabbitMQ one seemed a bit slow. &nbsp;I =
have a different implementation with the same API here: <a =
href=3D"https://github.com/okeuday/pqueue/blob/master/src/pqueue.erl">http=
s://github.com/okeuday/pqueue/blob/master/src/pqueue.erl</a><br><br>The =
results from my test are here: <a =
href=3D"http://okeuday.livejournal.com/19187.html">http://okeuday.livejour=
nal.com/19187.html</a><br><br>The implementation has "in" operations =
that are roughly 3 times faster (300%), however, the "out" operation =
became roughly 30% slower. &nbsp;So, as long as the priority queue is =
storing a decent amount of items, this data structure should provide =
better speed. &nbsp;The implementation is limited to a specific priority =
range: -20 (high) to 20 =
(low).<br>_______________________________________________<br>erlang-questi=
ons mailing list<br><a =
href=3D"mailto:erlang-questi...@erlang.org">erlang-questi...@erlang.org</a=
><br><a =
href=3D"http://erlang.org/mailman/listinfo/erlang-questions">http://erlang=
.org/mailman/listinfo/erlang-questions</a><br></div></blockquote></div><br=
><div>
<div>Ulf Wiger,&nbsp;CTO, Erlang Solutions, Ltd.</div><div><a =
href=3D"http://erlang-solutions.com/">http://erlang-solutions.com</a></div=
><div><br></div><br class=3D"Apple-interchange-newline">
</div>
=
<br></div>_______________________________________________<br>erlang-questi=
ons mailing list<br><a =
href=3D"mailto:erlang-questi...@erlang.org">erlang-questi...@erlang.org</a=
><br><a =
href=3D"http://erlang.org/mailman/listinfo/erlang-questions">http://erlang=
.org/mailman/listinfo/erlang-questions</a><br></blockquote></div><br><div>=

<div><br></div>
</div>
<br></div></div></blockquote></div><br><div>
<span class=3D"Apple-style-span" style=3D"border-collapse: separate; =
color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; =
font-variant: normal; font-weight: normal; letter-spacing: normal; =
line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; =
text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; =
-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: =
0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: =
auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div>Ulf =
Wiger,&nbsp;CTO, Erlang Solutions, Ltd.</div><div><a =
href=3D"http://erlang-solutions.com">http://erlang-solutions.com</a></div>=
<div><br></div></span><br class=3D"Apple-interchange-newline">
</div>
<br></body></html>=

--Apple-Mail-17-1072107767--

--===============3596171103179496351==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
erlang-questions mailing list
erlang-questi...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions

--===============3596171103179496351==--
Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
Account Options
