I am working on a project where the hotspot is some code that is supposed to find an offset, such that the squared differences between a reference vector and a given vector becomes minimal. The core function is this:
#include <vector>
#include <map>
typedef std::vector<double> vect_d
double sqDiffSum(const vect_d& ref, const vect_d& x,int offset){
size_t scale = ref.size() / x.size(); // ref.size() is always n*x.size()
double sum = 0;
int counter = 0;
for (size_t i=0;i<x.size();i++){
for (size_t j=0;j<scale;j++){
int bin = i*scale + j - offset;
if (bin >= 0 && bin < (int)ref.size()){
double diff = ref[bin] - x[i];
sum += diff * diff;
counter++;
}
}
}
return sum / counter;
}
This is called from some minimization routine, that (for now) I dont want to change. It varies the offset
to get the minimum sqDiffSum
. I know that I could probably do the task faster by using a FFT, but for now I want to see how much I can get out of the current approach. I could already make it faster (roughly x2.5) by adding some memoization:
double callSqDiffSum(const vect_d& ref, const vect_d& x,int offset,bool firstCall){
static std::map<int,double> memo;
if (firstCall){ memo.clear(); }
else {
std::map<int,double>::iterator found = memo.find(offset);
if (found != memo.end()){
return found->second;
}
}
double result = sqDiffSum(ref,x,offset);
memo[offset] = result;
return result;
}
However, it is still too slow. There are several points that in principle I could optimize, but for each I have my doubts whether it will bring any benefit:
The reference vector
ref
is actually always the same, thus I could avoid passing it around at all.The size of the vectors is always the same, so actually there is no need for
std::vector
, but if possible I would like to avoid c-style arrays and I dont expect too much improvement by not using vectors here.The innermost loop has some branching, that could be avoided
Is there anything that comes to your mind to make this more efficient? Is my assumption that the above points are not really worth to change wrong?
Please note that this is pre-C++11.
f(x)
is your first vector andg(x)
is your second vector, you want to get the minimum value ofh(x) = (f(x)-g(x))^2)
. I'm not sure, but maybe you can get away with just calculating the derivativeh'(x)
. That would go from O(n^2) to O(1). \$\endgroup\$ – ChatterOne Jul 22 '16 at 21:03