Priority Queues

[Rudolph van Graan]

Hi Ulf,

Thank you for the information below. I have tested code similar to  
yours below and for the moment I'm happy.

Regards,

Rudolph

On 16 May 2005, at 2:29 PM, Ulf Wiger ((AL/EAB)) wrote:

>
> You can do this (almost) using an ordered_set disc_copy
> table in mnesia. The object key could be e.g.
> {Priority, erlang:now()} for prioritized FIFO, or
> {Priority, negative(erlang:now())} for prioritized LIFO,
> where
>
> negative({MSec, Sec, MuSec}) ->
>   {-MSec, -Sec, -MySec}.
>
>
> 1) Using dirty_first(Tab) and dirty_last(Tab), you can
>    get to the first and last entries respectively.
>
> 2) The structure of the key determines the ordering.
>    See above.
>
> 3) Not a big problem, but the entries will all be in
>    RAM (and logged to disk periodically)
>
> 4) Not constant time, but close enough (logN)
>
> 5) Persistence is taken care of by mnesia
>
> 6) To make this thread-safe, you need to either
>    serialize the operation using a server, or use
>    mnesia transactions. The transaction can for example
>    return the next value for processing like so:
>
>    mnesia:activity(
>         dirty,
>         fun() ->
>             case mnesia:dirty_first(prio_queue) of
>                 '$end_of_table' -> queue_empty;
>                 Key ->
>                     [Result] = mnesia:read(prio_queue, Key, write),
>                     mnesia:delete(prio_queue, Key)
>                     Result
>             end
>         end).
>
> It's a little trickier if you want full atomicity, since there
> is no mnesia:first/1. You can still do it like described above,
> since you get synchronization on the read, and thus avoid the
> risk of race conditions or lost updates. However, you can get
> aborted transactions instead of proper serialization.
>
> It's possible to use mnesia:select(Tab, Pattern, 1, write),
> which will, on an ordered_set, return the first object in the
> table matching Pattern, but it will be slightly more expensive
> (esp. if this operation is called as a nested transaction, since
> the select() call has to scan the transaction store.)
>
> Of course, the overhead of using transactions will be significant,
> but mnesia:activity(dirty, ...) is not so bad. It's a very handy
> way of packaging dirty operations.
>
> /Uffe
>
>
>> -----Original Message-----
>> From: owner-erlang-questions@REDACTED
>> [mailto:owner-erlang-questions@REDACTED]On Behalf Of
>> Rudolph van Graan
>> Sent: den 16 maj 2005 08:24
>> To: Erlang Questions
>> Subject: Priority Queues
>>
>>
>> Hi All,
>>
>> I am currently thinking about the implementation of priority queues
>> in erlang. Specifically, what do you guys suggest as an
>> efficient way
>> to achieve the following:
>>
>> 1. A queue with a definitive head and tail (i.e. first and
>> last records)
>> 2. The items in the queue need to be sorted according to some
>> criteria that will always allow you to identify an entry as the
>> "first" or "next" one
>> 3. The queue length can be massive (100's of thousands or
>> millions of
>> records)
>> 4. Insertion time should be constant
>> 5. The queue must be persistent (i.e. mnesia or dets)
>> 6. Once the first/head entry has been processed, it will no
>> longer be
>> in the queue.
>>
>> Any suggestions?
>>
>> Rudolph van Graan
>>
>>
>>
>
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2373 bytes
Desc: not available
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20050518/51256e1c/attachment.bin>