19
$\begingroup$

I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. Why can't we compare which one is better by running both programs and counting the total time needed to run the algorithms?

$\endgroup$
  • $\begingroup$ Welcome! I hope that most such papers don't use runtimes. I know some do, though, especially in the more applied communities and when the considered systems are very complex. $\endgroup$ – Raphael Aug 12 '12 at 0:15
14
$\begingroup$

This is actually a deep issue that has some methodic and some pragmatic answers. I assume you want to know something about the algorithm(s) at hand. If you want to know which algorithm works better on a given machine on given inputs, go ahead and measure runtimes. If you want to compare the quality of a compiler for a given algorithm, go ahead and measure runtimes. For learning something about the algorithm, don't do it.

Let me first give some reasons why using runtimes is not a good idea.

  1. Generality
    Runtimes measured using one language and one compiler on one machine have little meaning if you change any component. Even slightly different implementations of the same algorithm may perform differently because you trigger some compiler opimisation in on case but not in the other.
  2. Prediction
    So you have a couple of runtimes for some inputs. What does that tell about the runtime of some other input? In general, nothing.
  3. Significance
    Usually, you won't benchmark all inputs (of some size), so that immediately restricts your ability to compare algorithms: maybe your test set triggered the worst case in one and the best case in the other algorithm? Or maybe your inputs were too small to exhibit the runtime behaviour.
  4. Metering
    Measuring runtimes well is not trivial. Is there a JIT? Has there been contention, i.e. are you counting time the algorithm did not even run? Can you reproduce exactly the same machine state for another run (of the other algorithm), in particular concurrent processes and caches? How is memory latency dealt with?

I hope these convinced you that runtimes are a horrible measure to compare algorithms, and that some general, abstract method for investigating algorithm runtime is needed.

On to the second part of the question. Why do we use comparisons or similar elementary operations?

  1. Analytic tractability
    Assuming you want to do formal analysis, you have to be able to do it. Counting individual statements is very technical, sometimes even hard; some people do it nevertheless (e.g. Knuth). Counting only some statements -- those that dominate the runtime -- is easier. For the same reason, we often "only" investigate (upper bounds on) worst-case runtime.

  2. Dominance
    The selected operation dominates the runtime. That does not mean that it contributes the most runtime -- comparisons clearly do not, e.g. in Quicksort when sorting word-sized integers. But they are executed the most often, so by counting them you count how often the most executed parts of the algorithm are run. Consequently, your asymptotic runtime is proportional to the number of dominant elementary operations. This is why we are comfortable using Landau notation and the word "runtime" even though we only count comparisons.

Note that it can be useful to count more than one operation. For example, some Quicksort variants take more comparisons but less swaps than others (on average).

For what it's worth, after you have done all the theory you might want to revisit runtimes in order to verify that the predictions your theory makes are sound. If they are not, your theory is not useful (in practice) and has to be extended. Memory hierarchy is one of the first things you realise is important but missing in basic analyses.

$\endgroup$
  • 1
    $\begingroup$ Keep in mind that formal analysis has its limits, too. For example, the average case for non-uniform input distributions is oftentimes intractable. $\endgroup$ – Raphael Aug 12 '12 at 0:17
10
$\begingroup$

This is because the total time to run the algorithms has a dependency on the hardware in which it is ran on along with other factors. It is not reliable to compare two algorithms if one is running on a Pentium 4 and the other running on, let's say, a Core i7. Not only this, but let's say you ran both on the same computer. What's to say that they both have the same amount of processor time? What happens if some other process has a higher priority than the process of the one of the algorithms?

To get past this, we decouple away from this overall time to complete, and instead comparing based on how well the algorithm scales. You may have noticed notation such as O(1) or O(n^2) in the research papers. This may require a bit more reading, if you are interested see Big O notation.

$\endgroup$
  • 1
    $\begingroup$ Also the actual running time depends on the size and the content of the actual input used to run the algorithms! $\endgroup$ – Tsuyoshi Ito Aug 11 '12 at 21:47
7
$\begingroup$

Since the other answers explain why we analyze runtime in terms of number of elementary operations, let me offer a couple of reasons for why comparisons are the right metric of many (not all) sorting algorithms:

  • for many sorting algorithms the number of comparisons dominates the running time, i.e. at least as many comparisons are performed as any other elementary operation
  • comparisons are the expensive operation; think about how a sorting routine is implemented in library: the sort function is passed an array of elements and a pointer to a function that compares two elements; in general calling and waiting for the compare function to execute is more expensive than "internal" operations; as this function is provided by the user, it's harder to optimize it
  • (this may or may not be a good reason for some) we can can say something interesting about the number of comparisons that are sufficient and necessary to sort a sequence; we know how to do this in the worst case and on average for various distributions, even how to design an algorithm that converges to optimal as it is run on items sampled iid from an unknown distribution (Self-Improving Algorithms); we know how to do this when some comparisons are given for free (Sorting with Partial Information)
$\endgroup$
  • $\begingroup$ 1) "at least as many comparisons are performed as any other elementary operation" -- only up to a constant factor. 2) "comparisons are the expensive operation" -- that assumes a generic setting. For integer sorting (which is usually analysed), swaps are typically more expensive. $\endgroup$ – Raphael Aug 12 '12 at 9:14
  • $\begingroup$ sure. op seemed to be confused about analysis of algorithms in general, didn't want to bring constant factors. i hope the fact that i am talking about a generic setting is clear from the description - the sort routine in a standard library is not integer sorting $\endgroup$ – Sasho Nikolov Aug 12 '12 at 9:32
  • $\begingroup$ plus the papers that op saw are definitely not about specialized integer sorting algorithms, there no one counts number of comparisons $\endgroup$ – Sasho Nikolov Aug 12 '12 at 9:33
  • $\begingroup$ @Raphael Sorting small integers is not a common issue in practice. I'll wager most sorting that goes on in the world is on strings (of some length or other). Even for integer sorting, I'm not sure if it's accurate that swaps are more expensive — branching is a relatively expensive operation on a modern high-end processor, seeing that branch prediction would be mostly useless when sorting. $\endgroup$ – Gilles 'SO- stop being evil' Aug 21 '14 at 14:19
  • $\begingroup$ @Gilles In itself, swaps are more expensive than integer comparisons than any platform I know. "Secondary" costs like e.g. branch mispredictions are definitely a factor, the impact of which is subject of ongoing research. (Regarding use in practice, I can't make a qualified statement. However, I observe that standard library maintainers keep improving the sorting algorithms they use for primitive datatypes so I assume that they see a lot of (ab)use.) $\endgroup$ – Raphael Aug 21 '14 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.