|
|
|
How many interfaces are there in the JDK that have no fields and no methods? What are these interfaces used for? Read on in our "Fast Random Access" article from our "Learning From Code" series.
Published February 2004, Author Jack Shirazi
Page 2 of 2
previous page: Fast Random Access
So now that we know what RandomAccess
means, how do we use it? Well, for the most part you will rarely need to implement the interface -- in fact only if you are implementing a List
class which has fast random access. However, when you want to iterate List
classes, then you can optimize the iteration speed by using RandomAccess
. For an example, let's look at the java.util.Collections
class. The Collections
class implements many utility methods for searching and manipulating Collection
objects. In order to optimize performance, many of the utility methods use a variant of an algorithm depending on whether or not the object is a RandomAccess
object. For example, the Collections.binarySearch()
method is defined as follows:
|
This method checks to see if it has been passed a RandomAccess
List, and if so uses the List.get()
method to access elements while iterating the List
(in the indexedBinarySearch()
method); otherwise the Iterator.next()
method is used (in the iteratorBinarySearch()
method). As you can see, that isn't quite the whole story for the binarySearch()
method. There is another case where the List.get()
method is also used to iterate the List
: when the size of the List
object is below the BINARYSEARCH_THRESHOLD
value. The author of the Collections
class, Joshua Bloch, noticed that for smallish collections it was faster to iterate the List
using List.get()
even if the List
wasn't RandomAccess
. The threshold value below which the List.get()
iteration is used is different for the various utility methods in the Collections
class, and each such utility method has it's own threshold value. This is a classic tuning technique. The actual values of the thresholds seem to have been determined by testing using LinkedList
as the non-RandomAccess
class, and possibly on a Solaris machine, though I would assume that the selected thresholds had been verified on a couple of architectures.
Another Collections
method , the Collections.fill()
method, illustrates the most common RandomAccess
idiom
|
Some projects may need to worry about backward compatibility, or may not yet have moved to the 1.4 SDK. Instructions for using RandomAccess
with any version of the SDK are available in my earlier article "Faster List iteration using the RandomAccess interface"
Page 2 of 2
previous page: Fast Random Access