<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><br></div><div>Always nice when the simplest approaches prove to be among the fastest. :)</div><div><br></div><div>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…</div><div><br></div><div>BR,</div><div>Ulf W</div><br><div><div>On 10 Nov 2011, at 08:45, Michael Truog wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">

  
    <meta content="text/html; charset=ISO-8859-1" http-equiv="Content-Type">
  
  <div bgcolor="#ffffff" text="#000000">
    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:<br>
    <a class="moz-txt-link-freetext" href="https://github.com/okeuday/pqueue/blob/master/src/pqueue2.erl">https://github.com/okeuday/pqueue/blob/master/src/pqueue2.erl</a><br>
    <br>
    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)):<br>
    TEST run_priority_queue<br>
    N == 1000000 (10 runs)<br>
                  pqueue get:   481774.3 µs (  1.4), set:   525589.1 µs
    (  1.0)<br>
                 pqueue2 get:   332711.2 µs (  1.0), set:   680209.0 µs
    (  1.3)<br>
          priority_queue get:   362588.9 µs (  1.1), set:  1443674.2 µs
    (  2.7)<br>
    <br>
    <br>
    On 11/09/2011 08:58 AM, Michael Truog wrote:
    <blockquote cite="mid:4EBAB14E.2080805@gmail.com" type="cite">
      <meta http-equiv="Context-Type" content="text/html;
        charset=ISO-8859-1">
      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">
        <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>
      <pre wrap=""><fieldset class="mimeAttachmentHeader"></fieldset>
_______________________________________________
erlang-questions mailing list
<a class="moz-txt-link-abbreviated" href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>
<a class="moz-txt-link-freetext" href="http://erlang.org/mailman/listinfo/erlang-questions">http://erlang.org/mailman/listinfo/erlang-questions</a>
</pre>
    </blockquote>
    <br>
  </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>