Re: Looping through with an Iterator Vs. ArrayList (see msg body)

Discussion in 'Java' started by John C. Bollinger, Aug 4, 2003.

  1. Kabal wrote:
    > Anyone know if going through with an iterator is slower or faster than
    > an ArrayList. See below for an example:
    >
    > ArrayList list = new ArrayList();
    >
    > ...
    >
    > Iterator it = list.iterator();
    >
    > while (it.hasNext()) {
    > ....
    > }
    >
    > // OR
    >
    > for (int i=0; i<list.size(); i++) {
    > ...
    > }


    For ArrayList, tests often show that the two approaches are about
    equivalent. The same is not true of LinkedList, where the iterator
    approach is much faster for lists of any significant size.

    You can never beat testing your own code, though.


    John Bollinger
     
    John C. Bollinger, Aug 4, 2003
    #1
    1. Advertising

  2. John C. Bollinger

    Wayne Guest

    John C. Bollinger wrote:

    > Kabal wrote:
    >
    >> Anyone know if going through with an iterator is slower or faster than
    >> an ArrayList. See below for an example:
    >>
    >> ArrayList list = new ArrayList();
    >>
    >> ...
    >>
    >> Iterator it = list.iterator();
    >>
    >> while (it.hasNext()) {
    >> ....
    >> }
    >>
    >> // OR
    >>
    >> for (int i=0; i<list.size(); i++) {
    >> ...
    >> }

    >
    >
    > For ArrayList, tests often show that the two approaches are about
    > equivalent. The same is not true of LinkedList, where the iterator
    > approach is much faster for lists of any significant size.


    I don't understand the question. What goes in the for loop
    in place of the "..."? Surely some call to "ArrayList.get()"?
    So the resulting byte code should be nearly identical and
    dominated by the method calls, right?

    Multi-Threading issues aside, when will this be faster?

    Object [] array = list.toArray();
    for ( int i = 0; i < array.length; ++i )
    {
    ...array...
    }

    It seems that is should be a lot faster since the method calls
    in the loop body have been replaced with a single method call
    outside. Or is that what the original question was about?

    -Wayne
     
    Wayne, Aug 5, 2003
    #2
    1. Advertising

  3. Wayne wrote:
    > John C. Bollinger wrote:
    >
    >> Kabal wrote:
    >>
    >>> Anyone know if going through with an iterator is slower or faster than
    >>> an ArrayList. See below for an example:
    >>>
    >>> ArrayList list = new ArrayList();
    >>>
    >>> ...
    >>>
    >>> Iterator it = list.iterator();
    >>>
    >>> while (it.hasNext()) {
    >>> ....
    >>> }
    >>>
    >>> // OR
    >>>
    >>> for (int i=0; i<list.size(); i++) {
    >>> ...
    >>> }

    >>
    >>
    >>
    >> For ArrayList, tests often show that the two approaches are about
    >> equivalent. The same is not true of LinkedList, where the iterator
    >> approach is much faster for lists of any significant size.

    >
    >
    > I don't understand the question. What goes in the for loop
    > in place of the "..."? Surely some call to "ArrayList.get()"?


    In the Iterator case, an Iterator.next() goes in the loop, and normally
    some use of the object thereby retrieved. This is to be compared to the
    indexed loop in which case, as you say, an ArrayList.get(i) goes in the
    loop, along with the same use of the retrieved object.

    > So the resulting byte code should be nearly identical and
    > dominated by the method calls, right?


    If you look at the byte codes in detail then there are plenty of
    differences, but the general schemes are about the same. Each one
    contains two method invocations per loop iteration. (Disregarding the
    part of the loop that does the real work.) The time might be dominated
    by the method invocations, but more bytecodes are devoted to
    manipulating variables and operands.

    > Multi-Threading issues aside, when will this be faster?


    Do you mean the previous or the following? As I wrote before,
    timing-wise and for ArrayLists specifically, the two above approaches
    are pretty much equivalent. The Iterator approach provides better
    encapsulation when the specific indices are not significant. The
    Iterator approach performs _much_ better than the indexed approach for
    some other kinds of Lists (e.g. LinkedLists), and so using that approach
    also insulates your code from changes to the List implementation used.

    > Object [] array = list.toArray();
    > for ( int i = 0; i < array.length; ++i )
    > {
    > ...array...
    > }
    >
    > It seems that is should be a lot faster since the method calls
    > in the loop body have been replaced with a single method call
    > outside. Or is that what the original question was about?


    That is not what the original question was about, but it does bear some
    discussion. It might sometimes be useful to do exactly as you describe,
    but doing so is unlikely to be faster. That's because in order to
    construct the array it is necessary to perform a sequence of operations
    equivalent to the code we were talking about before. Only after that is
    complete is the real work done in your example. Moreover, constructing
    an intermediate array consumes more memory; this is not of much concern
    if the operation is not performed too often and the original List is not
    too large, but otherwise it could be a problem.

    It could be useful to construct that intermediate array when you want to
    enforce stricter typing in the loop body without using casts there.
    Instead of the first line of your example you would use

    MyType[] array = (MyType[]) list.toArray(new MyType[0]);

    or something similar. Actually, now that I look at it, I'm not sure
    that that gives much advantage at all. Perhaps you'll see some.


    John Bollinger
     
    John C. Bollinger, Aug 5, 2003
    #3
  4. John C. Bollinger

    Adam Maass Guest

    "John C. Bollinger" <> wrote:
    > Wayne wrote:
    > >
    > > Object [] array = list.toArray();
    > > for ( int i = 0; i < array.length; ++i )
    > > {
    > > ...array...
    > > }
    > >
    > > It seems that is should be a lot faster since the method calls
    > > in the loop body have been replaced with a single method call
    > > outside. Or is that what the original question was about?

    >
    > That is not what the original question was about, but it does bear some
    > discussion. It might sometimes be useful to do exactly as you describe,
    > but doing so is unlikely to be faster. That's because in order to
    > construct the array it is necessary to perform a sequence of operations
    > equivalent to the code we were talking about before.


    Well, perhaps. ArrayList.toArray (both versions) do the bulk of their work
    by calling System.arraycopy(). System.arraycopy() is a native method, but
    is likely implemented under-the-covers by some version of the C library's
    memcpy. This should be a bulk-copy operation on many systems, and may be
    rather fast.

    Of course, my standard response to performance questions still applies:
    First prove you have a performance problem. Then and only then prove that
    the not-quite standard thing you did in the code improves performance.

    -- Adam Maass
     
    Adam Maass, Aug 6, 2003
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Saravanan Rathinavelu

    Iterate through ArrayList using an another ArrayList

    Saravanan Rathinavelu, Aug 16, 2003, in forum: ASP .Net
    Replies:
    3
    Views:
    2,744
    Natty Gur
    Aug 19, 2003
  2. akila_natarajan

    Read .msg attachment from a mail(.msg)

    akila_natarajan, May 13, 2011, in forum: Java
    Replies:
    0
    Views:
    391
    akila_natarajan
    May 13, 2011
  3. Charles Lowe
    Replies:
    0
    Views:
    226
    Charles Lowe
    May 13, 2007
  4. Charles Lowe
    Replies:
    0
    Views:
    173
    Charles Lowe
    Aug 22, 2007
  5. Aaron
    Replies:
    2
    Views:
    530
    dhtml
    Apr 10, 2011
Loading...

Share This Page