Monday, February 27, 2006

New features in Java 1.5

The For-Each loop
A task that is done often is to iterate through a collection, and do something with each element. For example, this shows all the elements in a list :

public void Show(List l) {
for (int i = 0; i < l.size(); i++) {
System.out.println (l.get(i));
}
}

This code seems right; however it could be very inefficient.
The in-efficiency can be attributed to the sequential manner - the
above progresses,resulting in an algorithm of order O(n^2)
whereas an algorithm O(n) is easily obtained.

O(n) can be got with the use of iterators (similar to c++)

public static void ShowFast(List l) {
for (Iterator it = l.iterator(); it.hasNext();) {
System.out.println (it.next());
}
}

When you ask for an iterator of the collection using the method
iterator(), a reference to the beginning of the list is retrieved.
Then, the hasNext() method returns whether there are still more
elements to come, and it.next() does two things: it advances the
reference to the next element in the collection and retrieves the
current element. This gives the LinkedList the opportunity to iterate
through the list in O(n). For the moment, all that can be done in
earlier versions of Java. Even if the above code works, it's not nice
and quite error prone. For example, if in the hurry you call again to
it.next() in the for block in order to retrieve again the element,
you'll get half the list in one place and half in another. Of course
that this can be solved storing the value of it.next() in a local
variable, but Java 1.5 brings a nicer and safer way to do the same: the
for-each loop.


public static void ShowFastAndNice(List l) {
for (Object o : l) {
System.out.println (o);
}

}


You can read the for sentence as "for each Object o in l"

With New features--- have to come their share of new problems.
Not everything is rosy here .....

The following bombs
Object o;
for (o : l) {
System.out.println (o);
}

Sun documents this as "these kinds of practices are not very clear and robust,
so the compiler is making you to write better code, even if it might require
an additional flag."(not verbatim but on similar lines).



3 comments:

Unknown said...

Have you checked out all the new features?? It looks very much like C++ with generics/templetes, etc!

Arvind said...

How is the first iteration example u quoted is O(n^2) .. if correct it should be O(n) .. what do u say? please justify ... By Manu.

Shantanu said...

public void Show(List l) {
for (int i = 0; i < l.size(); i++) {
System.out.println (l.get(i));
}
}

The reason is that a linked list doesn't have random access to its elements, so when you ask for an element, the linked list will sequentially search your element. For getting the 10000th element, the entire list will be iterated. So, the problem with this approach is that depending on the list implementation you could get an algorithm of order O(n^2) whereas an algorithm O(n) is easily obtained.