Comparing effect of optimization on multiple runs with one variable I have a problem with one variable (rounds) that affects the time it takes a program to solve it. For a given number of rounds I generate multiple independent instances and measure the time it takes to solve them.
I then repeat this (with the same instances) with an modified (optimized) version of the solving algorithm. I want to see if the modification leads to faster solving times or not.
I am sure there is proper statistic test for this kind of experiment, however I was unable to find it. Could you point me in the right direction?
Also, to visualize the difference I used two violin plots. The first one shows the distribution of running times for instances of given size side by side (left/yellow is original, right/green is optimized). The second shows the distribution of pairwise differences in time.


 A: I don't know a frequentist test for your problem (a one-sided Wilcoxon signed-rank test or sign test won't work because the differences are not identically distributed). But perhaps your problem could be solved easily using a Bayesian approach. For example:
Let $d_i = 1(x_i < y_i)$, which is 1 if the runtime of the modified optimization, $x_i$, was smaller than the runtime of the unmodified optimization, $y_i$, and 0 otherwise.
Let's say $\pi$ is the (unknown) probability that $x < y$. If our prior beliefs over $\pi$ are uniform, $p(\pi) = 1$, then
\begin{align}
p(\pi \mid \mathcal{D}) &\propto p(\mathcal{D} \mid \pi) p(\pi)
=\prod_i \pi^{d_i} (1 - \pi)^{1 - d_i} 
\propto \text{Beta}\left(\pi; 1 + \sum_i d_i, 1 + N - \sum_i d_i \right),
\end{align}
where $\mathcal{D} = \{d_1, ..., d_N\}$. I.e., our posterior beliefs over $\pi$ are beta distributed. From this we can easily derive the probability that the modified optimization tends to be faster, $P(\pi > .5 \mid \mathcal{D})$.
If instead of using a uniform prior we want to make the reasonable assumption that $\pi$ is more likely to be around .5 then one of the extreme values, we could use a beta prior with parameters $\alpha = \beta$, $\alpha > 1$ and get 
$$p(\pi \mid \mathcal{D}) = \text{Beta}\left(\pi; \alpha + \sum_i d_i, \beta + N - \sum_i d_i \right).$$
In Python code:

import numpy as np
import scipy as sp

# prior
alpha = beta = 2

# data
x = np.asarray([1, 4, 5, 7, 10, 11])
y = np.asarray([3, 4, 6, 8,  9, 12])

# statistic
d = np.asarray(x < y, int)
N = d.size
T = np.sum(d)

# posterior probability that x < y
p = 1. - sp.stats.beta.cdf(.5, alpha + T, beta + N - T)

