|
|
This straightforward program is about a quarter the size (in lines of source code) of tsort, so one should not be surprised to find that it runs substantially more slowly.
In practice, however, this is not the case. For very small inputs, tsort is faster because String input may be relatively slow. However, for larger inputs, the logarithmic behavior of maps wins over the quadratic behavior of the algorithm used in tsort.
As an example, we used two sets of test data. Because topological sorting is often used on program dependencies, we generated our test data from two actual load module libraries: the C library on our system (a VAX 8550 running System V release 2) and the PORT library of mathematical software. Here are the results:
| C | PORT | |
| total relations | 742 | 6,513 |
| distinct tokens | 248 | 1,505 |
| tsort execution time | 1.0 | 97.5 |
| C++ program execution time | 0.6 | 8.2 |
The first two lines in the table characterize the size of the problem in terms of the total number of relations and the number of distinct tokens in the input data. The next two lines give the execution time, in seconds, to process each set of data. Note that the C++ program is considerably faster on both samples; the difference on the larger sample is more than a factor of ten.