爲大量迭代優化代碼

Question

我目前正在研究一個涉及大量迭代（準確地說是2^32）的項目。我主要在我的大部分計算中都使用了mathematica，但它無法處理這種數量的過程。有人建議，我認爲C++將能夠處理它，所以昨天晚上我學過C++，並寫了下面的代碼：

//old code 

的代碼運行正常，（我查了小參數），但我已經開始運行它爲4294967295 = 2^32-1步驟，我認爲這將需要數百小時。如果有人能告訴我是否有辦法優化代碼的某些部分，以便它運行得更快，我會非常感激的。我對這種語言沒有經驗，所以我如何構建這些功能可能看起來相當混亂。我認爲我的Ca2step函數運行得非常有效（我可能是錯誤的），並且我認爲它的主要部分中的循環會放慢一切。我認爲我想要完成的工作必須有更快的方法，所以任何幫助都會很棒。 謝謝， 理查德。

======= UPDATE ========

非常感謝大家，我真的很感激。好的，我對我來說都很新，所以我很難理解有些事情的意思。以下是我更新的代碼。不過，我感覺它仍然很慢。有人建議「並行」，但我不知道這是什麼，我會怎麼做？再次感謝理查德。

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 

//parameters 
int a[32] = {0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 
      1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1}; 
int b[32] = {1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 
      1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}; 
// Create vector of vectors from arrays to be input into function. 
vector<int> va (a, a + sizeof(a)/sizeof(int)); 
vector<int> vb (b, b + sizeof(b)/sizeof(int)); 

vector< vector<int> > ca2step (long int r, vector< vector<int> > vec) 
{ 
    int rulearray[32] = { 0 }; 
    for (int pos = 31; pos >= 0; --pos){ 
     if (r % 2) 
      rulearray[pos] = 1; 
     r /= 2; 
    } 
    int arraya[32] = {0}; 
    int arrayb[32] = {0}; 
    for (int i = 0; i < 32; i++) { 
     arraya[i] = vec[0][i]; 
     arrayb[i] = vec[1][i]; 
    } 

    vector< vector<int> > output; 
    typedef int t_array[32]; 
    t_array vll, vl, vr, vrr, vx; 

    rotate_copy(arrayb,arrayb+2,arrayb+32,vll); 
    rotate_copy(arrayb,arrayb+1,arrayb+32,vl);  
    rotate_copy(arrayb,arrayb+31,arrayb+32,vr);  
    rotate_copy(arrayb,arrayb+30,arrayb+32,vrr); 


    for (int i = 0; i < 32; i++) { 
     vx[i] = (arraya[i] + rulearray[(31 - (vll[i] + (2 * vl[i]) 
              + (4 * arrayb[i]) + (8 * vr[i]) + (16 * vrr[i])))]) % 2; 
    } 

    output.push_back(vector<int>(arrayb, arrayb+32)); 
    output.push_back(vector<int>(vx, vx+32)); 

    return (output); 

} 

int caevolve (long int r, vector< vector<int> > vector){ 
    int count; 
    for(int j=0; j<20; j++){ 
     //run function 
     vector = ca2step(r, vector); 
    } 
    if (vector[0] == va || vector[1] == va) { 
     count = 1; 
     } 
    else{ 
     count=0; 
    } 
    return (count); 
} 

int main() 
{ 
    vector< vector<int> > vinput; 
    vinput.reserve(32); 
    vinput.push_back(va); 
    vinput.push_back(vb); 
    int counter = 0; 

    for(unsigned long long int i=0;i<4294967295;i++){ //4294967295 
     counter += caevolve(i, vinput); 
     } 

    cout<< "Counter : " << counter << endl; 

    return 0; 

} 

Answer 1

您可以使用LinkedList而不是矢量。 LinkedLists有更快的插入（向量push_back），因爲他們永遠不需要調整自己的大小，這在很大程度上可能是一個代價高昂的操作。

Answer 2

Jack已經正確地識別出向量內的內存分配可能是一筆可觀的成本。所以把這些矢量移到循環外面，而不是創建全新的矢量。

這將每次迭代至少爲每個向量節省一次分配/釋放。

不要按值傳遞向量，而應使用const vector<vector<int>>&作爲ca2step的參數類型。這將爲內部循環的每次迭代節省大量的矢量副本（以及內存分配和釋放），這是一大堆。

Inside ca2step，使用堆棧數組（可能是std::array）而不是向量。這節省了更多的動態內存分配。 begin(arrayb)將適用於數組和向量（而不是arrayb.begin()）。

Answer 3

我想你可以擺脫最初的循環來填補rulearray，R上有位測試取代：測試第N位，你可以使用

(r & (1 << nth)) ? 1 : 0 ... 

然後rulearray的使用可以通過

被替換

arraya[i] + (r & (1 << (31 - (vll[i] + (2 * vl[i]) + (4 * arrayb[i]) + (8 * vr[i]) + (16 * vrr[i])) ? 1 : 0) 

rotate_copy可以與普通的舊數組一起使用：並且可以避免使用該分配進行太多的動態內存分配，因爲所有大小都是固定的。執行本使用的typedef：

typedef int t_array[32]; 
t_array arraya, arrayb, vll, vl, vr, vrr, vx; 

rotate_copy(arrayb,arrayb+2,arrayb+32,vll); 
rotate_copy(arrayb,arrayb+1,arrayb+32,vl);  
rotate_copy(arrayb,arrayb+31,arrayb+32,vr);  
rotate_copy(arrayb,arrayb+30,arrayb+32,vrr); 

然後，只需最後返回值需要堆分配的數組的副本：

output.push_back(vector<int>(arrayb,arrayb+32)); 
    output.push_back(vector<int>(vx,vx+32)); 

Answer 4

除了C++的表現，你應該考慮並行代碼，並利用多核架構。在我看來，你的問題是一個經典的例子。

Answer 5

儀器/配置文件並運行您的代碼說幾十萬或一百萬次迭代。確定花費大量執行時間的代碼部分。嘗試並改善這些部分的性能。重複。只有當你滿意的時候，你才能不再進一步改進，你是否應該嘗試運行超過四次以上的時間。

Answer 6

有太多的數組訪問。您需要預取或更多本地人來表示這些被重新獲取的數組元素。緩存友好。讀到這裏你ca2step功能超出這個

http://www.research.scea.com/research/pdfs/GDC2003_Memory_Optimization_18Mar03.pdf

Answer 7

把你所有的載體;使他們甚至全球變量。使用vector::reserve()可以在開始push_back()之前擴展它們的尺寸，您知道所有尺寸。由於ca2step現在可以在它外部的數組上工作，因此它不需要返回任何東西，所以不需要雙矢量向量;直接使用這兩個向量，當你完成後，他們只是vector::clear()。

另外，您可能需要將環路變量類型更改爲unsigned long或unsigned long long。

Answer 8

這應該由編譯器在一定程度上完成。在你的情況下，你應該嘗試並行化你的代碼。

Answer 9

感謝所有的幫助，我終於在合理的時間內（約11小時）得到了這個工作。只是想我會分享我的代碼。我將需要在接下來的幾周內運行這幾次，所以如果有任何其他技巧我可以用來進一步減少時間，建議將不勝感激！

#include <iostream> 
using namespace std; 

bool is_equal (int a[], int b[]){ 
    for (int i=0; i<32; i++){ 
     if (a[i] != b[i]) 
      return false; 
    } 
    return true; 
} 

int ca2step (long long int rule, int arraya[32], int arrayb[32]){ 
    int count =0; 
    int x[32]; 
    int y[32]; 
    for(int i=0;i<32;i++){ 
     x[i] = arraya[i]; 
     y[i] = arrayb[i]; 
    } 

    for (int j=0; j<19;j++){ 
      int arrayc[32]; 
      for (int i=0; i<32; i++){ 
      arrayc[i] = (x[i] + ((rule >> (y[(i+2)%32] + (2 * y[(i+1)%32]) + 
        (4 * y[i]) + (8 * y[(i+31)%32]) + (16 * y[(i+30)%32])))& 1))%2; 
      } 

      for(int k=0;k<32;k++){ 
       x[k] = y[k]; 
       y[k] = arrayc[k];} 
    } 

    if(is_equal(y, arraya) || is_equal(y, arrayb)){ 
     count++;} 
    return(count);  
} 

int main(){ 
    int a[32] = {0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 
       0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1}; 
    int b[32] = {1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 
       0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}; 
    int counter = 0; 
    for(long long int i=0;i<10000000;i++){ //4294967295 
     counter += ca2step(i, a, b); 
     } 

    cout << counter ; 
    return 0; 
} 

Answer 10

我通過了這個線程，並看看這個問題。但它已經有一段時間了。無論如何，我已經嘗試使用一些按位運算符和openmp。

我的假設：1的二進制數 2.所有32位

我已經通過單個int替換所有陣列的處理，因爲只有包含您32寬陣列「0」和「1」剛好適合很好融入一個int（4字節）。這樣做可以幫助您消除一些循環並節省內存訪問。

更新* 學到了一些新花樣，用一些最起碼的彙編代碼

#include <iostream> 
using namespace std; 

#define MASK 0x1F /*last 5 bits*/ 

unsigned int toInt(int a[32]){ 
    int result = 0; 
    for(int i = 0; i<32;i++) 
    if(a[i]==1) result |= 1 << (31-i); 
    return result; 
} 

inline unsigned int ror(unsigned int v,unsigned int sh){ 
//rotate v to the right by sh 
    asm("ror %1,%0;" :"=r"(v) : "cI"(sh), "0"(v)); 
    return v; 
} 

unsigned int compute(unsigned int rule, unsigned int target){ 
    unsigned int t = rol(target,3); 
    unsigned int d = 0; 
    unsigned int k; 
    for(int i=0;i<32;i++){ 
     k = (t & MASK); 
     d |= ((rule>>k) & 1) << (31-i) ; 
     t = rol(t,1);  
    } 
    return d; 
} 

int ca2step (unsigned int rule, unsigned int a, unsigned int b){ 
    unsigned int xx = a; 
    unsigned int yy = b; 

    int tmp; 
    unsigned int d,tmpyy; 

    for (int j=0; j<19;j++){ 
     d = compute(rule,yy); 
     tmpyy = xx^d ; 
     xx = yy; 
     yy = tmpyy; 
    } 
    return (yy == a || yy == b) ; 
}  

int main(){ 

    int a[32] = {0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 
       0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1}; 
    int b[32] = {1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 
       0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}; 
    int counter = 0; 
    unsigned int aa = toInt(a); 
    unsigned int bb = toInt(b); 

    #pragma omp parallel for reduction(+:counter) 
    for(unsigned int i=0;i < 0xffffffff ;i++){ 
     counter += ca2step(i, aa, bb); 
    } 

    cout << counter <<"\n"; 

    return 0; 
} 

更新，編譯：

g++ filename.cpp -O3 -fopenmp