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

  • Thread starter John C. Bollinger
  • Start date
J

John C. Bollinger

Kabal said:
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
(e-mail address removed)
 
W

Wayne

John said:
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
 
J

John C. Bollinger

Wayne said:
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
(e-mail address removed)
 
A

Adam Maass

John C. Bollinger said:
Wayne said:
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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top