my dog learned polymorphism*
The moose likes Beginning Java and the fly likes How Random Access works Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "How Random Access works" Watch "How Random Access works" New topic
Author

How Random Access works

Anant Jagania
Ranch Hand

Joined: Oct 20, 2004
Posts: 49
Hi All,

There is a marker interface called java.util.RandomAccess. It says that when this is implemented over sequential or random access it gives better performance. The API also say that

As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:

for (int i=0, n=list.size(); i < n; i++)
list.get(i);

runs faster than this loop:

for (Iterator i=list.iterator(); i.hasNext(); )
i.next();


How the first for loop becomes faster then another one? What does JVM do to make the access faster?

Thanks & Regards,
Anant
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18509
    
  40

How the first for loop becomes faster then another one? What does JVM do to make the access faster?


I think you got it backwards. The first "for" loop doesn't become faster if the interface is implemented. The JavaDoc is saying that if the first "for" loop is already faster, then the interface should be implemented to tell users of the container that it supports fast random access.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
IMO the documentation here is poorly written. An iterator returned be an ArrayList uses calls to get(index) behind the scenes. But for the additional overhead of the Iterator object the difference in performace of the two loops should be unnoticable. I would say :

As a rule of thumb, a List implementation should implement this interface if, elements can be accessed by get(index) in more or less constant (O(1)) time.


The marker interface has no functionality, but it does serve as an indicator as to which algorithms should give better performance. For instance if you receive a sorted List and you want to find a particular element, if the List is random access then a binary search will be the optimal solution, however that would be a totally inappropriate choice for a sequential list. The JVM does nothing to optimize the performance of lists tagged as RandomAccess.
[ March 21, 2007: Message edited by: Garrett Rowe ]

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Anant Jagania
Ranch Hand

Joined: Oct 20, 2004
Posts: 49
if JVM doesn't do anything when RandomAccess has been used over the implementation of ArrayList then why JavaDoc says that

The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

there must be something which JVM or Collection framework does to improve the performance of lists. what could be that?
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
there must be something which JVM or Collection framework does to improve the performance of lists. what could be that?
As the documentation suggests, methods that receive a List as a parameter can check to see if the List implements RandomAccess. If it does the method can make assumptions about the best algorithm to use. The simplest example I can think of is:



[ March 22, 2007: Message edited by: Garrett Rowe ]
[ March 22, 2007: Message edited by: Garrett Rowe ]
 
Consider Paul's rocket mass heater.
 
subject: How Random Access works
 
Similar Threads
Why LinkedList over ArrayList for Insertion and Deletion?
which is faster in List Classes
Difference between ArrayList and LinkedList?
Question on general advice of when to implement RandomAccess
Big OOoooooo