[erlang-questions] Priority queue

Eranga Udesh casper2000a@REDACTED
Fri Jul 6 17:53:49 CEST 2007


Instead you can use an ets table with ordered_set and use ets:first/1 or
ets:last/1 to get the prioritized messages. But still this is an expensive
task in terms of insertion and retrieval (2nd and 3rd reasons below).

A simple solution would be to extend Erlang process/message passing model to
enable to originate priority and normal type messages. When it's a priority
message, the message is placed at the beginning (head) of the queue. When
it's a normal message, it's placed at the end of the queue.

Taking gen_server as an exmaple there're 2 functions,
	gen_server:pri_call/2/3
	gen_server:pri_cast/2
when run, it places the new message at the beginning of the message queue to
the gen_server process?

This doesn't preserve the FIFO for priority messages (but LIFO), but at
least it could give the facility to deliver a high priority message to a
process without waiting for its turn in the message queue.

BRgds,
- Eranga



-----Original Message-----
From: erlang-questions-bounces@REDACTED
[mailto:erlang-questions-bounces@REDACTED] On Behalf Of Eranga Udesh
Sent: Friday, July 06, 2007 8:47 PM
To: yerl@REDACTED; ulf.wiger@REDACTED;
erlang-questions@REDACTED
Subject: Re: [erlang-questions] Priority queue

Well, gb_trees are created in process heap. Therefore between 2 processes
you cannot have a shared gb_tree. So, one process cannot add messages while
the other retrieves.

Also gb_trees is O(log n) complex. Hence it's not like queue where messages
are entered from one side (tail) and read from the other side (head). It's a
complex task than a plain message queue, which is O(1). Also a process has
to constantly query a gb_tree to see if a message is available. 

Ideally, a process waits until a message is put in to its input stream.

Pls correct me if I am wrong.

BRgds,
- Eranga



-----Original Message-----
From: yerl@REDACTED [mailto:yerl@REDACTED] 
Sent: Friday, July 06, 2007 6:42 PM
To: casper2000a@REDACTED; ulf.wiger@REDACTED;
erlang-questions@REDACTED
Subject: Re: RE: [erlang-questions] Priority queue

As pointed by Ulf for priority queues, just use "gb_trees".

What do you mean by "efficient message retrieval" ?
Explain further your problem.

cheers
Y.

Explain further your problem? What do you want to 

----Message d'origine----
>De: "Eranga Udesh" <casper2000a@REDACTED>
>A: "'Ulf Wiger \(TN/EAB\)'" <ulf.wiger@REDACTED>,
>	"'Yerl'" <yerl@REDACTED>,
>	<erlang-questions@REDACTED>
>Sujet: RE: [erlang-questions] Priority queue
>Date: Fri, 6 Jul 2007 17:43:09 +0530
>
>How to handle Priority Queues between processes, while keeping efficient
>message retrieval?
>
>BRgds,
>- Eranga
>
>
>-----Original Message-----
>From: erlang-questions-bounces@REDACTED
>[mailto:erlang-questions-bounces@REDACTED] On Behalf Of Ulf Wiger
(TN/EAB)
>Sent: Thursday, June 28, 2007 2:17 AM
>To: Yerl; erlang-questions@REDACTED
>Subject: Re: [erlang-questions] Priority queue
>
>
>You can use a gb_trees structure:
>
>in(Item, Prio, Q) ->
>   gb_trees:insert({Prio,now()}, Item, Q).
>
>out(Q) ->
>   gb_trees:take_smallest(Q).
>
>peek(Q) ->
>   gb_trees:smallest(Q).
>
>The order will be FIFO. If you want LIFO, you 
>could negate the Prio value and take_largest
>instead.
>
>BR,
>Ulf W
>
>> -----Original Message-----
>> From: erlang-questions-bounces@REDACTED 
>> [mailto:erlang-questions-bounces@REDACTED] On Behalf Of Yerl
>> Sent: den 27 juni 2007 20:56
>> To: erlang-questions@REDACTED
>> Subject: [erlang-questions] Priority queue
>> 
>> Hi Folks!
>> 
>> I'm looking for a robust implementation of "Priority queue"
>> (http://en.wikipedia.org/wiki/Priority_queue) in Erlang.
>> 
>> Any pointer?
>> 
>> cheers
>> Y.
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://www.erlang.org/mailman/listinfo/erlang-questions
>> 
>_______________________________________________
>erlang-questions mailing list
>erlang-questions@REDACTED
>http://www.erlang.org/mailman/listinfo/erlang-questions
>
>


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




More information about the erlang-questions mailing list