Algorithms in a Nutshell

323

AppendixBenchmarking

APPENDIX

Benchmarking

Each algorithm in this book is presented in its own section where you will find

individual performance data on the behavior of the algorithm. In this bench-

marking chapter, we present our infrastructure to evaluate algorithm

performance. It is important to explain the precise means by which empirical data

is computed, to enable the reader to both verify that the results are accurate and

understand where the assumptions are appropriate or inappropriate given the

context in which the algorithm is intended to be used.

There are numerous ways by which algorithms can be analyzed. Chapter 2

presented the theoretic formal treatment, introducing the concepts of worst-case

and average-case analysis. These theoretic results can be empirically evaluated in

some cases, though not all. For example, consider evaluating the performance of

an algorithm to sort 20 numbers. There are 2.43*10^18 permutations of these 20

numbers, and one cannot simply exhaustively evaluate each of these permuta-

tions to compute the average case. Additionally, one cannot compute the average

by measuring the time to sort all of these permutations. We find that we must rely

on statistical measures to assure ourselves that we have properly computed the

expected performance time of the algorithm.

Statistical Foundation

In this chapter we briefly present the essential points to evaluate the performance

of the algorithms. Interested readers should consult any of the large number of

available textbooks on statistics for more information on the relevant statistical

information used to produce the empirical measurements in this book.

To compute the performance of an algorithm, we construct asuiteofTindepen-

denttrialsfor which the algorithm is executed. Each trial is intended to execute an

algorithm on an input problem of sizen. Some effort is made to ensure that these

trials are all reasonablyequivalentfor the algorithm. When the trials are actually

identical, then the intent of the trial is to quantify the variance of the underlying

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