RE: Massively OT, 'Closures in Java' [was Re: AW: [Patch] modifiedselector, style, remove unused code, slightly more lazy DigestAlgorithm.getValue (now with added source code -doh!)]

[Phil Weighill-Smith <ph...@volantis.com>]

If you want to iterate through a List that has an unspecified
implementation (at the point of iteration) always use an iterator; this
is the only way to implement performant code without making assumptions
about the implementation of the list.

Phil :n.

On Mon, 2005-02-28 at 11:30, Jose Alberto Fernandez wrote:

> I do not think so, from LinkedList implementation:
> 
>     /**
>      * Return the indexed entry.
>      */
>     private Entry entry(int index) {
>         if (index < 0 || index >= size)
>             throw new IndexOutOfBoundsException("Index: "+index+
>                                                 ", Size: "+size);
>         Entry e = header;
>         if (index < size/2) {
>             for (int i = 0; i <= index; i++)
>                 e = e.next;
>         } else {
>             for (int i = size; i > index; i--)
>                 e = e.previous;
>         }
>         return e;
>     }
> 
> It will iterate on every call.
> 
> Enough of this, as I think it is becoming a little out of subject for
> the ANT list :-)
> 
> Jose Alberto
> 
> > -----Original Message-----
> > From: Kev Jackson [mailto:kevin.jackson@it.fts-vn.com] 
> > Sent: 28 February 2005 11:19
> > To: Ant Developers List
> > Subject: Re: Massively OT, 'Closures in Java' [was Re: AW: 
> > [Patch] modifiedselector, style, remove unused code, slightly 
> > more lazy DigestAlgorithm.getValue (now with added source code -doh!)]
> > 
> > 
> > Jose Alberto Fernandez wrote:
> > 
> > >AFAIU, LinkedList.get(N) requires traversing the list to 
> > position N on 
> > >every call [O(n^2)], so usage of an iteratoe is much cheaper on this 
> > >case as there is no array behind the scenes.
> > >
> > >Jose Alberto
> > >  
> > >
> > I've just worked out why it's ok to do it this way (with 
> > respect to my 
> > particular use-case).  Basically I *want* to traverse the 
> > entire list, 
> > I'm not trying to pick out any particular position in the list (yes 
> > truly expensive using LinkedList.get(i)).  In my method I simply call 
> > get(i) from 0..List.size():
> > 
> > from docs
> > <quote>Operations that index into the list will traverse the 
> > list from 
> > the begining or the end, whichever is closer to the specified 
> > index.</quote>
> > 
> > So as I'm asking for position 0, the traversal starts at the 
> > head of the 
> > list, then I simply walk the list with the loop calling get(i), which 
> > also happens to be the next element in the list from where the list 
> > cursor currently is (ListIterator interface docs).  Serendipity I 
> > suppose, but my usage is the most efficient for LinkedLists and also 
> > happens to be performant with ArrayLists, to do the 
> > particular traversal 
> > that I'm doing.
> > 
> > Kev
> > 
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: dev-unsubscribe@ant.apache.org
> > For additional commands, e-mail: dev-help@ant.apache.org
> > 
> > 
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@ant.apache.org
> For additional commands, e-mail: dev-help@ant.apache.org

-- 
Phil Weighill-Smith <ph...@volantis.com>
Volantis Systems