CODEWITHSUNDEEP
c++optimization
ExonegeS
ExonegeS

Reputation: 3

Optimization. How to speed up the given C ++ code?

This is my code. 1<=i<=j<=n j-i<=a 1<=n<=1000000 0<=a<=1000000

#include <iostream>
using namespace std;
int main(){
    int n, a, r = 0;
    cin>>n>>a;
    for(int i = 1; i <= n; i++){
        int j = i;
        for(j; j <= n; j++){
            if(j-i<=a){
                r++;
            }
        }
    }
    cout<<r;
}

Instead of loops, I changed it to a simple check of variables, which greatly accelerated the code. there is no need to calculate thousands of options. My final, optimized code is:

 #include <iostream>
using namespace std;
int main(){
    unsigned long long n, a, r = 0;
    cin>>n>>a;
    if(a==0){
        r = n;
    }
    if(n<=a){
        r = (n*(n+1))/2;    
    }
    if(n>a){
        r += (n-a)*(a+1) + (a*(a+1))/2;
    }
    cout<<r;
}

Upvotes: 0

Views: 170

Answers (4)

selbie
selbie

Reputation: 104474

After accounting for both positive numbers, negative numbers, and zeros, your double-nested for-loop can be simplified into this:

if (n < 1)
{
    r = 0;
}
else if (a == 0)
{
    r = n;
}
else if (a < 0)
{
    r = 0;
}
else if (n <= a)
{
    r = (n * (n + 1)) / 2;
}
else
{
    r = (n-a)*(a + 1) + (a * (a + 1)) / 2;
}

Recall that summing a sequence of digits from 1..N is:

 N*(N+1)
 -------
    2

If n <= a (positive numbers), r is incremented n times in the inner loop on the first iteration of the outer loop. Then n-1 times, then n-2 times... all the way down to 1.

For cases where n > a, then there are n-a summations of a+1 followed by a decrementing summation from a down to 1

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490048

This strikes me as something to speed up by doing a bit of math, not by massaging the code.

Basically, we can think of the loops as defining a square matrix of the values of i and j. So let's assume n = 9, and a = 3. I'll draw in a + for each place we increment r, a blank for the values we don't generate, and a 0 for the places we generate values, but don't increment r.

i\j 1 2 3 4 5 6 7 8 9
1   + + + + 0 0 0 0 0 
2     + + + + 0 0 0 0 
3       + + + + 0 0 0 
4         + + + + 0 0 
5           + + + + 0 
6             + + + +
7               + + +
8                 + + 
9                   +

So, ignoring the last a rows (i.e., for the first n-a rows), in each row we have a band a + 1 elements wide where we do an increment. Then at the end, we have a triangle, where we're basically summing a + a-1 + a-2 ... 0.

So, the first piece is (a+1) * (n-a) and the second piece is a * (a+1) / 2. Add those together, and we get the final answer.

Upvotes: 1

Jim Pp
Jim Pp

Reputation: 157

If you want to speed up your code, instead of just tuning your algorithm, you can also try to use some parallel api.

Parallel computing api such as OpenMP enables you take advantage of your cpu resources.

If you uses OpenMP, you can try to use it to parallel your loop.

Upvotes: 0

Rick James
Rick James

Reputation: 142208

Seems like

    for(j; j <= n; j++){
        if(j-i<=a){
            r++;
        }
    }

could be replaced by

   r += f(i,n,a);

Where f() is some simple expression involving those 3 values, probably including the equivalent of min(..,..)

Upvotes: 0

Related Questions