c++ - 优化 C++ 代码

Question

我正在在线法官上尝试经典的子集和问题。但是，这次的不同之处在于 n<=30，因此最大操作数可以达到 30*2^30。我已经在下面有一些工作代码。但是，程序的时间限制是 1 秒，我的程序在 0.5 到 1.1 秒之间徘徊。尽管我已尽我所能加快我的代码速度，但这会导致 TLE。你们对我如何能够进一步加快和优化我的代码有什么建议吗？提前致谢。

#include <iostream>
#include <cstdio>
using namespace std;

unsigned power(unsigned x, unsigned y){        //pow function
    unsigned sum=x;
    for (int i=1;i<=y-1;i++)
        sum*=x;
    return sum;
}

int main(){
    unsigned t, n, p, sum, sum2, tmpsum=0;
    unsigned bars[32];
    bool found;
    scanf("%u", &t);
    while (t--){
        tmpsum=0;
        found=false;
        scanf("%u %u", &n, &p);
        for (int i=0;i<p;i++){
            scanf("%u",&bars[i]);
            tmpsum+=bars[i];
        }
        if (tmpsum<n)found=false;
        unsigned end=power(2,p)-1;          //counting from the end and from the start
        for (unsigned i=0;i<power(2,p)&&tmpsum>=n;i++){       //counting from 1 to 2^n in binary
            sum=0;
            sum2=0;
            for (unsigned j=0;j<p;j++){
                if (i&(1<<j))
                    sum+=bars[j];
                if (end&(1<<j))     //counting from the end and start at the same time
                    {sum2+=bars[j];end--;}
            }
            if (sum==n||sum2==n)
                {found=true;break;}
        }
        cout<<(found==true?"YES":"NO")<<endl;
    }
}

score 3 · Accepted Answer

移出power(2,p)循环。

for (unsigned i=0;i<power(2,p)&&tmpsum>=n;i++)
                      ^^^^

score 3 · Accepted Answer

3

使用位移来计算 2 的度数。

于 2013-02-18T08:58:39.610 回答

score 2 · Accepted Answer

编写丑陋的代码并不能使它更快，将您的语句分成不同的行，即替换{sum2+=bars[j];end--;}为

{
    sum2 += bars[j];
    --end;
}

关于问题：您的主要时间损失可能在这里：

for (unsigned i=0;i<power(2,p)&&tmpsum>=n;i++){

除非你有一个特别好的编译器，否则power(2, p)每个循环都会计算一次，这是完全不需要的。预先计算它。

int pow2p = power(2, p);
for (unsigned i=0;i<pow2p&&tmpsum>=n;i++){

此外，以这种方式执行 2 的幂非常慢，因此请<<改用 ( 1<<p == power(2, p))。

编辑由于这已被接受，我将从其他答案/评论中收集小点：

正如 Nim 指出的那样，tmpsum>=n检查不需要在每个循环中都进行，因为在循环期间既不改变n也不tmpsum改变。
正如 Karthik T 指出的那样，这条线if (tmpsum<n)found=false;是多余的，found只能false在这一点上。

score 1 · Accepted Answer

除了其他人所说的，避免分支。例如：

if (i&(1<<j))
    sum+=bars[j];

可以写成

sum+=bars[j] * ((i&(1<<j))>>j);

诚然，它使已经很难阅读的代码变得更难阅读。

score 0 · Accepted Answer

if (tmpsum<n)found=false;

这条线一事无成，found已经是false。

1<<j

正在计算两次，通过存储结果可以减少到一次。

score 0 · Accepted Answer

对于初学者，您可以移出power(2,p)for 循环

for (unsigned i=0, end=power(2,p); i<end && tmpsum>=n; i++)

score -1 · Accepted Answer

幂（2，p）等于 1 << p
将 sum 和 sum2 定义为寄存器变量。

注册无符号和，sum2；

c++ - 优化 C++ 代码

7 回答 7

Related

Reference