Java Cookbook, Second Edition

New developers sometimes worry about the overhead of these collections and think they should use arrays instead of data structures. To investigate, I wrote a program that creates and accesses 250,000 objects, once through a Java array and again through an ArrayList. This is a lot more objects than most programs use. First the code for the Array version:

import com.darwinsys.util.MutableInteger; /** Time a bunch of creates and gets through an Array */ public class Array { public static final int MAX = 250000; public static void main(String[] args) { System.out.println(new Array( ).run( )); } public int run( ) { MutableInteger list[] = new MutableInteger[MAX]; for (int i=0; i<list.length; i++) { list[i] = new MutableInteger(i); } int sum = 0; for (int i=0; i<list.length; i++) { sum += list[i].getValue( ); } return sum; } }

And the ArrayList version:

import java.util.ArrayList; import com.darwinsys.util.MutableInteger; /** Time a bunch of creates and gets through an Array */ public class ArrayLst { public static final int MAX = 250000; public static void main(String[] args) { System.out.println(new ArrayLst( ).run( )); } public int run( ) { ArrayList list = new ArrayList( ); for (int i=0; i<MAX; i++) { list.add(new MutableInteger(i)); } int sum = 0; for (int i=0; i<MAX; i++) { sum += ((MutableInteger)list.get(i)).getValue( ); } return sum; } }

The Vector-based version, ArrayVec , is sufficiently similar that I don't feel the need to kill a tree reprinting its code it's online.

How can we time this? As covered in Recipe 25.5, you can either use the operating system's time command, if available, or just use a bit of Java that times a run of your main program. To be portable, I chose to use the latter on an older, slower machine. Its exact speed doesn't matter since the important thing is to compare only versions of this program running on the same machine.

Finally (drum roll, please), the results:

$ java Time Array Starting class class Array 1185103928 runTime=4.310 $ java Time ArrayLst Starting class class ArrayLst 1185103928 runTime=5.626 $ java Time ArrayVec Starting class class ArrayVec 1185103928 runTime=6.699 $

Notice that I have ignored one oft-quoted bit of advice that recommends giving a good initial estimate on the size of the ArrayList. I did time it that way as well; in this example, it made a difference of less than four percent in the total runtime.

The bottom line is that the efficiency of ArrayList is not totally awful compared to arrays. Obviously there is more overhead in calling a "get" method than in retrieving an element from an array. The overhead of objects whose methods actually do some computation probably outweighs the overhead of fetching and storing objects in an ArrayList rather than in an Array. Unless you are dealing with large numbers of objects, you may not need to worry about it. Vector is slightly slower but still only about two-thirds the speed of the original array version. If you are concerned about the time, once the "finished" size of the ArrayList is known, you can convert the ArrayList to an array (see Recipe 7.12).