有人可以告诉我任何不同的方法来使这段代码更快吗？

Question

代码运行正确，它做了它应该做的事情，但我被告知我可以通过使用布尔表达式来加快它的速度，但我真的不知道在哪里插入它们。问题是：

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

有人可以建议我任何使代码更高效的技术吗？

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;

}

Answer 1

首先，您不必要地调用了 remote 两次（在某些情况下）。考虑使用这个：

#include <algorithm>

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

这也会缩短和阐明代码。

此外，除法可能很慢。尝试（分析后！）替换

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

来自

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

注意 @Donnie & others 在评论中声称编译器将进行后者优化，他们可能是正确的。

Answer 2

我想给你看看我机器上的时间：

版本 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);
        }               
    }
}

版本 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);
        }               
    }
 */
}

对于 n=10^5，使用 -O3 编译都产生 60 毫秒。未经优化编译：均为 60ms。

优化的第一步是了解您的程序将时间花在哪里。 Reading/parsing数据是瓶颈。

您可以通过将第一行添加到 main 中来加快速度：

ios_base::sync_with_stdio(false);

在我的机器上我减少到 20 毫秒。

Answer 3

1) 给remote函数赋一个临时值：

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

2) 用remote的内容替换对remote的调用，去除函数调用的开销：

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

3) 用常量临时变量替换a / 2：

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

4) 将编译器优化级别更改为高 - 以提高速度。

5) 瓶颈现在在输入语句中。通过优化循环的剩余部分获得的任何收益都被输入时间浪费了。没有更多 Return On Investment 需要进一步更改。

有人可以告诉我任何不同的方法来使这段代码更快吗？

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

c++

algorithm

optimization

min