Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Re: Looping through with an Iterator Vs. ArrayList (see msg body)

Reply
Thread Tools

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

 
 
John C. Bollinger
Guest
Posts: n/a
 
      08-04-2003
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
http://www.velocityreviews.com/forums/(E-Mail Removed)

 
Reply With Quote
 
 
 
 
Wayne
Guest
Posts: n/a
 
      08-05-2003
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[i]...
}

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

 
Reply With Quote
 
 
 
 
John C. Bollinger
Guest
Posts: n/a
 
      08-05-2003
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[i]...
> }
>
> 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 Removed)

 
Reply With Quote
 
Adam Maass
Guest
Posts: n/a
 
      08-06-2003

"John C. Bollinger" <(E-Mail Removed)> wrote:
> Wayne wrote:
> >
> > Object [] array = list.toArray();
> > for ( int i = 0; i < array.length; ++i )
> > {
> > ...array[i]...
> > }
> >
> > 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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Read .msg attachment from a mail(.msg) akila_natarajan Java 0 05-13-2011 07:35 AM
looping through json array loops through the characters instead ofthe values Aaron Javascript 2 04-10-2011 05:58 PM
[ANN] ruby-msg-1.3.1 (outlook msg lib) and ruby-ole-1.2.1 Charles Lowe Ruby 0 08-22-2007 01:13 AM
[ANN] ruby-msg-1.2.17 (converter for outlook msg files) Charles Lowe Ruby 0 05-13-2007 06:55 AM
Iterate through ArrayList using an another ArrayList Saravanan Rathinavelu ASP .Net 3 08-19-2003 07:03 AM



Advertisments