優化C++代碼

-2

我正在嘗試在線裁判的經典子集總和問題。然而，這次的差別是，n < = 30，所以最大操作可以達到30 * 2^30。我已經在下面有一些工作代碼。但是，程序的時間限制是1秒，我的程序在0.5到1.1秒之間徘徊。這導致了TLE，儘管我試圖儘可能地加快我的代碼速度。你們有沒有關於我如何能夠進一步加快和優化我的代碼的提示？提前致謝。優化C++代碼

#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; 
    } 
}

來源

2013-02-18 cortex

您應該在http://codereview.stackexchange.com/上發佈此問題。 – 2013-02-18 09:00:17

人，指數函數可以大大提高。在這裏尋找更多的信息：http://eli.thegreenplace.net/2009/03/21/efficient-integer-exponentiation-algorithms/ – AraK 2013-02-18 09:01:14

書寫醜陋的代碼不會使其更快，你的陳述劃分到不同的線路，即與

{ 
    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)）。

編輯因爲這已被接受，我會從其他的答案/意見收集起來次要問題：

由於稔指出，tmpsum>=n檢查並不需要做的每一個迴路因爲在循環期間n和tmpsum都沒有改變。
由於Karthik T指出，行if (tmpsum<n)found=false;是多餘的，found在這一點上永遠不可能是false。

來源

2013-02-18 09:00:39

還有一件事要補充，在該循環中檢查'tmpsum> = n'是多餘的，在循環中看起來都沒有被觸及，只要重寫if條件即可繞過循環.. – Nim 2013-02-18 09:26:20

也可以使用'std ::來自''的pow'而不是手滾動，編譯器可以優化兩個冪的更好... – Nim 2013-02-18 09:28:52

移動power(2,p)外循環。

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

來源

2013-02-18 08:57:48

移位會更快恕我直言。 – 2013-02-18 08:59:04

@IvayloStrandjev都應該發生我期望的最佳結果。 – 2013-02-18 09:00:53

使用位移來計算兩個度數。

來源

2013-02-18 08:58:39

if (tmpsum<n)found=false;

此行實現了什麼，found已經false。

1<<j

正在計算兩次，可以通過存儲結果減少到一次。

來源

2013-02-18 09:00:01

編譯器不可能不會緩存1 << j。 – 2013-02-18 09:06:19

對於初學者可以移動power(2,p)出的for循環

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

來源

2013-02-18 09:01:11 Thomas

-1

功率（2，p）爲等於1個< < p
定義之和SUM2作爲寄存器變量。

寄存器無符號和sum2;

來源

2013-02-18 09:01:52

註冊是非常非常不可能使_any_差異。 – 2013-02-18 09:04:04

除非這是Turbo C++或其他20年前的編譯器，否則使用register函數幾乎不會產生任何影響 - 如果它有任何影響，那麼它很可能是有害的，因爲它是好的。現代編譯器，比如（至少）2.95 [最新發布的版本是4.8左右]的gcc將使用寄存器，無論你是否要求它都可以。 – 2013-02-18 09:04:14

除了別人所說的，Avoid Branching。例如：

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

可以寫成

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

誠然，這讓已經難以閱讀的代碼更難閱讀。

來源

2013-02-18 09:30:15 Sebastian

回答

相關問題