Timing

If we want to know which of two methods is faster, the most obvious approach is to time them. The TimeTest program (Figure 7-1) compares the get() methods from the ArrayList and LinkedList classes in the Java collections framework.

Lines 1416 of the method test() add many elements to list. We don't care what these elements are, so this is one of those rare occasions where it makes sense to create instances of the Object class.

To determine the time taken by line 18, we examine the clock before and after invoking get(). To get the current time, we invoke the static currentTimeMillis() method of the System class. For historical reasons involving the UNIX operating system, this is given as the number of milliseconds since midnight, January 1, 1970, Greenwich mean time. Because this is a very large number, the return type of currentTimeMillis() is long. A long is similar to an int, but its range is roughly ±1019.

Figure 7-1. The TimeTest class compares the get() methods of the ArrayList and LinkedList classes.

Unfortunately, running our program doesn't give us much information:

ArrayList: 0 milliseconds LinkedList: 0 milliseconds

Any modern computer is so fast that, on either of these data structures, the get() method takes less than one millisecond to run. A reasonable solution is to look at the time required to perform each operation a million times (Figure 7-2).

Figure 7-2. We can improve the resolution of our timing by performing the operation in question many times.

The exact result of running this program varies from one run to the next. For example, one run might give

ArrayList: 21 milliseconds LinkedList: 39 milliseconds

while another might give

ArrayList: 22 milliseconds LinkedList: 40 milliseconds

This variation is due to a number of factors beyond our control, such as how Java manages its memory (Chapter 16) and what other programs are running on our machine. We could try harder to control these conditions and apply various statistical techniques to determine which method is faster, but the short answer is that the method from ArrayList is roughly twice as fast as the method from LinkedList. They are both very fast, so this is not a big difference.

The story is different if we get element 50 instead of element 5. Now the method from LinkedList takes vastly longer:

ArrayList: 22 milliseconds LinkedList: 226 milliseconds

In retrospect, this is not surprising. In an ArrayList, get() jumps right to the array element in question. In a LinkedList, it is necessary to traverse all of the previous list nodes to find the one we want. Our timing experiment provides empirical evidence that the time to get element i of a LinkedList increases with i, while the time to get element i of an ArrayList is independent of i. If we need a List and get() is going to be a very common operation, an ArrayList is a good choice.

We now have some evidence that LinkedList search time increases with i, but a couple of data points are not really a convincing case. Rather than perform a more extensive battery of tests, we can use some formal, mathematical tools to make statements about the efficiency of an algorithm. Section 7.2 introduces these tools.

The material that follows is important for designing general-purpose algorithms and data structures. Empirical timing is still important in optimization.

Exercises