<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
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.<br>
<br>
On 11/09/2011 01:00 AM, Ulf Wiger wrote:
<blockquote
cite="mid:AD5ABC43-3687-40DD-972E-E6FFF69965F4@erlang-solutions.com"
type="cite">
<meta http-equiv="Context-Type" content="text/html;
charset=us-ascii">
<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. </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>
<blockquote type="cite">
<div>Hi Ulf,
<div><br>
</div>
<div>Michael Truog already has a SkewBinHeap impelmentation
here:</div>
<div><a moz-do-not-send="true"
href="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>
<blockquote type="cite">
<div>
<div>I'm partial to skew heaps, mainly because they
are so elegant.</div>
<div><br>
</div>
<div><a moz-do-not-send="true"
href="http://www.cse.yorku.ca/%7Eandy/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() -></div>
<div> [].</div>
<div><br>
</div>
<div>in(X, Heap) -></div>
<div> merge({X,[],[]}, Heap).</div>
<div><br>
</div>
<div>out([]) -></div>
<div> error;</div>
<div>out({X, L, R}) -></div>
<div> {X, merge(L, R)}.</div>
<div><br>
</div>
<div>merge({P0,Pl,Pr}, {Q0,_,_} = Q) when P0 <
Q0 -></div>
<div> {P0, Pr, merge(Pl,Q)};</div>
<div>merge({P0,_,_} = P, {Q0,Ql,Qr}) when P0 >
Q0 -></div>
<div> {Q0, Qr, merge(Ql,P)};</div>
<div>
<div>merge({P0,Pl,Pr} = P,{P0,Ql,Qr}) -> %
equal roots</div>
<div> merge(P, merge(merge(Pl,Pr),
merge(Ql,Qr)));</div>
</div>
<div>merge([], Q) -> Q;</div>
<div>merge(P, []) -> 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>
<blockquote type="cite">
<div>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: <a
moz-do-not-send="true"
href="https://github.com/okeuday/pqueue/blob/master/src/pqueue.erl">https://github.com/okeuday/pqueue/blob/master/src/pqueue.erl</a><br>
<br>
The results from my test are here: <a
moz-do-not-send="true"
href="http://okeuday.livejournal.com/19187.html">http://okeuday.livejournal.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.
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).<br>
_______________________________________________<br>
erlang-questions mailing list<br>
<a moz-do-not-send="true"
href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a moz-do-not-send="true"
href="http://erlang.org/mailman/listinfo/erlang-questions">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
</div>
</blockquote>
</div>
<br>
<div>
<div>Ulf Wiger, CTO, Erlang Solutions, Ltd.</div>
<div><a moz-do-not-send="true"
href="http://erlang-solutions.com/">http://erlang-solutions.com</a></div>
<div><br>
</div>
<br>
</div>
<br>
</div>
_______________________________________________<br>
erlang-questions mailing list<br>
<a moz-do-not-send="true"
href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a moz-do-not-send="true"
href="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>
<div>Ulf Wiger, CTO, Erlang Solutions, Ltd.</div>
<div><a moz-do-not-send="true"
href="http://erlang-solutions.com">http://erlang-solutions.com</a></div>
<div><br>
</div>
</span><br>
</div>
<br>
</blockquote>
<br>
</body>
</html>