fastest way to get the maximal difference between 2 vectors

1
votes

I would like to get ideas for finding a fast way to get the maximal difference between 2 vectors as if they're accumulated .

For example, (not accumulated yet)

vector<int> vec1 = {10, 30, 20, 40 };
vector<int> vec2 = {5, 10, 5, 8 };

the naive way to get the result, is to accumulate them first into new vectors so:

vector<int> accumulated_vec1 = {10, 10+30, 10+30+20, 10+30+20+40};
vector<int> accumulated_vec2 = {5, 5+10, 5+10+5, 5+10+5+8};

i.e:

accumulated_vec1 = {10,40,60,100};
accumulated_vec2 = {5,15,20,28};

Then, the result is the max between abs(accumulated_vec1[i]-accumulated_vec2[i]) while 0 <= i <= 3.

so result = 72 (when i==3)

a faster way can be by representing the vectors by 1 number(even 0.10302040)... but I can't find it helpful :\ Think that I have millions pairs of the 2 vectors vec1 and vec2, and I am trying to avoid calculating the accumulated vectors for each of pair.. sorry if it's not clear but if I find a solution, I'll answer this annoying question.

3
c++vectorstl
This seems very simple to do... (you can compute accumulation on the fly, without need to store it in another vector). What is the problems you are having? – 6502
sorry, forgot to say that I need the accumulated vectors for other calculations in other functions. I'm just trying to think about holding them in other structures than vector.. maybe, other way such as hexa \ number(somehow).. Just think that I have millions of pairs like these ones – Maor Cohen
Your code is pretty fast already, but make sure you call .reserve() on your accumulated vectors to avoid reallocating while you're pushing things back into it (I'm assuming you're filling it inside a loop in your actual code). If you do have a lot of elements like you just said, this would be a good optimization to your code. – notadam
I have no idea what your question is actually. Is it how to get running partial sums into vectors? Or what? – Barry
@ErezShmiel I don't really understand your question. In the question you say "as if they were accumulated" suggesting you're looing for an alternative to avoid the accumulation and the copy to other vectors, then in your comment you say that you need the two accumulated vectors for other things. If you do need those vectors to be present for other calculations, there's really no way of avoiding the calculation of those vectors, right? If you do need that data, you can't skip that step. I'm confused about what you need exactly. – notadam

3 Answers

2
votes

Fastest way...

int maxDiff(const vector<int> &v1, const vector<int> &v2) {
    int maxDiff(0), diff(0);

    for (auto it1 = v1.begin(), it2 = v2.begin(); it1 != v1.end() && it2 != v2.end(); ++it1, ++it2) {
        diff += *it1-*it2;
        maxDiff = max(abs(diff), maxDiff);
    }

    return maxDiff;
}

No other vector construction, just moving pointers that are even faster than getting elements per their index each time.

Live Demo

0
votes

Take a look at the code below. Does this do what you are asking?

vector<int> accumulated_vec;
accumulated_vec.resize(vec1.size());
accumulated_vec[0] = vec1[0] - vec2[0];

for(int i = 1; i < accumulated_vec.size(); i++)
{
    accumulated_vec[i] = accumulated_vec[i-1] + (vec1[i] - vec2[i]);
    cout << accumulated_vec[i] << endl;
}
0
votes

Here is my version for your problem

int getAccumulatedForIndex(int index, vector<int> &vec) {
    if (index == 0) {
        return vec.at(index);
    }
    return vec.at(index) + getAccumulatedForIndex(index - 1, vec);
}

and than

int getAccumulatedMax(vector<int> vec1, vector<int> vec2) {
    if (vec1.size() != vec2.size()) { // don't much each other
        return -1;
    }

    int max = -1;
    for (int i = 0; i < vec1.size(); ++i) {
        int currentMax = abs(getAccumulatedForIndex(i, vec1) - getAccumulatedForIndex(i, vec2));
        if (currentMax > max) {
            max = currentMax;
        }
    }

    return max;
}

hope that's it what you want