[erlang-questions] Priority queue

Eranga Udesh <>
Fri Jul 6 18:47:35 CEST 2007


Alright, I wasn't thinking this model. 

This receive loop doesn't wait at any level, hence seems CPU intensive.
However this can be improved.

Thanks,
- Eranga


-----Original Message-----
From: 
[mailto:] On Behalf Of David Mercer
Sent: Friday, July 06, 2007 9:16 PM
To: 
Subject: Re: [erlang-questions] Priority queue

I would guess you'd use Mr. Wiger's functions in some sort of receive loop.
Something like (I did not test this or even make sure it compiles, but it
gives an idea of what I thought Mr. Wiger was saying):

priority_receive(Queue) ->
	receive
		{Priority, Message} ->
			in(Message, Priority, Queue)
		after 0 ->
			process_message(out(Queue))
	end,
	priority_receive(Queue).


-----Original Message-----
From: 
[mailto:] On Behalf Of Eranga Udesh
Sent: Friday, July 06, 2007 10:17
To: ; ;

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:  [mailto:] 
Sent: Friday, July 06, 2007 6:42 PM
To: ; ;

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" <>
>A: "'Ulf Wiger \(TN/EAB\)'" <>,
>	"'Yerl'" <>,
>	<>
>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: 
>[mailto:] On Behalf Of Ulf Wiger
(TN/EAB)
>Sent: Thursday, June 28, 2007 2:17 AM
>To: Yerl; 
>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:  
>> [mailto:] On Behalf Of Yerl
>> Sent: den 27 juni 2007 20:56
>> To: 
>> 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
>> 
>> http://www.erlang.org/mailman/listinfo/erlang-questions
>> 
>_______________________________________________
>erlang-questions mailing list
>
>http://www.erlang.org/mailman/listinfo/erlang-questions
>
>


_______________________________________________
erlang-questions mailing list

http://www.erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list

http://www.erlang.org/mailman/listinfo/erlang-questions




More information about the erlang-questions mailing list