I need to compare average runtime execution of two different C++ algorithms. The question is: how many times do I need to repeat the experiment in order to calculate the average runtime for each algorithm? 10? 100 times? Can you provide me with a paper regarding this issue? Thanks in advance!
Standard statistics. Depends on what degree of variability you can tolerate. The standard error is proportional to 1/variance. So for 10% standard error (i.e. Within 10% of the true value) will require 100 experiments. For 1%, then 10000 measurements. People never like the conclusions, but the math is simple.
Standard statistics. Depends on what degree of variability you can tolerate. The standard error is proportional to 1/variance. So for 10% standard error (i.e. Within 10% of the true value) will require 100 experiments. For 1%, then 10000 measurements. People never like the conclusions, but the math is simple.
Thank you Alan!
Do you know any paper or book supporting your answer?
Best regards!
Buenos Dias, Erick. Any standard statistics book should help. In my undergrad days I used'Mathematics and statistics for chemists' by Brooke's. Alternatively search simply on 'standard error' and you'll bring up appopriate Wiki and academic links.
your comparison will be biased because you are comparing two different algorithms that require different parameters for their execution. So you can't properly adjudge one to be more efficient than the other based on the above premise.
I would like to suggest to use the SUSA code:
http://www.grs.de/en/simulation-codes/susa
This kind of situation is well match with Monte Carlo simulation where it needs a large runtime of the simulation to reduce the error and most paper considered 10,000 repetation is sufficient.
Most of the answers here focus on the number of trials needed to guarantee that the variability of the execution time of one algorithm is less than a given number. Here are other aspects you need to consider.
Best case/worst case scenario:
- A standard Quick Sort algorithm has average complexity of N*Log(N) but worst case performance of N^2.
- The structure of your data set might influence greatly the results you get. You might need to run different kind of experiments based of this to quantify the best/worst case performance.
Effective Big-O complexity:
- Even though theoretical Big-O complexity is not a guarantee of best performance because of hardware issues like data locality (cache miss, etc) can have bigger impacts yet, they provide a rough starting point.
- If the 2 algorithms you are trying to compare really have different "effective Big-O complexity", you will be able to tell quite fast even with only a few run (say 10) for each sample size (say 10^3, 10^4, 10^5, 10^6...) . The idea is that with sufficiently big data sets, the performance difference caused by the effective Big-O complexity of the algorithm will be FAR bigger than the individual variability you were trying to minimize. If not, the two algorithms have essentially the same complexity and choosing one over the other must be done based on other factors like: ease of implementation, possibility of parallelization (CPU or GPU), availability of specialized library, etc.
Regards
Besides the great information provided by the others, there are also pragmatic things to consider. For instance, if your algorithm accesses the hard drive for reading, you may find that the first run is the slowest, because in subsequent runs, the files your program wants to read are in the OS file cache in RAM, and the data is accessed MUCH faster.
In this situation, if the algorithm will usually be ran when the OS file cache is cold, your results are going to under represent disk access times by quite a bit.
There are similar issues with other hardware and software - such as the GPU for instance, which may not actually have a shader prepared until first use, and first use again, would be much more costly than subsequent uses.
I've found it useful to report the mean, the worst and/or best time and also the variance sometimes, as these things will show more information than a simple mean will.
But, for most accurate profiling, it's important to think about details like those I mentioned, or else you will risk profiling something very different from the actual common usage case.
Hi Alan,
Thank you for your response. But when you say "mean", how many repetitions do you need to consider to provide an useful mean (with a variance) value??
My answer is just meant to add to what the other folks have said. Use their advice for sample count, but I wanted to point out that there is more to an accurate profile than just considering a sample count. Specifically that reporting any or all of min,max,variance can make a big difference, and also some understanding about what the machine is doing underneath you that may impact your samples in a way that is different than what you actually intend to measure - such as disk i/o time being drastically under-reported.
- Badges
- Science topic
- Similar topics
- Mathematics
- Statistics