id	summary	reporter	owner	description	type	status	priority	milestone	component	version	severity	resolution	keywords	cc
336	p_psVectorSmoothHistGaussian missing obvious optimisation	Paul Price	gusciora@…	"Given a histogram with bounds x, and values in the bins between the bounds, y,
p_psVectorSmoothHistGaussian uses a binary search on x to find the range for
smoothing (x_i + 5 sigma and x_i - 5 sigma).  This neglects an obvious
optimisation: if psHistogram.uniform is true (as is often the case), then the
bins are uniformly distributed (i.e., they have equal spacing).  This property
means that finding a bin index is a matter of linear interpolation: to find
value, use
    dxInverse = (float)N / (x[N-1] - x[0])
    index = (value - x[0]) * dxInverse
dxInverse could be carried in the psHistogram structure if it's useful.

Even in the event that psHistogram.uniform is false (and even if it is true), a
better algorithm than identifying the maximum and minimum bin and then summing
the values within these bins would be to simply move from the central bin (which
is known) up until we fall outside the limit, summing the bins as we go, and
then repeat on the low side.  This is more efficient because we're going to sum
these bins anyway.

An even better optimisation would take advantage of the symmetrical property of
the Gaussian, like this:

// Initialise the bins to their own current values
float weightAtZero = gaussian(0.0, sigma); // To make sure the normalisation is
right
for (int i = 0; i < num; i++) {
    weights[i] = weightAtZero;
    smoothed[i] = y[i] * weightAtZero;
}
// Work through the histogram
for (int i = 0; i < num; i++) {
    weights[i] = 0.0;
    smoothed[i] = y[i];
    float distance = 0.0;
    // Go out until we fall off the 5 sigma limit
    for (int j = i + 1; j < num && (distance = midPoint[j] - midPoint[i]) < 5 *
sigma; j++) {
        // Because the Gaussian is symmetrical, we can take care of both the
positive and negative side at the same time
        weight = gaussian(distance, sigma);
        smoothed[i] += y[j] * weight;
        weights[i] += weight;
        smoothed[j] += y[i] * weight;
        weights[j] += weight;
    }
}
// Normalise by the weights
for (int i = 0; i < num; i++) {
    smoothed[i] /= weights[i];
}"	defect	closed	high		types	unspecified	normal	fixed