Iterator vs Index Numbers

[randumb]

Say I want to go through a collection like an ArrayList, is it faster to use an iterator or the index numbers?

Edit: In Java

 

[DaveSimmons]

Bench and see if you really care, but it's trivial for both so not worth optimizing.

The rule of thumb really is true, > 90% of your code is not worth optimizing for speed.

Consider if the loop is serializing the elements to/from a file. Then 99.99999% of the the time will be spent on serializing, 0.00001% on moving to the next element.

 

[randumb]

Originally posted by: DaveSimmons
Bench and see if you really care, but it's trivial for both so not worth optimizing.

The rule of thumb really is true, > 90% of your code is not worth optimizing for speed.

Consider if the loop is serializing the elements to/from a file. Then 99.99999% of the the time will be spent on serializing, 0.00001% on moving to the next element.

So is it generally better to use an iterator or index numbers? I'm guessing an iterator for readability?

 

[DaveSimmons]

I'm primarily a C++ developer (and not using STL) so hopefully a java developer can answer the style question.

But in C++ I generally pick the loop control statement or function that is easiest to understand, keeping in mind it might not be read until a year later or more and I'll have forgotten why and how I wrote it.

 

[akubi]

using the iterator is faster.

btw, I think your code is buggy if you remove those elements like that while you're iterating through it.

for example, if you remove(0) then everything after that is shifted down, but because your i++ you'll be doing remove(1), etc, and you won't end up removing all the elements.

in general, you don't want to remove stuff out of collections while iterating.

 

[lchyi]

Iterator is l3373r.

 

[randumb]

Originally posted by: akubi
using the iterator is faster.

btw, I think your code is buggy if you remove those elements like that while you're iterating through it.

for example, if you remove(0) then everything after that is shifted down, but because your i++ you'll be doing remove(1), etc, and you won't end up removing all the elements.

in general, you don't want to remove stuff out of collections while iterating.

whoops, you're right, the removal wouldn't work with the index number implementation.

why would the iterator be faster? is it because get has to search through the arraylist each time and the iterator has pointers to the next object?

 

[EagleKeeper]

Originally posted by: randumb

Originally posted by: akubi
using the iterator is faster.

btw, I think your code is buggy if you remove those elements like that while you're iterating through it.

for example, if you remove(0) then everything after that is shifted down, but because your i++ you'll be doing remove(1), etc, and you won't end up removing all the elements.

in general, you don't want to remove stuff out of collections while iterating.

whoops, you're right, the removal wouldn't work with the index number implementation.

why would the iterator be faster? is it because get has to search through the arraylist each time and the iterator has pointers to the next object?

Correct. Such is the advantage of linked-lists.

 

[SinNisTeR]

results:

iterator: 63
index: 938


*keep in mind that scores can be skewed by other programs utilizing cpu time...

 

[statik213]

Since you are using an arraylist it shouldn't make much of a difference, esp. if the `// statement` part of the loop is big...
But if you were using a linked list (i.e. regular List) a get(i) would be a lot more ineffecient than using an iterator and doing a .next().

 

[znaps]

Originally posted by: SinNisTeR
results:

iterator: 63
index: 938


*keep in mind that scores can be skewed by other programs utilizing cpu time...

Change the code to the following and the results are much different. I think my code *might* be a fairer test, and that list.get() is generally a little bit faster, but in most cases it's too trivial to make it worthwhile using.

 

[SinNisTeR]

wow, that makes a big difference. I wonder why.

Now im getting

iterator: 62
index: 47

or often times, they are equal.

 

[znaps]

The only difference I can see is your generics usage in the second part of the test to avoid an explicit cast. I did notice that the comparisons may not be equal, but I didn't think it would have made such a dramatic difference.

 

[randumb]

Originally posted by: znaps
The only difference I can see is your generics usage in the second part of the test to avoid an explicit cast. I did notice that the comparisons may not be equal, but I didn't think it would have made such a dramatic difference.

using the new string hurts performance drastically in sinister's code for some reason.

 

[SinNisTeR]

ya. that's not really relevant for the test, sorry

 

[torpid]

Performance probably won't matter much. The iterator implementation in an ArrayList is mostly there so that you can treat the ArrayList like an IEnumerable. My guess is that the IEnumerable implementation in ArrayList uses the index to keep track of position. Edit: i.e. index may be faster by a small margin due to not having to call wrapper functions.

 

[znaps]

Yep, I think the generated byte code is pretty similar in the end.

 

[kamper]

Originally posted by: SinNisTeR
wow, that makes a big difference. I wonder why.

Now im getting

iterator: 62
index: 47

or often times, they are equal.

You might want to crank up the size of the ArrayList. I've not known java's timing facilities to be very fine grained at that level.

I have a guess as to why the Iterator was taking so long in the first example, I think it's memory usage. Try putting "test = null;" before running the second loop (maybe do a garbage collection and thread yield as well if you don't see any difference). Maybe try increasing the vm heap size as well to alleviate some of the problems.

Last, if y'all are going to use iterators and java 1.5 you may as well do it properly: