

Faster List Iteration with RandomAccess Interface
10/24/2001Java SDK version 1.4, due out later this year, introduces a new
java.util.
interface that has no methods.
What is the purpose of this interface?RandomAccess
What does RandomAccess mean?
RandomAccess
is a marker interface, like the
Serializable
and Cloneable
interfaces. All of these
marker interfaces do not define methods; instead, they identify a class as
having a particular capability.
In the case of Serializable
, the
interface specifies that if the class is serialized using the serialization I/O
classes, then a NotSerializableException
will not be thrown (unless
the object contains some other class that cannot be serialized).
Cloneable
similarly indicates that the use of the
Object.clone()
method for a Cloneable
class will not
throw a CloneNotSupportedException
.
The RandomAccess
interface identifies that a particular
java.util.List
implementation has fast random access. A more
accurate name for the interface would have been FastRandomAccess
.
This interface tries to define an imprecise concept: how fast is fast? The
documentation provides a simple guide: if repeated access using the
List.get()
method is faster than repeated access using the
Iterator.next()
method, then the List has fast random access. The
two types of access are shown in the following code examples:
Object o;
for (int i=0, n=list.size(); i < n; i++)
o = list.get(i);
Object o;
for (Iterator itr=list.iterator(); itr.hasNext(); )
o = itr.next();
There is a third loop that combines the previous two loops to avoid the
repeated Iterator.hasNext()
test on each loop iteration.
Object o;
Iterator itr=list.iterator();
for (int i=0, n=list.size(); i < n;!
i++)
o = itr.next();
This last loop relies on the normal situation, where List objects cannot
change in size while they are being run without an exception of some sort
occuring. So, since the loop size remains the same, you can simply count the
accessed elements without testing at each iteration whether the end of the list
has been reached. This last loop is generally faster than the one in Example 2.
In the context of the RandomAccess
interface, the first loop using
List.get()
should be faster than both of the loops that use
Iterator.next()
for a list to implement
RandomAccess
.
How is RandomAccess
used?
So now that we know what RandomAccess
means, how do we use it?
With the other two marker interfaces, Serializable
and
Cloneable
, there are two aspects to using them:
- Defining classes which implement them, and
- Using their capabilities via
ObjectInput/ObjectOutput
andObject.clone()
.
RandomAccess
is a little different. Of course, we still need to
decide whether any particular class implements it, but the possible classes are
severely restricted: RandomAccess
should only be implemented in
java.util.List
classes. And most such classes are created outside
of projects; e.g., the SDK provides the most frequently used implementations,
and subclasses of the SDK classes do not need to implement
RandomAccess
, as they will automatically inherit the capability
where appropriate.
The second aspect, using the RandomAccess
capability, is also
different. Whether a class is Serializable
or
Cloneable
is automatically detected when you use
ObjectInput/ObjectOutput
and Object.clone()
. But
RandomAccess
has no such automatic support. You need to explicitly check whether a class implements RandomAccess
using the
instanceof
operator:
if (listObject instanceof RandomAccess)
Then you must explicitly choose the appropriate access method,
List.get()
or Iterator.next()
. Clearly, if we test for
RandomAccess
on every loop iteration, we would be making a lot of
redundant calls, and probably losing the benefit of RandomAccess
as
well. So the pattern to follow in using RandomAccess
makes the test
outside the loop. The canonical pattern looks like:
Object o;
if (listObject instanceof RandomAccess)
{
for (int i=0, n=list.size(); i < n; i++)
{
o = list.get(i);
//do something with object o
}
}
else
{
Iterator itr = list.iterator();
for (int i=0, n=list.size(); i < n; i++)
{
o = itr.next();
//do something with object o
}
}
The speedup from using RandomAccess
Related Reading
|
I tested the four code loops shown in this article, using the 1.4 beta
release, separately testing the -client
and -server
options. To test the effect of the RandomAccess
interface, I used
the java.util.ArrayList
and java.util.LinkedList
classes. ArrayList
implements RandomAccess
, while
LinkedList
does not. ArrayList
has an underlying
implementation consisting of an array with constant access time for any element,
so using the ArrayList
iterator is equivalent to using the
ArrayList.get()
method, but with some additional overhead.
LinkedList
has an underlying implementation consisting of linked
node objects, so it has access time proportional to the shortest distance of the
element from either end of the list; iterating sequentially through the list can
shortcut the access time by traversing one node after another.
Pages: 1, 2 |
