Chad Stansbury wrote:
I suspect you're right - the Linked List has the added expense of
instantiating a Node for every object you add to it, so even though it's
O(1) for adds and removes from the head and/or tail, it's got a much higher
constant than ArrayList - which is has O(n) for adds/removes from the
head/tail. You mentioned small queues - I suspect that once your queue size
(n) became large enough, the LinkedList would begin winning out over the
ArrayList...
It would be interesting to find that threshold, but it is good practice to
minimize the size of the queues if at all possible. Sometimes there are
cases that cannot be helped such as slow connections not allowing events
to be dequeued fast enough, etc. Sometimes that effect can be minimized
using concurrency.
Berin Loritsch wrote:
Chad Stansbury wrote:
Also, for the FixedSizedQueue, you might want to consider a circular
buffer,
which is already part of the Excalibur Collection classes.
What I have works, and I have a feeling that it will still be more
performant
than the CircularBuffer. I will throw together a CircularBuffer based
Queue
for test results though.
Test results for CircularBuffer beat out the ArrayList implementation by
the same margin that ArrayList beat out LinkedList. The average
enqueue/dequeue time is 1.05 usecs--consistently 100 nsecs less than
the ArrayList implementation.
It would be good to base the DefaultQueue on CircularBuffer as CircularBuffer
does resize itself as needed (just like ArrayList). It is not a replacement
for a FixedSizeQueue as the maximum size may change.
--
"They that give up essential liberty to obtain a little temporary safety
deserve neither liberty nor safety."
- Benjamin Franklin
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
