Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Runtime prediction of real programs on real machines


Finkler,  Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Any fulltext), 220KB

Supplementary Material (public)
There is no public supplementary material available

Finkler, U., & Mehlhorn, K.(1996). Runtime prediction of real programs on real machines (MPI-I-1996-1-032). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-A40D-D
Algorithms are more and more made available as part of libraries or tool kits. For a user of such a library statements of asymptotic running times are almost meaningless as he has no way to estimate the constants involved. To choose the right algorithm for the targeted problem size and the available hardware, knowledge about these constants is important. Methods to determine the constants based on regression analysis or operation counting are not practicable in the general case due to inaccuracy and costs respectively. We present a new general method to determine the implementation and hardware specific running time constants for combinatorial algorithms. This method requires no changes of the implementation of the investigated algorithm and is applicable to a wide range of of programming languages. Only some additional code is necessary. The determined constants are correct within a constant factor which depends only on the hardware platform. As an example the constants of an implementation of a hierarchy of algorithms and data structures are determined. The hierarchy consists of an algorithm for the maximum weighted bipartite matching problem (MWBM), Dijkstra's algorithm, a Fibonacci heap and a graph representation based on adjacency lists. ion frequencies are at most 50 \% on the tested hardware platforms.