這段代碼爲什麼更快？

Question

這個問題讓我瘋狂。頂部的代碼在我的電腦上執行大約0.3秒，而底部的代碼在大約2.7秒內執行。但是，我試圖將第二個代碼調整爲與第一個代碼類似，但它似乎總是比較慢。誰能告訴我爲什麼第一個代碼比第二個執行速度快得多？

更快的代碼

#include <cstdio> 
#include <set> 
#define ls(x) (x & (-x)) 
using namespace std; 
int tc, n; 
set<long long> s; 
long long p, a[35]; 
int main() { 
    freopen("mini3b.in","r",stdin); 
    scanf("%d", &tc); 
    while (tc--) { 
     s.clear(); 
     scanf("%lld%d", &p, &n); 
     for (int i = 0; i < n; ++i) scanf("%lld", &a[i]); 
     int h = n/2; 
     for (int i = 0; i < (1<<h); ++i) { 
      long long sum = 0; 
      for (int j = 0; j < h; ++j) if (i&(1<<j)) sum += a[j]; 
      s.insert(sum); 
     } 
     bool found = false; 
     for (int i = 0; (i < (1<<(n-h))) && !found; ++i) { 
      long long sum = 0; 
      for (int j = 0; j < n-h; ++j) if (i&(1<<j)) sum += a[h+j]; 
      if (s.find(p-sum) != s.end()) found = true; 
     } 
     printf(found? "YES\n":"NO\n"); 
    } 
} 

慢的代碼

#include <cstdio> 
#include <set> 
using namespace std; 
long long n, bars[35]; 
int t, p; 
set<long long> s; 
int main(){ 
    freopen("mini3b.in","r", stdin); 
    scanf("%d", &t); 
    while (t--){ 
     s.clear(); 
     scanf("%lld%d", &n, &p); 
     for (int i=0;i<p;++i) scanf("%lld", &bars[i]); 
     int limit=p/2; 
     for (int i=0;i<(1<<limit);++i){ 
      long long sum=0; 
      for (int j=0;j<limit;++j) if (i&(1<<j)) sum+=bars[j]; 
      s.insert(sum); 
     } 
     bool found=false; 
     for (int i=0;i<(1<<(n-limit))&&!found;++i){ 
      long long sum=0; 
      for (int j=0;j<p-limit;++j) if (i&(1<<j)) sum+=bars[limit+j]; 
      if (s.find(n-sum) != s.end()) 
       found=true; 
     } 
     printf(found?"YES\n":"NO\n"); 
    } 
} 

Answer 1

在for循環中你有

for (int i = 0; (i < (1<<(n-h))) && !found; ++i) { // fast one 
         ^

對

第四

for (int i=0;i<(1<<(n-limit))&&!found;++i){ // slow one 
        ^

請注意，快速代碼中的'n'是慢速代碼中的'p'。所以你應該有

for (int i=0;i<(1<<(p-limit))&&!found;++i){ // slow one 
        ^