-3
$\begingroup$

I want to test how long it takes to run an algorithm.

So here is what I am doing:

  • close all the other un-needed applications, run my algorithms alone
  • considering some unstable computer system factors, run multiple times

As you can tell, I can get a set of running time t1, t2, t3, t4, ... , tn, so I'm asking:

  1. What to choose from t1, t2, t3, t4, ... , tn as my final result, median or average?
  2. Is this the right way to do this?

btw: my algorithm is actually a rendering algorithm, so it would be more complicated.

$\endgroup$
3
  • $\begingroup$ You've tested how long it takes. It takes any of t1 to tn. Any quantity derived from these is not answering your question. $\endgroup$
    – Spacedman
    Oct 14 '17 at 8:21
  • $\begingroup$ Where are those downvotes came from? $\endgroup$
    – xtluo
    Oct 14 '17 at 12:32
  • $\begingroup$ "Does not show any research effort" - have you researched the difference between mean and median? "It is unclear or not useful" - have you explained what you mean by "the right way" or what you are trying to achieve? Could you show the distribution of times you get? etc etc. There's a lot more you could do. $\endgroup$
    – Spacedman
    Oct 14 '17 at 12:33
5
$\begingroup$

You haven't asked a proper statistical question, so the choice of mean or median as "best" as a measure of your runtime is unanswerable.

Have you looked at the distribution of run times? Is the algorithm intrinsically variable in its run-time, or is it fixed in its run time but the run times differ because of noise caused by the OS doing other things? Do you want to remove that noise? What if the OS suddenly decides to swap to disk for a bit, or a big network data packet arrives, and the OS goes and does something for a few ms. You could get a long run time for one of your times, and that could pull the mean value way off.

The median is a robust estimator which means a single "bad" value can't throw it off. The mean can be thrown off by a single "rogue" value. Is that what you want? Maybe you do.

$\endgroup$
3
  • $\begingroup$ GOOD questions, thanks. But it seems impossible to remove the OS noise, so I need to run many times and decide what is the expected running time. $\endgroup$
    – xtluo
    Oct 14 '17 at 12:34
  • $\begingroup$ The "running time" is a random variable. You have to consider its distribution and form your questions as functions of its distribution to be meaningful. You can use the empirical distribution or model it (maybe its a gamma distribution). But what is "best" as a single summary is meaningless until you decide your criterion for "bestness". Minimising RMS error? Minimising absolute error? Considering noise? etc $\endgroup$
    – Spacedman
    Oct 14 '17 at 12:39
  • $\begingroup$ Yes, as you mentioned, the running time is a random variable, but it is a random variable in some certain range like [t1, tn]. And it may fit some kind of distribution, mostly like a Gaussian distribution. So if I want to get the most likely running time from its distribution, and choosing mean of the median value seems to make sense, right? or should I keep the distribution instead? $\endgroup$
    – xtluo
    Oct 14 '17 at 12:59
1
$\begingroup$

You should choose mean or average over median. Let me explain why, specifically in your case since you're checking for expected computational time.

Mean or average could be one of the three cases.

  1. Equal to the median
  2. Greater than the median
  3. Lesser than the median

Now if it is equal to the median there is no problem in choosing whichever value but in real time it's most likely to follow the other two cases. The reason the mean is greater or lesser than the median, in this case, is because it skews to either higher computational time or lower computational time. What this skew represents is you could say where the most likely frequency of computational times would be. This implies it gives a more normalized approach and it shows where you can expect the computational times of most of your execution runs expected to be.

So choose mean over median.

$\endgroup$
3
  • $\begingroup$ Brilliant. Thanks. Take this case as an example, [2,3,3,4,4,4,4,4,5,5,6], cause in this case, median value 4 appears a lot, so is it better choosing the median value? (I am using the median as my expectation time, for now.) $\endgroup$
    – xtluo
    Oct 14 '17 at 2:53
  • $\begingroup$ For this example you gave, It's the first case of my answer mean = median so it doesn't matter which value you take. But as I stressed before always represent it in terms of mean $\endgroup$ Oct 14 '17 at 5:11
  • 1
    $\begingroup$ Unless you get outliers in your data in which case you need a robust estimator like... the median. $\endgroup$
    – Spacedman
    Oct 14 '17 at 8:21
0
$\begingroup$

Typically 'How long an algorithm takes' is a set of outputs: Expected value for the expected performance and Maximum value for the worst case performance.

A time-critical application needs the Maximum value to prevent failures.

The Average value is the best indication of the expected performance and it is also the easiest to calculate.

$\endgroup$

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.