Received: by 10.204.140.198 with SMTP id j6mr781156bku.8.1320912780053;
Thu, 10 Nov 2011 00:13:00 -0800 (PST)
X-BeenThere: erlang-programming@googlegroups.com
Received: by 10.205.80.78 with SMTP id zt14ls5162688bkb.1.gmail; Thu, 10 Nov
2011 00:12:59 -0800 (PST)
Received: by 10.204.129.8 with SMTP id m8mr790802bks.5.1320912779114;
Thu, 10 Nov 2011 00:12:59 -0800 (PST)
Received: by 10.204.129.8 with SMTP id m8mr790801bks.5.1320912779097;
Thu, 10 Nov 2011 00:12:59 -0800 (PST)
Return-Path: <erlang-questions-boun...@erlang.org>
Received: from hades.cslab.ericsson.net (hades.cslab.ericsson.net. [192.121.151.104])
by gmr-mx.google.com with ESMTP id j1si1248176bky.2.2011.11.10.00.12.58;
Thu, 10 Nov 2011 00:12:59 -0800 (PST)
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;
Authentication-Results: gmr-mx.google.com; spf=pass (google.com: domain of erlang-questions-boun...@erlang.org designates 192.121.151.104 as permitted sender) smtp.mail=erlang-questions-boun...@erlang.org; dkim=neutral (body hash did not verify) header...@messagingengine.com
Received: from hades.cslab.ericsson.net (hades [192.121.151.104])
by hades.cslab.ericsson.net (Postfix) with ESMTP id A09295C1AD;
Thu, 10 Nov 2011 09:12:51 +0100 (CET)
X-Original-To: erlang-questi...@erlang.org
Delivered-To: erlang-questi...@erlang.org
Received: from out2.smtp.messagingengine.com (out2.smtp.messagingengine.com
[66.111.4.26])
by hades.cslab.ericsson.net (Postfix) with ESMTP id A040B5C00C
for <erlang-questi...@erlang.org>; Thu, 10 Nov 2011 09:12:49 +0100 (CET)
Received: from compute5.internal (compute5.nyi.mail.srv.osa [10.202.2.45])
by gateway1.nyi.mail.srv.osa (Postfix) with ESMTP id 284AD21229
for <erlang-questi...@erlang.org>; Thu, 10 Nov 2011 03:12:49 -0500 (EST)
Received: from frontend1.nyi.mail.srv.osa ([10.202.2.160])
by compute5.internal (MEProxy); Thu, 10 Nov 2011 03:12:49 -0500
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=
messagingengine.com; h=message-id:date:from:mime-version:to:cc
:subject:references:in-reply-to:content-type; s=smtpout; bh=ceiM
PCSstfMY5HqpclJnc2xNTPo=; b=STQTn2jRseTLxox+LbFTmlfeuzZRg/O6gmx0
gIqftmTSLi4GV2gYzvNXPgoG4vy47yVWzmweidwTf7/bRNpxsHbjlLfvvuAnWo03
5NRObUoGNdCseQdlOWYRC+RNdbzWDfNJPzU1E3WH1LXuZHyNHbwMN6uI0ME++9mD
Ap35U6Y=
X-Sasl-enc: Wh7RxZ78S4IaHEtGj1WK8Y63Us0xXbWrU0JUEWtn/Fvd 1320912768
Received: from [192.168.2.4] (97-113-255-212.tukw.qwest.net [97.113.255.212])
by mail.messagingengine.com (Postfix) with ESMTPSA id 2C19F8E00D9;
Thu, 10 Nov 2011 03:12:47 -0500 (EST)
Message-ID: <4EBB877E.9020...@gmail.com>
Date: Thu, 10 Nov 2011 00:12:46 -0800
From: Michael Truog <mjtr...@gmail.com>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US;
rv:1.9.2.13) Gecko/20101208 Thunderbird/3.1.7
MIME-Version: 1.0
To: Ulf Wiger <ulf.wi...@erlang-solutions.com>
References: <4EB9F477.9040...@gmail.com>
<DBF1E381-27E6-412A-9887-8E5B41F1D...@erlang-solutions.com>
<3EF316E5-ADB4-4D50-AC04-A7F8B1EA9...@gmail.com>
<AD5ABC43-3687-40DD-972E-E6FFF6996...@erlang-solutions.com>
<4EBAB14E.2080...@gmail.com> <4EBB8120.2060...@gmail.com>
<756EEC5C-E42B-435D-B343-2A41A5A91...@erlang-solutions.com>
In-Reply-To: <756EEC5C-E42B-435D-B343-2A41A5A91...@erlang-solutions.com>
Cc: erlang-questions Questions <erlang-questi...@erlang.org>
Subject: Re: [erlang-questions] [ANN] Priority Queue Implementation
X-BeenThere: erlang-questi...@erlang.org
X-Mailman-Version: 2.1.14
Precedence: list
List-Id: General Erlang/OTP discussions <erlang-questions.erlang.org>
List-Unsubscribe: <http://erlang.org/mailman/options/erlang-questions>,
<mailto:erlang-questions-requ...@erlang.org?subject=unsubscribe>
List-Archive: <http://erlang.org/pipermail/erlang-questions>
List-Post: <mailto:erlang-questi...@erlang.org>
List-Help: <mailto:erlang-questions-requ...@erlang.org?subject=help>
List-Subscribe: <http://erlang.org/mailman/listinfo/erlang-questions>,
<mailto:erlang-questions-requ...@erlang.org?subject=subscribe>
Content-Type: multipart/mixed; boundary="===============6561970997866178655=="
Errors-To: erlang-questions-boun...@erlang.org
Sender: erlang-questions-boun...@erlang.org
This is a multi-part message in MIME format.
--===============6561970997866178655==
Content-Type: multipart/alternative;
boundary="------------010208040900000405060400"
This is a multi-part message in MIME format.
--------------010208040900000405060400
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 8bit
I previously added code that took care of that case, where two nodes needed to be merged that both have queues. However, I convinced myself at the time, that the case would never happen. So, the code probably needs to be thought-through a bit more with more testing, but my hope is that merging the queues isn't necessary. I haven't been able to crash the data structure without that case while using many priorities, but it still requires investigation.
On 11/10/2011 12:01 AM, Ulf Wiger wrote:
>
> Always nice when the simplest approaches prove to be among the fastest. :)
>
> 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�
>
> BR,
> Ulf W
>
> On 10 Nov 2011, at 08:45, Michael Truog wrote:
>
>> 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:
>> https://github.com/okeuday/pqueue/blob/master/src/pqueue2.erl
>>
>> 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)):
>> TEST run_priority_queue
>> N == 1000000 (10 runs)
>> pqueue get: 481774.3 �s ( 1.4), set: 525589.1 �s ( 1.0)
>> pqueue2 get: 332711.2 �s ( 1.0), set: 680209.0 �s ( 1.3)
>> priority_queue get: 362588.9 �s ( 1.1), set: 1443674.2 �s ( 2.7)
>>
>>
>> On 11/09/2011 08:58 AM, Michael Truog wrote:
>>> 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.
>>>
>>> On 11/09/2011 01:00 AM, Ulf Wiger wrote:
>>>>
>>>> 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 <http://www.cse.yorku.ca/%7Eandy/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-questi...@erlang.org <mailto:erlang-questi...@erlang.org>
>>>>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>>>
>>>>>> Ulf Wiger, CTO, Erlang Solutions, Ltd.
>>>>>> http://erlang-solutions.com <http://erlang-solutions.com/>
>>>>>>
>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> erlang-questions mailing list
>>>>>> erlang-questi...@erlang.org <mailto:erlang-questi...@erlang.org>
>>>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>>
>>>>>
>>>>>
>>>>
>>>> Ulf Wiger, CTO, Erlang Solutions, Ltd.
>>>> http://erlang-solutions.com <http://erlang-solutions.com/>
>>>>
>>>>
>>>>
>>>
>>>
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questi...@erlang.org <mailto:erlang-questi...@erlang.org>
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>
> Ulf Wiger, CTO, Erlang Solutions, Ltd.
> http://erlang-solutions.com
>
>
>
--------------010208040900000405060400
Content-Type: text/html; charset=windows-1252
Content-Transfer-Encoding: 8bit
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
I previously added code that took care of that case, where two nodes
needed to be merged that both have queues.� However, I convinced
myself at the time, that the case would never happen.� So, the code
probably needs to be thought-through a bit more with more testing,
but my hope is that merging the queues isn't necessary.� I haven't
been able to crash the data structure without that case while using
many priorities, but it still requires investigation.<br>
<br>
On 11/10/2011 12:01 AM, Ulf Wiger wrote:
<blockquote
cite="mid:756EEC5C-E42B-435D-B343-2A41A5A91...@erlang-solutions.com"
type="cite">
<meta http-equiv="Context-Type" content="text/html;
charset=windows-1252">
<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>
<blockquote type="cite">
<div> 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 moz-do-not-send="true"
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.2080...@gmail.com"
type="cite"> 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-E6FFF6996...@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-questi...@erlang.org">erlang-questi...@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-questi...@erlang.org">erlang-questi...@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>
_______________________________________________
erlang-questions mailing list
<a moz-do-not-send="true" href="mailto:erlang-questi...@erlang.org">erlang-questi...@erlang.org</a>
<a moz-do-not-send="true" 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>
<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>
--------------010208040900000405060400--
--===============6561970997866178655==
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
--===============6561970997866178655==--
Message from discussion [ANN] Priority Queue Implementation
| Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy |
| ©2013 Google |