Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 787

we would expect to see far larger input datasets than this, so this runtime isn't accept-
able for general use.
Studying a piece of code and trying to figure out how to speed it up can be decep-
tively difficult. It's tempting to approach the problem by looking at each line of code
and trying to reduce the amount of computation it performs. For example, you may
have noticed that our range method actually examines every pair of elements in the
array twice: For unique integers i and j , we examine the pair of elements at indexes
( i , j ) as well as the pair at ( j , i ).
We can perform a minor modification to our range methods code by starting each
inner j loop ahead of i , so that we won't examine any pair ( i , j ) where i - j .
Performing minor modifications like this is sometimes called tweaking an algorithm.
The following code implements our tweaked version of the range algorithm:

public static int range2(int[] numbers) {
int maxDiff = 0;
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
int diff = Math.abs(numbers[j] - numbers[i]);
maxDiff = Math.max(maxDiff, diff);

}

}
return maxDiff;

}

Since about half of the possible pairs of i / j values are eliminated by this tweak,
we'd hope that the code would run about twice as fast. Figure 13.3 shows its actual
measured runtime. As we estimated, the second version is about twice as fast as the
first. We could implement other minor tweaks, such as replacing the Math.max call
with a simple if test (which would speed up the algorithm by around 10% more), but
there's a more important point to be made. When the input size doubles, the runtime
of either version of the algorithm roughly quadruples. Consequently, regardless of
which version we use, if the input array is very large the method will be too slow.

1000
2000
4000
8000
16000
32000
64000

N Runtime (ms)

16
16
110
406
1578
6265
25031

30000
25000
20000
15000
10000
5000
0

Input size (N)

Figure 13.3

Runtimes for second version of range algorithm