O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Reporting

It is instructive to review the actual results when computed on the same platform, in this case a Linux 2.6.9-67.0.1.ELsmp i686 (this machine is different from the desktop PC and high-end computer mentioned earlier in this chapter). We present three tables (Tables A-3, A-5, and A-6), one each for Java, C, and Scheme. In each table, we present the millisecond results and a brief histogram table for the Java results.

Table A-3. Timing results of 30 computations in Java

n

average

min

max

stdev

#

1,000,000

8.5

8

18

0.5092

28

2,000,000

16.9643

16

17

0.1890

28

3,000,000

25.3929

25

26

0.4973

28

4,000,000

33.7857

33

35

0.4179

28

5,000,000

42.2857

42

44

0.4600

28

The aggregate behavior of Table A-3 is detailed in histogram form in Table A-4. We omit from the table rows that have only zero values; all nonzero values are shaded in the table.

Table A-4. Individual breakdowns of timing results

time (ms)

1,000,000

2,000,000

3,000,000

4,000,000

5,000,000

8

15

0

0

0

0

9

14

0

0

0

0

16

0

2

0

0

0

17

0

28

0

0

0

18

1

0

0

0

0

25

0

0

18

0

0

26

0

0

12

0

0

33

0

0

0

7

0

34

0

0

0

22

0

35

0

0

0

1

0

42

0

0

0

0

21

43

0

0

0

0

8

44

0

0

0

0

1

To interpret these results for Java, we turn to statistics. If we assume that the timing of each trial is independent, then we refer to the confidence intervals described earlier. If we are asked to predict the performance of a proposed run for n=4,000,000, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required