• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Question on List.get() in for loop vs listIterator()

 
Ranch Hand
Posts: 585
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Anyone know if it's better performance (and code-maintenance-wsie) to do a for loop and call "get()" to get the elements in a list versus getting the list iterator and doing a "hasNext()" loop?
 
Ranch Hand
Posts: 7729
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
PS: Whoops, I've answered a more general question than you asked. But I'll leave it in.
From a design point of view: suppose you have Collection c = new ArrayList(); and then you fill the list with stuff. You cannot use c.get() because get() does not exist in Collection. Iterator i = c.iterator(); will work though.
So one point to consider is the amount of generality your program requires. Is it required that the List type is possibly replaced by another Collection type at a later time?
For performance: if you use an ArrayList, say al, then I would guess ( I have not checked it ) that the for( int i = 0, n = al.size() ; i < n ; i++ ) { Object o = al.get( i ); } would be faster than an iterator, because the ArrayList is implemented by means of an array of Object.
You'd best check each Collection type ( API details, source code ) on a case-by-case basis, and compare with your application's specific requirements.
For get() verses ListIterator.next(): if you just want to blast down the list from front to back the for/get would *most likely* perform better than the ListIterator because ListIterator has to maintain more context about its position in the list. However, again check the source.
[ February 02, 2003: Message edited by: Barry Gaunt ]
[ February 02, 2003: Message edited by: Barry Gaunt ]
 
author
Posts: 3252
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Robert,
When all you have is "a List" then there is no question about it: use an Iterator. Because the List you have may be a LinkedList and get() will perform O(n), giving the entire loop O(n*n) performance. Ouch. An Ierator will give you O(n) performance on any flavour of List.
If, on the other hand, you know that your List is actually an ArrayList, it is tempting to use get() is a little bit faster. Do not do this. You would be, deviously, implicitly, coding to implementation rather than interface. Increasing the coupling, and reducing the abstraction and flexibility in your code. If you really, really have to do this (remember the first three rules of optimization though) then use get(), while at the same time changing variables and method signatures from List to ArrayList to clearly flag up that you are coding to a specific implementation here.
Finally, if you can't require an ArrayList, for example because you're developing a library and really can't make assumptions about the kind of List you're getting, yet you still need the fastest possible iteration, useYou may find the javadoc for java.util.RandomAccess interesting reading.
- Peter
[ February 02, 2003: Message edited by: Peter den Haan ]
 
Barry Gaunt
Ranch Hand
Posts: 7729
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I said:

For get() verses ListIterator.next(): if you just want to blast down the list from front to back the for/get would *most likely* perform better than the ListIterator because ListIterator has to maintain more context about its position in the list. However, again check the source.


I had to think hard about what Peter has said about get() being of O(n). Of course he's correct in the case of a linked list. Every time you do get(i) the thing's going to start at the head of the list and chug along, following links, until it has got to the i-th item.
In the case of an ArrayList I'm following the advice of Joshua Bloch (Effective Java).
Thanks, Peter for the education
PS The RandomAccess interface approach is interesting!
[ February 02, 2003: Message edited by: Barry Gaunt ]
 
Robert Paris
Ranch Hand
Posts: 585
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you both for the answers. Peter - you're 100% right. I'm going back and changing my code to use Iterator. I thought it was a bit cleaner/more decoupled but didn't realize the huge danger of using the for loop.
 
Any sufficiently advanced technology will be used as a cat toy. And this tiny ad contains a very small cat:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic