Algorithms in a Nutshell

(^334) | Appendix: Benchmarking
In raw numbers, the C implementation appears to be about three times faster. The
histogram results are not as informative, because the timing results include frac-
tional milliseconds, whereas the Java timing strategy reports only integer values.
The final table contains the results for Scheme. The variability of the execution
runs in the Scheme implementation is much higher than Java and C. One reason
may be that the recursive solution requires more internal bookkeeping of the
computation.
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.
Table A-5. Timing results of 30 computations in C
n average min max stdev #
1,000,000 2.6358 2.589 3.609 0.1244 28
2,000,000 5.1359 5.099 6.24 0.0672 28
3,000,000 7.6542 7.613 8.009 0.0433 28
4,000,000 10.1943 10.126 11.299 0.0696 28
5,000,000 12.7272 12.638 13.75 0.1560 28
Table A-6. Timing results of 30 computations in Scheme
n average min max stdev #
1,000,000 1173 865 1,274 7.9552 28
2,000,000 1921.821 1,824 2,337 13.1069 28
3,000,000 3059.214 2,906 3,272 116.2323 28
4,000,000 4040.607 3,914 4,188 81.8336 28
5,000,000 6352.393 6,283 6,452 31.5949 28
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( );
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use