CODEWITHSUNDEEP
c++algorithmoptimizationmin
23ElCaliente
23ElCaliente

Reputation: 33

Could someone tell me any different way to make this code faster?

The code runs correctly and it does what it is supposed to do, but I was told I could make it faster by using Boolean expressions instead but would not really know where to insert them here. The problem is:

Given a sequence of n points with their coordinates, write a program remote, which calculates the value of the smallest remoteness of a point, which is outside the square. A point is outside the square, if it is neither inner to the square, nor belongs to square contour. If there are no points outside the square, your program has to output 0.

Constraints:
1 ≤ n ≤ 10000 and 1 ≤ a ≤ 1000 ;
Example:

Input: 5 4
1 2
4 6
-3 2
-2 2
4 -1
Output: 5

Could someone suggest me any technique to make the code more efficient?

int remote(int x, int y) {
    int z = abs(x) + abs(y);
    return z;
}   

int main() {

    int n, a;
    int x;
    int y;

    cin >> n >> a;

    int z=20001;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        if (x > a / 2 || y > a / 2) {
            if (z > remote(x, y)) {
                z = remote(x, y);
            }               
        }
    }    
    cout << z <<endl;

    return 0;

}

Upvotes: 0

Views: 108

Answers (3)

Thomas Matthews
Thomas Matthews

Reputation: 57678

1) Assign a temporary value to the remote function: 

if (x > a / 2 || y > a / 2)
{
    const int r = remote(x,y);
    if (z > r)
    {
        z = r;
    }
}

2) Replace the call to remote with the contents of remote, removing the overhead of a function call: 

if (x > a / 2 || y > a / 2)
{
    const int r = abs(x) + abs(y);
    if (z > r)
    {
        z = r;
    }
}

3) Replace a / 2 with a constant temporary variable: 

const int midpoint = a >> 1;
if (x > midpoint || y > midpoint)

4) Change compiler optimization level to high - for speed.

5) The bottleneck is now in the input statement. Any gain by optimizing the remainder of the loop is wasted by the Input time. There is no more Return On Investment for further changes.

Upvotes: 0

ead
ead

Reputation: 34316

I would like to show you the timings on my machine:

Version 1:

for (int i = 1; i <= n; i++) {
    cin >> x >> y;
   if (x > a / 2 || y > a / 2) {
        if (z > remote(x, y)) {
            z = remote(x, y);
        }               
    }
}

Version 2:

for (int i = 1; i <= n; i++) {
    cin >> x >> y;
/*    if (x > a / 2 || y > a / 2) {
        if (z > remote(x, y)) {
            z = remote(x, y);
        }               
    }
 */
}

For n=10^5, compiled with -O3 both yield 60ms. Compiled without optimization: both 60ms.

First step for optimizing is to know where your program spends time. Reading/parsing the data is the bottle neck.

You could speed up it a little bit by adding as first line to your main:

ios_base::sync_with_stdio(false);

On my machine I'm down to 20ms.

Upvotes: 1

Ami Tavory
Ami Tavory

Reputation: 76297

For one, you are calling remote twice (in some cases) needlessly. Consider using this:

#include <algorithm>

z = std::max(z, remote(x, y));

This will also shorten and clarify the code.

Also, it's possible the divisions are slow. Try (after profiling!) replacing

x > a / 2 || y > a / 2

by

(x << 1) > a || (y << 1) > a

Note @Donnie & others claims in the comments that compilers will do the latter optimization, and they are probably correct.

Upvotes: 1

Related Questions