Algorithms in a Nutshell

Precision

Instead of using millisecond-level timers, nanosecond timers could be used. On the Java platform, the only change in the earlier timing code would be to invoke System.nanoTime( ) instead of accessing the milliseconds. To understand whether there is any correlation between the millisecond and nanosecond timers, the code was changed as shown in Example A-9.

Example A-9. Using nanosecond timers in Java

TrialSuite tsM = new TrialSuite(  );
TrialSuite tsN = new TrialSuite(  );
for (long len = 1000000; len <= 5000000; len += 1000000) {
    for (int i = 0; i < 30; i++) {
        long nowM = System.currentTimeMillis(  );
        long nowN = System.nanoTime(  );
        long sum = 0;
        for (int x = 0; x < len; x++) { sum += x; }
        long endM = System.currentTimeMillis(  );
        long endN = System.nanoTime(  );

tsM.addTrial(len, nowM, endM);
        tsN.addTrial(len, nowN, endN);
    }
}

Table A-3, shown earlier, contains the millisecond results of the timings, and Table A-7 contains the results when using the nanosecond timer. The clearest difference is that the standard deviation has shrunk by an order of magnitude, thus giving us much tighter bounds on the expected execution time of the underlying code. One can also observe, however, that the resulting timings still have issues with precision—note the large standard deviation for the n=5,000,000 trial. This large deviation corresponds with the "spike" seen in this case in Table A-3.

Table A-7. Results using nanosecond timers

n	average	min	max	stdev	#
1,000,000	8.4833	8.436	18.477 ...