Empirical algorithmics

In computer science, empirical algorithmics (or experimental algorithmics) is the practice of using empirical methods to study the behavior of algorithms. The practice combines algorithm development and experimentation: algorithms are not just designed, but also implemented and tested in a variety of situations. In this process, an initial design of an algorithm is analyzed so that the algorithm may be developed in a stepwise manner.

Overview

Methods from empirical algorithmics complement theoretical methods for the analysis of algorithms. Through the principled application of empirical methods, particularly from statistics, it is often possible to obtain insights into the behavior of algorithms such as high-performance heuristic algorithms for hard combinatorial problems that are (currently) inaccessible to theoretical analysis. Empirical methods can also be used to achieve substantial improvements in algorithmic efficiency.

American computer scientist Catherine McGeoch identifies two main branches of empirical algorithmics: the first (known as ''empirical analysis'') deals with the analysis and characterization of the behavior of algorithms, and the second (known as ''algorithm design'' or ''algorithm engineering'') is focused on empirical methods for improving the performance of algorithms. The former often relies on techniques and tools from statistics, while the latter is based on approaches from statistics, machine learning and optimization. Dynamic analysis tools, typically performance profilers, are commonly used when applying empirical methods for the selection and refinement of algorithms of various types for use in various contexts.

Research in empirical algorithmics is published in several journals, including th
ACM Journal on Experimental Algorithmics
(JEA) and th
Journal of Artificial Intelligence Research
(JAIR). Besides Catherine McGeoch, well-known researchers in empirical algorithmics include Bernard Moret, Giuseppe F. Italiano, Holger H. Hoos, David S. Johnson, and Roberto Battiti.

Performance profiling in the design of complex algorithms

In the absence of empirical algorithmics, analyzing the complexity of an algorithm can involve various theoretical methods applicable to various situations in which the algorithm may be used. Memory and cache considerations are often significant factors to be considered in the theoretical choice of a complex algorithm, or the approach to its optimization, for a given purpose. Performance profiling is a dynamic program analysis technique typically used for finding and analyzing bottlenecks in an entire application's code or for analyzing an entire application to identify poorly performing code. A profiler can reveal the code most relevant to an application's performance issues.

A profiler may help to determine when to choose one algorithm over another in a particular situation. When an individual algorithm is profiled, as with complexity analysis, memory and cache considerations are often more significant than instruction counts or clock cycles; however, the profiler's findings can be considered in light of how the algorithm accesses data rather than the number of instructions it uses.

Profiling may provide intuitive insight into an algorithm's behavior by revealing performance findings as a visual representation. Performance profiling has been applied, for example, during the development of algorithms for matching wildcards. Early algorithms for matching wildcards, such as Rich Salz' wildmat algorithm, typically relied on recursion, a technique criticized on grounds of performance. The Krauss matching wildcards algorithm was developed based on an attempt to formulate a non-recursive alternative using test cases followed by optimizations suggested via performance profiling, resulting in a new algorithmic strategy conceived in light of the profiling along with other considerations. Profilers that collect data at the level of basic blocks or that rely on hardware assistance provide results that can be accurate enough to assist software developers in optimizing algorithms for a particular computer or situation. Performance profiling can aid developer understanding of the characteristics of complex algorithms applied in complex situations, such as coevolutionary algorithms applied to arbitrary test-based problems, and may help lead to design improvements.

See also

* Algorithm engineering
*Analysis of algorithms
*Profiling (computer programming)
*Performance tuning
*Software development

References

{{reflist

Analysis of algorithms
Empiricism