3
$\begingroup$

I'd like to compare the execution speed of two different methods (say foo and bar in some language like Ruby). I wish I was more knowledgeable in stats to tackle this problem...

I am tempted to compare the means of the time taken by foo and bar over a number of samples, but I'm thinking it might be more appropriate to compare the minimum values measured.

I imagine we can assume that, for a given platform, there is an absolute minimum of time required for the execution of foo and bar (let's call them min(foo) and min(bar)) and that what I'm really after is their ratio. I should be getting values always which are min(foo) + ∆_i, where ∆_i >= 0 and has some known distribution? What would this distribution be?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Why are you thinking it might be more appropriate to compare the minimum values? I would have thought it was more appropriate to compare typical values rather than best-case execution times. $\endgroup$
    – onestop
    Jan 23, 2012 at 12:59
  • $\begingroup$ @onestop: Ideally, best-case execution times should yield the same ratio as typical values, I'm not sure. I thought that maybe best-case execution times might be possible to figure out more accurately? Also, I can't assume that typical values are normal, as there has to be a best-case minimum, no? $\endgroup$
    – Marc-André Lafortune
    Jan 23, 2012 at 13:39

3 Answers 3

Reset to default
1
$\begingroup$

It depends on what you are measuring. If the different runs are on different input data, it makes sense to compare the mean values to get average expected run times (i.e., the $\Theta(n)$ in algorithm analysis). Or may be the maximum to get the worst case analysis (the big Oh notation $O(n)$).

If the different runs are on identical data, and you are measuring wall-time rather then CPU time used by the process, minimums might be useful to get rid of the effect of other processes.

Improve this answer
$\endgroup$
1
$\begingroup$

I agree with @highBandWidth, that if different runs use identical data that the minimum is the important value. I don't think any standard distribution describes the difference of sample minimums, although a further look into the extreme value theory literature might reveal something.

If you want to determine if a difference in sample minimums is statistically significant you can use a modified bootstrap procedure called the m out of n bootstrap described and discussed here

Improve this answer
$\endgroup$
0
$\begingroup$

You can compare the five number summaries of each sample. Also a boxplot can be informative.

Improve this answer
$\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.