3

I'm testing if one algorithm is faster than another. I can carry on increasing the sample and use the Welch t-test to see if one of them is faster to confidence level. My problem is when to stop and declare them equal. Is there a way to do this with a Welch t-test? I guess I may need to say they are equal if they are within a certain time tolerance (say 0.1%) for the given confidence interval?

Many Thanks

Ant
  • 31
  • 1
  • Where is the variability here? If you repeat the algorithms many times do the results differ enough to measure the change in time. Do you run the algorithms the same number of times so that the sample sizes are equal? To use the t test you would want to have some idea that individual distributions are normal with the same variance. The Welch test would come into play if the variances are know to be different. – Michael R. Chernick Dec 23 '16 at 21:15
  • Its the time taken for an algorithm to run. I run the algorithms until I can return a result. I'm trying to use statistics to create a better unit testing library for performance. It seem to work well and quickly. – Ant Dec 23 '16 at 23:14
  • Why not just run each algorithm many times and declare the one that has a shorter total running time the winner? You may not need any statistical test. – Michael Lew Dec 24 '16 at 01:05
  • That's what performance libraries do at the moment. They run for say 10,000 runs and show you the results and you compare by eye. – Ant Dec 24 '16 at 10:22
  • I don't know the algorithms so I don't know how many runs should be done. Most libraries just make this an excessively large number. I want to not need this number and run until I can determine using stats which is faster. This will make testing performance much quicker and repeatable. – Ant Dec 24 '16 at 10:28

1 Answers1

3

This is an interesting problem, and one that has broad relevance. The answer revolves around the notion that this is not at its core a statistical question.

Given a large enough sample, any trivial difference in the speed of your algorithms can be found to be statistically significant at any desired level of statistical significance. (Note that this is only the case when there is a real difference in the speeds. See my answer here:Why does frequentist hypothesis testing become biased towards rejecting the null hypothesis with sufficiently large samples?)

However, as your question implies, at some level a small enough difference is effectively no practical difference. Thus the trick is to decide on a threshold for 'not large enough to care about' rather than to fob off the responsibility for decision onto a statistical routine.

I suggest that you decide on either a fractional difference or maybe an absolute time difference for your threshold. Then make sure that your sample is large enough that the upper end of a confidence interval for the difference between the mean speeds does not cross that threshold. (What level should your confidence interval be? That depends on the consequences of the decision might be, so note that you do not have to use a 95% interval.)

Community
  • 1
Michael Lew
  • 10,995
  • 2
  • 29
  • 47
  • Thanks. This is part of a unit testing library aimed at performance. Since there may be a number of performance tests the confidence interval has to be high to reduce the chance of false failures. I've chosen 99.99%. – Ant Dec 23 '16 at 23:23
  • Do you think welch t-test is incorrect here? It does seem sensible that I should be online checking the deviation against the variance and the welch t-test looks like it fits. – Ant Dec 23 '16 at 23:25
  • If you assume that the run times are normally distributed (or alternatively if your sample of run times is very large) and that the unknown variance differs between the algorithms then, yes, Welch's t-test should be OK. (I don't recommend a 99.99% confidence interval as it will be very, very wide. I suspect that I do not understand your purpose, or that you misunderstand my answer...) – Michael Lew Dec 24 '16 at 01:02
  • Sorry I may not have explained myself very well. This is to add performance testing to a unit testing library. I'd like to use stats to make this as quick and robust as possible and move away from just doing an excessive number of runs. – Ant Dec 24 '16 at 10:30