<html><head></head><body style="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. </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="Apple-interchange-newline"><blockquote type="cite"><div style="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="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="Apple-interchange-newline"><blockquote type="cite"><div style="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="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() -></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 class="Apple-interchange-newline"><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 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 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 href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br><a 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 href="http://erlang-solutions.com/">http://erlang-solutions.com</a></div><div><br></div><br class="Apple-interchange-newline">
</div>
<br></div>_______________________________________________<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">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="Apple-style-span" style="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, CTO, Erlang Solutions, Ltd.</div><div><a href="http://erlang-solutions.com">http://erlang-solutions.com</a></div><div><br></div></span><br class="Apple-interchange-newline">
</div>
<br></body></html>