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; } }
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 Section 25.6, 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 of
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 almost as good (75%) as that of
arrays. The overhead of objects whose methods actually do some
computation will almost certainly outweigh it. Unless you are dealing
with millions of objects per minute, you probably don’t need to
worry about it. Vector
is slightly slower, but
still only about two-thirds the speed of the
original array
version.
3.138.123.106