• 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

How Random Access works

 
Ranch Hand
Posts: 49
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Anant Jagania
Ranch Hand
Posts: 49
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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 ]
 
You learn how to close your eyes and tell yourself "this just isn't really happening to me." Tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic