CODEWITHSUNDEEP
c++vector
ctenochaetus
ctenochaetus

Reputation: 201

Skipping vector iterations based on index equality

Let's say I have three vectors.

#include <vector>
vector<long> Alpha;
vector<long> Beta;
vector<long> Gamma;

And let's assume I've filled them up with numbers, and that we know they're all the same length. (and we know that length ahead of time - let's say it's 3.)

What I want to have at the end is the minimum of all sums Alpha[i] + Beta[j] + Gamma[k] such that i, j, and k are all unequal to each other.

The naive approach would look something like this:

#include <climits>

long min = LONG_MAX;

for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        for (int k=0; k < 3; k++) {

            if (i != j && i != k && j != k) {
                long sum = Alpha[i] + Beta[j] + Gamma[k];
                if (sum < min)
                     min = sum;
            }
        }
    }
}

Frankly, that code doesn't feel right. Is there a faster and/or more elegant way - one that skips the redundant iterations?

Upvotes: 1

Views: 67

Answers (2)

Vincent Saulue-Laborde
Vincent Saulue-Laborde

Reputation: 1457

If you can temporarily modify the input vectors, you can swap the used values with the end of the vectors, and just iterate over the start of the vectors:

for (int i = 0; i < size; i++) {
    std::swap(Beta[i],Beta[size-1]);     // swap the used index with the last index
    std::swap(Gamma[i],Gamma[size-1]);
    for (int j = 0; j < size-1; j++) {     // don't try the last index
        std::swap(Gamma[j],Gamma[size-2]); // swap j with the 2nd-to-last index
        for (int k=0; k < size-2; k++) {   // don't try the 2 last indices
            long sum = Alpha[i] + Beta[j] + Gamma[k];
            if (sum < min) {
                min = sum;
            }
        }
        std::swap(Gamma[j],Gamma[size-2]); // restore values
    }
    std::swap(Beta[i],Beta[size-1]);       // restore values
    std::swap(Gamma[i],Gamma[size-1]);
}

Upvotes: 1

R Sahu
R Sahu

Reputation: 206697

The computational complexity of your algorithm is an O(N^3). You can save a very small bit by using:

for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        if ( i == j )
           continue;

        long sum1 = Alpha[i] + Beta[j];
        for (int k=0; k < 3; k++) {    
            if (i != k && j != k) {
                long sum2 = sum1 + Gamma[k];
                if (sum2 < min)
                     min = sum2;
            }
        }
    }
}

However, the complexity of the algorithm is still O(N^3).

Without the if ( i == j ) check, the innermost loop will be executed N^2 times. With that check, you will be able to avoid the innermost loop N times. It will be executed N(N-1) times. The check is almost not worth it .

Upvotes: 2

Related Questions