mercredi 6 mai 2015

Overcoming an n^2 runtime program

Is there a way to overcome a nested loop recursion in C++11? My program has a slow runtime. Or rather, is there a more efficient way to solve for the following formula z=|a-b|*|x-y|,with a, b, x and y being elements in a 10000 integer array?

Here is the code:

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream in("int.in");

int main()
{
    long long n, n1, z, x, y, in2=0;
    in>>n;
    long long l[n], p[n];
    for(x=0;x!=n;x++)
        in>>l[x]>>p[x];
    for(x=0;x!=n;x++)
    {
        for(y=x+1;y<n;y++)
        {
            n1=l[x]-l[y];
            if(n1<0)
                n1*=-1;
            z=p[x]-p[y];
            if(z<0)
                z*=-1;
            in2+=n1*z;
        }
    }
    cout<<in2<<"\n";
}

I tried to change the data types to short int, long, long long and unsigned, but it either dumps garbage values or executes ``Segmentation Core Fault` errors.

I've also tried to optimize the abs solution with the abs() function (ineq+=(abs(l[x]-l[y]*abs(p[x]-p[y])));, but it seems to execute slower. I do not know of any other optimizations I can implement, so please do recommend.

Linux-friendly solution preferred. Thank you.

Side Note: the values of a, b, x and y are all within the range 1<=a,b,x,y<=10000.

Aucun commentaire:

Enregistrer un commentaire