優化標準迭代算法

在談到這個問題的挑戰在這裏： Link 優化標準迭代算法

#include <iostream> 

using namespace std; 


int main() { 
    int T,*x,i,j,k,a,res,pres; 
    long Q,N,p,q; 
    cin>>T; 
    for(k=0;k<T;k++) 
    { 
     cin>>N>>Q; 
     x=new int[N]; 
     for(i=0;i<N;i++) 
     { 
      cin>>x[i]; 
     } 
     for(i=0;i<Q;i++) 
     { 
      pres=-999; 
      cin>>a>>p>>q; 
      for(j=p-1;j<q;j++) 
      { 
       res=a xor x[j]; 
       if(pres<res) 
       { 
        pres=res; 
       } 
      } 
      cout<<pres<<endl; 

     } 
     delete [] x; 
    } 
    return 0; 
}

我得到的時間超出限制的更大的問題（這意味着問題可以被優化）（N = 100000）（N ，Q，T超出）。我想我需要使用某種預處理來優化算法。我的解決方案是針對整個問題的O（NQT）。該問題需要針對查詢中給定限制的所有可能XOR進行評估。所以，該問題需要去（q-p）[可以在最大N]次查詢。我無法想出一個辦法來避免這種情況。一個命中或方向將非常感激。我正在考慮以某種方式實現一個堆，以便它從堆中扣除查詢a，並註冊一個最大堆以查看最大差異和數據庫xors。但是，這也將採取O（NQT）

來源

2013-12-21 Shaurya Chaudhuri

爲什麼你的循環從1開始？爲什麼你不分配分配？爲什麼你要遠離使用點聲明變量？你爲什麼使用名字空間std;'？首先清理代碼，並獲得巨大的不變因素。 – Yakk

清理Itsy Bitsy的東西。我的主要代碼全部清理完畢。在我清理不必要的東西之前，這已經是相當原始的了。從1開始，因爲最初並沒有得到結果，只是爲了確保1到N的所有東西，所以dat按照我認爲的算法進行。 –

可能更適合codereview.stackexchange.com –

一些提示：

所有調用cin使其無法衡量該代碼的性能。您應該事先從文件中讀取所有數據。
每次看都不分配x，用malloc分配一次，如果需要的話調用realloc使緩衝區變長。內存分配可能會減慢速度。

內循環非常簡單，所以編譯器可以對其進行矢量化。通過查看反彙編來確保實際發生這種情況。如果不是，則使用SSE內在函數一次處理4個或8個8個元素。

來源

2013-12-21 10:06:32 egur

下面是修改過的代碼和我在評論中提出的建議。

避免在性能敏感的代碼中使用C++ iostream。（FWIW，一般避免iostreams）儘可能避免分配/釋放。在下面的代碼中，vector::resize將照顧矢量總是至少有所需的空間。不表現，但可讀性明智：使用空格aronud操作符。聲明變量關閉到他們使用的地方。

#include <cstdio> 
#include <vector> 
#include <algorithm> 

int main() { 
    int T; 
    std::vector<int> x; 

    std::scanf ("%d", &T); 
    for (int k = 0; k < T ; ++k) { 

     int N, Q; 
     std::scanf ("%d%d", &N, &Q); 
     x.resize (N); 

     for (int i = 0; i < N; ++i) 
      std::scanf ("%d", &x[i]); 

     for (int i = 0; i < Q; ++i) { 
      int a, p, q; 
      std::scanf ("%d%d%d", &a, &p, &q); 

      int pres = -999; 
      for(int j = p - 1; j < q; ++j) 
       pres = std::max (pres, a^x[j]); 

      std::printf ("%d\n", pres); 
     } 
    } 
    return 0; 
}

來源

2013-12-21 10:18:49 chill

我不認爲擺弄你寫的東西會讓你在速度上有很大的提高。你想要更好的時間複雜性。

從這個問題中，我假設他們想要每個查詢都是O（log N）。我最初的想法是segment tree，但我找不到一種方法來使用它們來最大化a^x[i]。

我相信你應該使用這樣一個事實，即所有的數字都小於2^15。另外需要注意的是，您想要最大化xor操作。比方說，你有（二進制）

a = b_1 b_2 ... b_n

你要麼擁有所有x[j]與p <= j <= q有最顯著位等於b_1，還是有一些x[j]對於其中最顯著位的b_1的補充。這是因爲b xor ~b = 1爲b in {0,1}。您只選擇其中MSB是b_1的補充的那些j，並繼續下一位（對應於b_2）。

問題是，這種蠻力實施比你已經做的更糟糕，但它可能會幫助你實現更快的實施。

來源

2013-12-21 10:45:52 sebii

只有在x [j]的MSB是a的補數的數字上進行XOR操作纔會減少no。 XOR操作。但它不會增加N個比較來決定其中哪個具有補充的MSB？不會讓時間複雜度與之相同嗎？ –

是的，這是我的方法崩潰的地步。我不知道如何完全解決你的問題，但我認爲這與所有相對較小的數字有關（小於2^15）。如果我想到更好的東西，我會編輯我的答案。 – sebii

優化標準迭代算法

回答

相關問題