What's the fastest way to traverse all the elements of a Vector?

John Zukowski

If speed is of the essence, do not use a Vector. Instead, use an ArrayList. All accesses to a Vector are synchronized, whether you need it or not. If you know you aren’t accessing the structure from multiple threads, the ArrayList will be much faster.

With that said, what about if you need to stay with a Vector? There are at least four ways to traverse through all the elements of a Vector:

  • Using a for loop and accessing each element with elementAt(index) or get(index)
  • Using an Emumeration
  • Using an Iterator
  • Using an Enumeration/Iterator, but relying on an exception to catch ending

Of the four, there are neglible differences in performance. While looping through to a specific index is a little faster, you lose the flexibility of changing to another data structure at a later time. With the Enumeration / Iterator approach, there is the added cost to create the Enumeration/Iterator to walk through. With the exception approach, you are relying on NoSuchElementException to be thrown to catch the ending of the walk through. While creating the exception takes time, this approach avoids the repeated test of hasMoreElement(). As the structure gets larger, avoiding the test condition can save lots of time.

Added by Doug Bell:

You left out what is often the fastest means to sequence though the members of a Vector: get a copy of the elements in an array and sequence through the array. This results in either synchronized calls, after which there is not any method overhead at all:

    Object[] elements = vector.toArray();  // JDK 1.2


    Object[] elements;
    synchronized (vector) {  // needed if concurrently accessed
        elements = new Object[vector.size()];

Further, if you know the types of the elements in the Vector, you can put the copy of the elements in an array of the known type and eliminate the casting overhead necessary to cast the Object references to the known type.

JDK 1.1:

    MyType[] elements;
    synchronized (vector) {  // needed if concurrently accessed
        elements = new MyType[vector.size()];

JDK 1.2:

    MyType[] elements = new MyType[vector.size()];
    elements = (MyType[])vector.toArray(elements);

Note that while System.arraycopy() still needs to check the types of the objects when copying between arrays of different types, the check is performed much more efficiently than performing the cast operation on each element individually.

Getting an array of elements is faster than the other suggested approaches for vectors of more than a few elements. Although it does incur the overhead of instantiating a copy of the array and copying the elements, these operations generally take much less time than the repeated synchronization. As an added benefit (usually at least, depends on what you're trying to do) the process of iterating through the elements is predictable even in the presence of other threads which modify the vector. (You can also achieve this using any of the other techniques by placing the code that sequences the vector in a block synchronized on the Vector object.)

A fifth way actually exists that is faster for traversal, but requires additional setup and memory. Copy the elements out of the collection and into an array. You can even make the array the right data type.

0 Comments  (click to add your comment)
Comment and Contribute






(Maximum characters: 1200). You have 1200 characters left.



About | Sitemap | Contact