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, MVP
"Dan H." <Da**@projectavatar.com> wrote in message
news:#N**************@TK2MSFTNGP12.phx.gbl...
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