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]>
