Examples from the paper A Fast Generic Sequence Matching
Algorithm show two approaches to measuring
performance of generic algorithms. The first is measuring actual
computing times by using the standard clock function from the
<ctime> header (alternatively known as <time.h>), in
the programs in Appendices B.6 and B.7. The main issue here is
properly setting up executions of several different algorithms on the
same data in order to compare them fairly, with enough repeated calls
of each of the algorithms to result in an accurately measurable time.
The second approach is obtaining counts of the principal operations of
each of the concepts that parameterize the algorithms (as discussed
earlier for expressing performance requirements in Algorithm
Concepts for Standard Libraries). A test program for
this purpose for the sequence matching algorithms is given in Appendix
B.8: it is designed to record counts of value assignments and
comparisons, iterator operations, and certain integer operations.
Here again is the directory of files related to this paper, as updated
since the last class:
gensearch directory
[Note: I've revised all the code for correctness and timing to bring
it up to data with the C++ standard, but I'm still in the middle of
revising the code in Appendix B.8 for the counting measurements, so
it is currently not working.]
|