2
$\begingroup$

I want to learn how to use statistics to help me choose between two equivalent code. I want to choose the "fastest", the one that would take the less time to execute.

How should I collect data? And what test should I use to help me decide?

Let's take a concrete example, you have two ways to compute the double of a number n:

f(n) = n + n
g(n) = n * 2

How would you collect data? Should you:

  1. Take a random number n, compute f(n) et g(n) 1000 times, recording each time the amount of time it took.
  2. Take 1000 random numbers, compute f(n) and g(n) for each of those numbers one time.
  3. Take 1000 random numbers, compute 1000 times f(n) and g(n) for each of those numbers.

(I wrote 1000, but I don't know how many samples would be reasonable)

Now, for that set of data, what test should I choose?

I wrote "fastest" with quotes before, because I don't really know what it means in mathematical terms. Do we want to compare the fastest time between the f set and the g set? Do we want to get the fastest on average? What about errors in the dataset?

With some google search, I saw that the Student T-Test would be reasonable. But I would not know which one to choose, since I don't quite understand the concept of a dependent/independent variable, paired/not paired.

Also I read this answer: https://stats.stackexchange.com/a/139405/232833

saying that: "You should not use Student's T-test as it has a lot of assumptions which you can easily and unknowingly violate. It is much better so use some nonparametric tests."

(What are the assumptions that can easily be violated? What nonparametric test to choose?)

I've chosen f and g to understand more about the statistical method to choose the fastest one (so I can apply that with more complex codes/problems). I'm not really interested by programming tips.

$\endgroup$
  • $\begingroup$ Packages such as microbenchmark in R seem to do a lot of what you are after. $\endgroup$ – Christoph Hanck Jan 2 at 15:54
  • $\begingroup$ 1. What you might want to compare depends on the circumstances. If its a small piece of code people will use many many times, comparing means makes sense. If it's something a person will only run once in their lives but it takes a long time, they may find the mode much more relevant ("how long am I most likely to wait?") or indeed the median might be more relevant (or in some cases some other location-measure, such as some upper quantile). ... ctd $\endgroup$ – Glen_b Jan 3 at 5:21
  • $\begingroup$ ctd... 2. There's very likely no need to test; presumably you can generate as much data as required to accurately estimate the expected ratio of times (or whatever else you care to know) under any particular set of conditions, so hypothesis testing would be beside the point. The exception would be where the runs are expensive (in some sense, such as time) and you'd only be able to collect a relatively small sample. $\endgroup$ – Glen_b Jan 3 at 5:21
1
$\begingroup$

You can certainly use a $t$-test since you can (presumably) accumulate as much data as you want, and so the central limit theorem will have had enough time to kick in. As far as the amount of data that you need, that depends on how much of a difference in runtime you're trying to detect, and how much the runtime varies across independent executions. You can see this by looking at the definition of the $t$ statistic for two independent samples:

$$ \frac{\bar{x}_1 - \bar{x}_2}{\sqrt{s^2_1 / n_1 + s^2_2 / n_2}} . $$

The smaller the difference you want to detect ($|\bar{x}_1 - \bar{x}_2|$), or the greater the variability in runtime ($s_1$ and $s_2$), the more data you need ($n_1$ and $n_2$). Again since you're generating the data yourself, you can probably simulate enough to alleviate these concerns.

I think however that the important questions you want to answer are mostly not statistical in nature. The time it takes the program to run will also depend on the nature of the inputs as well as the computer architecture used. Are there certain sets of inputs that you can reasonably expect the program to be given? What happens when the program is given very large inputs compared to small inputs, and how likely are these input sizes? Does the winner change as the size of the input changes? This could happen if (say) you had two programs with runtimes as follows:

$$ T_1(n) = n \\ T_2(n) = 0.001 \cdot n^2 . $$

If you look at small inputs program one will appear to be slower, even though it is asymptotically faster. This also shows how you can't necessarily use the conclusion of your experiment to say something about wildly different inputs. Unless you are fairly sure about the constraints under which the program will run, it might be wise to perform several large experiments under different settings to see if and how the results change.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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