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...
Chad ----- Original Message ----- From: "Berin Loritsch" <[EMAIL PROTECTED]> To: "Avalon Developers List" <avalon-dev@jakarta.apache.org> Sent: Wednesday, December 19, 2001 12:36 PM Subject: Re: [Report] Efficiencies of FixedSize and Default Queues > Berin Loritsch wrote: > > > Chad Stansbury wrote: > > > >> Is there a reason you're using an ArrayList rather than a LinkedList > >> for the > >> DefaultQueue? ArrayLists are great for indexing, but suck for > >> variable-sized lists w/ lots off adds & removes. LinkedLists, on the > >> other > >> hand, excel at variable-sized lists with lots of adds/removes, but > >> suck at > >> indexing. Are you using indexing? > > > > > > > > No, I am not using indexing. I will try your suggestions, and report back. > > > My initial testing reveals that for small queues where the overall size is > fairly constant, the ArrayList wins out by 100 nsecs consistently. > > Run five times each, the LinkedList version was a complete second behind the > ArrayList version. I have a feeling this has to do with the way that LinkedLists > are constructed (i.e. many small objects that merely reference entries and the > object in question). The overhead is minor, but why incur it if you don't > need to? > > > > >> 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. > > -- > > "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]> > > -- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
