hide
Free keywords:
-
Abstract:
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.
