aspose file tools*
The moose likes Cattle Drive and the fly likes Array list > for loop or iterator Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » This Site » Cattle Drive
Bookmark "Array list > for loop or iterator" Watch "Array list > for loop or iterator" New topic
Author

Array list > for loop or iterator

Pauline McNamara
Sheriff

Joined: Jan 19, 2001
Posts: 4012
    
    6
Is there a performance or other issue involved in choosing a for loop over an iterator to go through an array list?
given myArrayList,

Does the creation of an Iterator object cost a lot?
Thanks,
Pauline
Marilyn de Queiroz
Sheriff

Joined: Jul 22, 2000
Posts: 9047
    
  10
Write a test case. Iterate a million times and let us know the results.


JavaBeginnersFaq
"Yesterday is history, tomorrow is a mystery, and today is a gift; that's why they call it the present." Eleanor Roosevelt
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Iterators are fairly cheap. The for loop will be slightly faster, but the difference is seldom significant for real applications (those that are bothering to do anything significant besides looping through a list). On the other hand if you're using a LinkedList, the for loop is quite horrid, and the Iterator works great. So I prefer the Iterator in general to allow maximum flexibility.
[ August 08, 2002: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, Twister
Lance Finney
Ranch Hand

Joined: Apr 26, 2001
Posts: 133
According to Peter Haggar's "Practical Java", iterating with a for loop is more efficient than using an iterator for traversing a vector. I can't guarantee it works the same for an ArrayList, but there's a good chance.
Of course, iterating 1,000,000 times and timing it is the way to find out.
[ August 08, 2002: Message edited by: Lance Finney ]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
True. And moreover, this is why they added the RandomAccess interface in 1.4 - so you can determine if you're dealing with a collection whose get(int) method is more efficient than the iterator (as is the case for an ArrayList) or not (like for LinkedList). But I still believe that in many cases (with real code, not simplified test cases) the added flexibility you get from using an iterator is more beneficial than the performance benefits you get from the get(int) method. YMMV and all that...
Oh, and to refine my answer to Pauline's question:
Does the creation of an Iterator object cost a lot?
No, it's trivial. It's a fairly lightweight object that's only instantiated once. However the use of the iterator methods while looping may cost a bit more than get(int). Mostly because you need to make two method calls with the iterator, and only one with get(int), for each iteration.
[ August 08, 2002: Message edited by: Jim Yingst ]
Pauline McNamara
Sheriff

Joined: Jan 19, 2001
Posts: 4012
    
    6
Thanks for the feedback folks. I'd been wondering after seeing the for loop in someone else's code where I'd used an iterator.

Write a test case. Iterate a million times and let us know the results.
...
Of course, iterating 1,000,000 times and timing it is the way to find out.

I hope to get to this, getting a "submittable" version of servlets-4b done and sent off was a priority.
Curious though, as far as the cattle drive instructor's solution is concerned, was performance the issue in the choice of a for loop?

I glanced through a copy of "Practical Java" yesterday and was very tempted to pay for it and take it home. I think it may be next on the list for Java books.
Marilyn de Queiroz
Sheriff

Joined: Jul 22, 2000
Posts: 9047
    
  10
More than one solution uses a for loop rather than an iterator. Are you asking in general?

Practical Java ... good book.
Pauline McNamara
Sheriff

Joined: Jan 19, 2001
Posts: 4012
    
    6
More than one solution uses a for loop rather than an iterator. Are you asking in general?
It was the Servlets-4a solution that got me wondering.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Choosing between a for loop and an iterator seems like a false dichotomy. It's perfectly possible to use a for loop with an iterator. It's even recommended by Joshua Bloch in Effective Java, since the for loop limits the scope of the Iterator variable:

Dunno how this compares with recommended cattle drive style - maybe it's less clear on first reading than the while loop version, but localizing the iterator is a tangible benefit. The idiom is fairly transparent once people have seen it a couple times.
Also, here's the fastest way to iterate through any collection that is not random-access like ArrayList:

This loses the benefit of localizing the iterator , but it's faster since there's no extra hasNext() call on each iteration. (Manipulating local variable i is notably faster than calling an instance method here.) If the collection is actually an ArrayList (or other RandomAccess) then this method is not quite as fast as using get(index). But it's close, moreso than a "standard" iterator traversal, and still offers the flexibility I touted earlier.
[ August 12, 2002: Message edited by: Jim Yingst ]
Mapraputa Is
Leverager of our synergies
Sheriff

Joined: Aug 26, 2000
Posts: 10065
Speaking about cost of the creation of an Iterator object, the best way to find out is probably to look at implementation code. Iterators are implemented as a private inner class whose state consists of only a few int variables - "a fairly lightweight object" as Jim said Naturally, they operate directly on a data structure that implements ArrayList, that's another reason why they are so fast.
Choosing between a for loop and an iterator seems like a false dichotomy.
I think Pauline meant "for loop with get(index)" method vs. Iterator So it is rather "get(index) vs. itr.next()" question?
[ August 12, 2002: Message edited by: Mapraputa Is ]

Uncontrolled vocabularies
"I try my best to make *all* my posts nice, even when I feel upset" -- Philippe Maquet
Marilyn de Queiroz
Sheriff

Joined: Jul 22, 2000
Posts: 9047
    
  10
Pauline meant
for ( int i = 0 ; i < list.size() ; i++ )
Mapraputa Is
Leverager of our synergies
Sheriff

Joined: Aug 26, 2000
Posts: 10065
What is inside the loop?
Dirk Schreckmann
Sheriff

Joined: Dec 10, 2001
Posts: 7023
Sure, trying to get the instructor's solution without doing the work.


[How To Ask Good Questions] [JavaRanch FAQ Wiki] [JavaRanch Radio]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
I understood what Pauline meant; I just wanted to point out that those weren't the only options, and that for many uses the best choice is a combination of the two options originally presented.
Mapraputa Is
Leverager of our synergies
Sheriff

Joined: Aug 26, 2000
Posts: 10065
Sorry
I just wanted to point out that there are two orthogonal (genuine) dichotomies: 1) "for loop vs. while loop" and 2) direct access with get(index) vs. using Iterator's next(). "Choosing between a for loop and an iterator" is indeed a "false dichotomy", and we are seemingly agreed that this is not what Pauline, in fact, asked, but just how she put it. )
Pauline McNamara
Sheriff

Joined: Jan 19, 2001
Posts: 4012
    
    6
hunh?
Mapraputa Is
Leverager of our synergies
Sheriff

Joined: Aug 26, 2000
Posts: 10065
Well, basically I was just saying that we certainly know better which question you actually asked... All our IT industry is progressing under the motto "we'll give the customer not what he asked for, but what he needs..."
Thomas Paul
mister krabs
Ranch Hand

Joined: May 05, 2000
Posts: 13974
Don't you guys even bother to read my articles:
http://www.javaranch.com/newsletter/June2002/newsletterjune2002.jsp#collections
As you can see, the test I ran on the ArrayList showed the iterator to be 3 times slower than the get. On the LinkedList the opposite is true.
So, the answer is to always test in your real production application to determine which works best for you.


Associate Instructor - Hofstra University
Amazon Top 750 reviewer - Blog - Unresolved References - Book Review Blog
Mapraputa Is
Leverager of our synergies
Sheriff

Joined: Aug 26, 2000
Posts: 10065
Read Thomas articles! Read Thomas articles!
Especially the last one!
------------------------------
"What exactly is a Map in Java?"
Thomas Paul, "Storing Objects in Java"
Pauline McNamara
Sheriff

Joined: Jan 19, 2001
Posts: 4012
    
    6
Ok I read the article. (What, no pictures?! )
Write a test case. Iterate a million times and let us know the results.
And I did a little test. Used an ArrayList with 5 to 50 elements, then went through it using the 2 different options, repeating that a million times. (Each iteration casted and assigned the list element to a string.)
At first I didn't include the creation of the iterator in the 1,000,000 repetitions. For those tests, the iterator came up faster (increasing with fewer list elements).
Then I included the iterator creation in the million repetitions. That made the get(index) 1.8 to 2.3 times faster (less arraylist elements, get(index) more fasterer).
Well that was fun, my first performance test. Ha! Should really be working ahead on the next servlets, or better yet, getting some sleep...
Dirk Schreckmann
Sheriff

Joined: Dec 10, 2001
Posts: 7023
What code did you use for the test?
Pauline McNamara
Sheriff

Joined: Jan 19, 2001
Posts: 4012
    
    6
Aside from creating and populating the arraylist, plus a bunch of println statements, the essence was

Go ahead and nitpick away, just be gentle with me...
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Thomas- As a matter of fact I did read your excellent article, and had tested such things myself beforehand anyway. My comments stand.
Pauline-
Cool, congratulations on your first performance test. Some comments:
Personally I prefer System.currentTimeMillis() rather than new Date().getTime(). We don't need no steenking new objects here. No big deal though...
Hey - where are the times for the last iteration method I suggested? (For loop with iterator & size(), no hasNext().) Sure, ignore my wonderful suggestion... :roll:
Certainly it makes sense to include iterator creation in the timing. But you'll also find that the relative importance of this is less and less significant as list size increases. I tend to assume that if perfomance of a loop like this is an issue at all, it's for one of three reasons:

(1) The whole loop is going to be re-run (from the beginning) many times.
(2) It's a loop through a really big list.
(3) Something inside the loop takes a long time.
You're basically testing the first situation only. Which is fine, and may well be appropriate for a particular application. But realize that if either of the next two are appropriate, the Iterator creation becomes insignificant. If the last case is dominant, then the whole question of Iterator vs. get() becomes insignificant as well. Note that most of my previous comments were referring to applications that did something in the loop other than just get() an object. E.g. for Servlets 4-a, you're supposed to output the list contents to a page, right? Try putting a print statement into your loop, and you'll see it matters much less whether you use get() or an iterator.
or better yet, getting some sleep...
Sleep is for the weak! Errr... sorry. Must've been reading the Klingon programmer quotes again. Cheers...
[ August 14, 2002: Message edited by: Jim Yingst ]
Marilyn de Queiroz
Sheriff

Joined: Jul 22, 2000
Posts: 9047
    
  10
Originally posted by Jim Yingst:
Hey - where are the times for the last iteration method I suggested? (For loop with iterator & size(), no hasNext().) Sure, ignore my wonderful suggestion...


Probably because those styles are discouraged around these parts.
[ August 15, 2002: Message edited by: Marilyn de Queiroz ]
Mapraputa Is
Leverager of our synergies
Sheriff

Joined: Aug 26, 2000
Posts: 10065
Sleep is for the weak!
I agree!
Read this and this instead, if haven't yet.
[ August 15, 2002: Message edited by: Mapraputa Is ]
Pauline McNamara
Sheriff

Joined: Jan 19, 2001
Posts: 4012
    
    6
Thanks you guys.
Sleep is for the weak!, oft repeated motto of chronic insomniacs. You have my sympathy, really.

Pauline "I believe in sleep" McNamara
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Probably because those styles are discouraged around these parts.
Awwww...
What if I add lots of gratuitous spaces and blank lines?
[time to run away quickly now...]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Array list > for loop or iterator