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 ]
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 ]
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 ]
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.
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 ]
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 ]
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. )
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..."
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...
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 ]