2014-04-20

For-each loop vs Iterator vs C-style for loop

In Java a for loop that uses an iterator
List<String> strings = new LinkedList<>(Arrays.asList("first", "second"));
for (Iterator iterator = strings.iterator(); iterator.hasNext();) {
    System.out.println(iterator.next());
}
is essentially the same as
List<String> strings = new LinkedList<>(Arrays.asList("first", "second"));
for (String string : strings) {
    System.out.println(string);
}
because the generated byte code for the second code snippet executes the same operations underneath as for the first code snippet. So the for-each loop, introduced with Java 5 is merely syntactic sugar for the for loop that explicitly deals with an iterator.

However this C-style for loop works with an index
List<String> strings = new LinkedList<>(Arrays.asList("first", "second"));
for(int index = 0; index < strings.size(); index++) { 
    System.out.println(strings.get(index));
}
and uses #get(index) instead of iterator.next(). This has vast implications on the execution performance of this loop. Both former loops call iterator.next() which is an O(1) operation, making the both loops to O(n) operations whereas strings.get(index) is an O(n) operation, making the entire loop an O(n²) operation which is substantially slower.

The first and last loop can be both expressed using the for-each' syntactic sugar form.

3 comments:

  1. looking on the code of asList, it seems to me that the get(index) is o(1) as it uses an array undercover

    ReplyDelete
  2. Thanks Francois, you're right. I've changed the implementation to use LinkedList, which is still not quite O(n) but fore sure > O(1).

    ReplyDelete
  3. Great. Good point made here, but it completely depends on the underlying data structure. Some data structure takes O (n) for get (I) where as some take O (1). So performance benifit will depend on the underlying data structure if we are using old c style loop.
    Here one point is worth making that using iterator we'll always have the complexity of O (1) for the next() as it is the basic requirement for all the iterators. I personally prefer for each style(if no removal is required) as it has no boilerplate code and provides same performance as of the iterator.

    ReplyDelete