File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Question on general advice of when to implement RandomAccess

 
vu lee
Ranch Hand
Posts: 195
  • 0
  • Mark post as helpful
  • send pies
  • 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.
 
Paul Clapham
Sheriff
Pie
Posts: 20205
26
MySQL Database
  • 0
  • Mark post as helpful
  • send pies
  • 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: 195
  • 0
  • Mark post as helpful
  • send pies
  • 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
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic