<p>I believe what you're looking for is the field of Experimental Algorithmics. There is a <a href="http://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/guide-experimental-algorithmics">text by McGeoch</a>, an <a href="http://www.jea.acm.org/">ACM Journal</a>, and a <a href="https://cstheory.stackexchange.com/questions/822/a-reading-list-on-experimental-algorithmics">previous question</a> on this site that provides a reading list for the field.</p>

CC BY-SA 3.0
2015-11-28T10:00:38.333Z
In my case, the input is a directed acyclic graph. In that case, if I generate random graphs, the output may not necessarily generate normal distribution. Am I right in this case?
user571376
CC BY-SA 3.0
2015-11-28T21:28:28.457Z
I can't really speak to your situation, just the fact that a whole area of research exists to address the performance of algorithms in practice. You packed 4 questions into your one question, and I was just addressing the general reference request part.
Logan Mayfield
CC BY-SA 3.0
2015-11-28T02:20:13.197Z
2015-11-28T02:20:13.197Z
Logan Mayfield
<p>Let $A$ be a heuristic algorithm for problem $Q$.
I want to evaluate the performance of my algorithm in a 
specific practical environment and
compare it to other algorithms.
Is there a rigorous framework for comparison of algorithms in practice?</p>

<p>One method to evaluate the performance and compare it with other algorithms
is to run them on randomly generated inputs from a distribution
(based on actual inputs or a theoretical model of inputs) and
measure the average running time of the algorithms.
However I want to be able to express that one algorithm is better than other one
in stronger sense than just having better expected running time.</p>

<p>What do people use for to express stronger conditions?
Would standard deviation be a useful for this purpose?
What is the best way to measure the confidence level of the performance? </p>

<p>Are the any references (books/surveys/tutorials/...) on how to compare the performance of algorithms in practice?</p>

CC BY-SA 3.0
2015-11-27T05:48:22.890Z
Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see [help center](http://cstheory.stackexchange.com/help/on-topic). Your question might be suitable for [Computer Science](http://cs.stackexchange.com/) which has a broader scope. If you post your question there, make sure to follow the cross-posting guidelines of both sites.
chazisop
CC BY-SA 3.0
2015-11-28T00:45:42.763Z
@chazisop, I think this is a good and on-topic question. There are many problems that we only have heuristics (or heuristics perform better than non-heuristic algorithms or algorithms with worst theoretical analysis perform better than those with better theoretical analysis).
Kaveh
CC BY-SA 3.0
2015-11-29T01:29:44.837Z
Yes and no. The edited question is a well-known question in heuristics research AFAIK, but on the other hand it is too broad (essentially it is the starting point for a large body of research). But imho the edit is far in meaning and intent from the original question which while had the merit to be narrow, was simply asking on how to measure the expected running time of a scheduling algorithm on random inputs, which is a standard topic.
chazisop
CC BY-SA 3.0
2015-11-30T18:00:41.867Z
try [putting the science back in CS](http://www.cs.princeton.edu/~rs/talks/ScienceCS10.pdf) by sedgewick. it is slightly controversial whether theoretical CS includes empirical/ experimental aspects. see eg [theory without experiments: have we gone to far?](http://cacm.acm.org/magazines/2015/9/191184-theory-without-experiments/fulltext) by Mitzenmacher / CACM.
vzn
<ds.algorithms><reference-request><research-practice><experimental>
How to evaluate and compare the performance of algorithms in practice?
user571376
# How to evaluate and compare the performance of algorithms in practice?

(Asked by: username_0 on 2015-11-27)

Let $A$ be a heuristic algorithm for problem $Q$.
I want to evaluate the performance of my algorithm in a
specific practical environment and
compare it to other algorithms.
Is there a rigorous framework for comparison of algorithms in practice?

One method to evaluate the performance and compare it with other algorithms
is to run them on randomly generated inputs from a distribution
(based on actual inputs or a theoretical model of inputs) and
measure the average running time of the algorithms.
However I want to be able to express that one algorithm is better than other one
in stronger sense than just having better expected running time.

What do people use for to express stronger conditions?
Would standard deviation be a useful for this purpose?
What is the best way to measure the confidence level of the performance?

Are the any references (books/surveys/tutorials/...) on how to compare the performance of algorithms in practice?

**Tags:** ds.algorithms, reference-request, research-practice, experimental

> **Comments:**
> **username_1**: Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see [help center](http://cstheory.stackexchange.com/help/on-topic). Your question might be suitable for [Computer Science](http://cs.stackexchange.com/) which has a broader scope. If you post your question there, make sure to follow the cross-posting guidelines of both sites.  
> **username_2**: @username_1, I think this is a good and on-topic question. There are many problems that we only have heuristics (or heuristics perform better than non-heuristic algorithms or algorithms with worst theoretical analysis perform better than those with better theoretical analysis).  
> **username_1**: Yes and no. The edited question is a well-known question in heuristics research AFAIK, but on the other hand it is too broad (essentially it is the starting point for a large body of research). But imho the edit is far in meaning and intent from the original question which while had the merit to be narrow, was simply asking on how to measure the expected running time of a scheduling algorithm on random inputs, which is a standard topic.  
> **username_3**: try [putting the science back in CS](http://www.cs.princeton.edu/~rs/talks/ScienceCS10.pdf) by sedgewick. it is slightly controversial whether theoretical CS includes empirical/ experimental aspects. see eg [theory without experiments: have we gone to far?](http://cacm.acm.org/magazines/2015/9/191184-theory-without-experiments/fulltext) by Mitzenmacher / CACM.  

---

## 1 answers

### Answer by username_4 on 2015-11-28. Score: 6 | Accepted answer

I believe what you're looking for is the field of Experimental Algorithmics. There is a [text by McGeoch](http://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/guide-experimental-algorithmics), an [ACM Journal](http://www.jea.acm.org/), and a [previous question](https://cstheory.stackexchange.com/questions/822/a-reading-list-on-experimental-algorithmics) on this site that provides a reading list for the field.

> **Comments:**
> **username_0**: In my case, the input is a directed acyclic graph. In that case, if I generate random graphs, the output may not necessarily generate normal distribution. Am I right in this case?  
> **username_4**: I can't really speak to your situation, just the fact that a whole area of research exists to address the performance of algorithms in practice. You packed 4 questions into your one question, and I was just addressing the general reference request part.  

---

