Priority Queue

[Dan H.]

Hello,
I have implemented a C# priority queue using an ArrayList. The objects
being inserted into the priority queue are being sorted by 2 fields, Time
(ulong) and Priority (0-100).

When I enqueue, I do a binary search on where to put the object and then
insert using that index and arraylist.insert(index, obj)

The bottom of my arraylist is always my lowest, therefore, dequeueing is
very fast and effecient.

Removing is done using a binary search as well and calling the
arraylist.remove.

I need to optimize my priorityqueue implementatation further. Here are a
couple of questions I have:

1. Would it be faster to just use C# array instead of ArrayList?
2. Anyone else have some C# priority queue approaches they would be willing
to share/discuss?

Thanks in advanced,
Dan

 

[Jay B. Harlow [MVP - Outlook]]

Dan,
Its been a while since I played with Priority Queues.

Would not a System.Collections.SortedList of System.Collections.Queue be
easier?

Each priority is an item in the SortedList, each item is a Queue.

I would key the SortedList by the priority, allowing easy retrieval &
indexing, while the Queue objects would take care of themselves.

I would encapsulate both in objects in a class or two to hide the actual
implementation details.

To add Items, I would look for the priority by key in the SortedList,
returning the queue, I would then add the item to the end of the queue. If
the item is not found I would create a new queue adding it to the
SortedList.

To remove items, the first ordinal position (element 0) in the SortedList is
the first queue, I would just dequeue the item. If the queue is now empty, I
would remove it from the SortedList.

Of course it may have been TOO long since I've used Priority Queues ;-)

The 'problem' is going to be if the Priority is an Integer, as you will need
to be specific to let the SortedList know when you are indexing by key or by
ordinal position.

Hope this helps
Jay

 

[William Stacey]

Thinking out loud...
Although you save using the binary search, you pay a couple different taxes
here. You pay on the overhead of both binary searches, you pay on
ArrayList.Insert() and RemoveAt() for every call as internally they do an
Array.Copy to adjust the internal array. Insert() will also allocate (by
2x) a new array and do an Array.Copy if it needs to grow.

So this may be faster, but would need to be perf tested.
Option1-
Use an ArrayList for you internal queue. Enqueue (and dequeue) your objects
using a struct or Class that you create that holds the priority, time, and
object fields. Your IComparer can be in this class. Enqueue the object and
sort the array using your IComparer in reverse and adjust your Enqueue and
Dequeue methods accordingly. Use reverse as removing the last element of an
arraylist will avoid the last Array.Copy and just set the last element to
null.

Option2-
Use object[] as your internal array for queue. Setup your queue as a
circular queue with head, tail, etc. If your producer's and consumer's will
be mostly even, then you can use a fixed length array to avoid growing, then
just sync your queue with wait()'s on gets and puts, etc. In a
producer/consumer, this is probably the way you want to go anyway, as your
producer will want to wait for more input on an empty queue (or a closed
flag) and not just return empty. Every Enqueue() will add the element and
sort the array ascending with your IComparer so your head element will
always be the next one for the next Dequeue(). As this is circular, you
don't need to copy the array or reallocate it in either case - just move the
head or tail ptr in your enqueue and dequeue (very fast). If you do want or
need to grow the array, just do it by a default or user supplied growth
factor during Enqueue(). So the only tax you pay here is the Sort in
Enqueue. And if your queue is small, this will be fast and maybe faster
then a binary search depending on the size. Overall, I would guess this
will be faster then the two binary searches, the allocations and the
Array.Copy's using the ArrayList method. The downside is, they both need to
be built and tested to discern the speed difference.

 

[William Stacey]

Option2-

Use object[] as your internal array for queue. Setup your queue as a
circular queue with head, tail, etc. If your producer's and consumer's will
be mostly even, then you can use a fixed length array to avoid growing,

then
....

There is another optimization here that I just thought about. Put the sort
logic in the Dequeue, not the Enqueue and use a "isSorted" flag. This
allows you to leverage the sort after you add your last element (Enqueue)
and with multiple Enqueues in a row (with not dequeue's in between.) So if
you add 10 elements and then start the dequeue, you only sort once and the
dequeues just grab the next element - no sort needed after the first. Set
the flag back to false after each Enqueue. hth

 

[Dan H.]

Thanks for the replies. I am digesting them now, but I just wanted to say
thanks for the info. Hopefully I can put together a small test harness to
test speeds soon.

Thanks,

dan

 

[George C]

hi Jay,
that is not a valid approach. Keys in SortedList are expected to be
unique, while priorities are not. Many problems would arise from this,
and their resolving would probably require more effort than Dan's
ArrayList approach.
--GC