• 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 general advice of when to implement RandomAccess

 
Ranch Hand
Posts: 208
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
From RandomAccess API


It is recognized that the distinction between random and sequential access is often fuzzy. For example, some List implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a List implementation should generally implement this interface. 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();



Since they both measure time sequentially, how could the second loop run slower than the first loop? Suppose the first look is backed by an Array and the second loop is backed by a LinkedList. Accessing the next item on the list takes O(1) since it just follows the next pointer to the next element.
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The quote is talking about comparing different ways of using a single implementation. Your example doesn't do that so it doesn't make sense. You could consider the comparison of the two pieces of code on an ArrayList, and then consider the comparison of the two pieces of code on a LinkedList. In fact you should.
 
vu lee
Ranch Hand
Posts: 208
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That is what I was missing. Thanks for pointing it out. For ArrayList, it should not be much different since the runtime of both iterations will be equivalent; however, there is a big different for LinkedList
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic