2

我目前正在从事一个涉及大量迭代的项目（准确地说是 2^32）。在我的大部分计算中，我主要使用mathematica，但它无法处理那种数量的过程。有人建议我c++可以处理它，所以昨晚我学习了c++并编写了以下代码：

//old code

代码运行良好，（我检查了较小的参数）但我已经开始运行它 4294967295 = 2^32-1 步骤，我认为这需要数百个小时。如果有人能告诉我是否有办法优化此代码的某些部分以使其运行得更快，我将不胜感激？我对这种语言没有经验，所以我如何构造函数可能看起来很混乱。我认为我的 Ca2step 函数运行得非常有效（我可能错了），而且我认为我在主要部分中的循环正在减慢一切。我认为必须有更快的方法来完成我想要完成的工作，所以任何帮助都会很棒。谢谢，理查德。

======= 更新 ========

非常感谢大家，我真的很感激。好的，这对我来说都是新事物，所以我发现很难理解某些事情的含义。下面是我更新的代码。但是我觉得它仍然很慢。有些人建议“并行化”，但我不知道这是什么以及我会怎么做？再次感谢，理查德。

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

}
4

10 回答 10

3

除了 C++ 性能之外，您还应该考虑并行化代码并利用多核架构。在我看来，你的问题是一个典型的例子。

于 2012-07-20T16:38:37.213 回答
1

仪器/配置文件并运行您的代码进行十万或一百万次迭代。确定花费大量执行时间的代码部分。尝试并提高这些部分的性能。重复。只有当你对自己无法再进步感到满意时，你才应该尝试运行它超过四十亿次。

于 2012-07-20T16:44:01.413 回答
1

数组访问太多。您需要一个预取或更多局部变量来表示这些重新取回的数组元素。缓存友好。在这里阅读

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

于 2012-07-20T16:51:42.597 回答
1

将所有向量移到ca2step函数之外；使它们甚至是全局变量。vector::reserve()在开始使用它们之前使用扩展它们的尺寸push_back()，你知道所有的尺寸。由于ca2step现在将在它外部的数组上工作，它不需要返回任何东西，所以不需要两个向量的向量；直接使用这两个向量，当你完成后，就用vector::clear()它们。

此外，您可能需要将循环变量类型更改为unsigned longor unsigned long long。

于 2012-07-20T17:10:03.243 回答
1

Jack 已经正确地确定了向量内的内存分配可能是一个巨大的成本。因此，将向量移到循环之外，并简单地使用clear()它们而不是创建全新的向量。

这将在每次迭代中为每个向量节省至少一次分配/解除分配。

不要按值传递向量，而是const vector<vector<int>>&用作ca2step. 这将为内部循环的每次迭代节省一大堆向量副本（以及内存分配和释放），这是一大堆。

在内部ca2step，使用堆栈数组（也许std::array）而不是向量。这可以节省更多的动态内存分配。 begin(arrayb)将适用于数组和向量（而不是arrayb.begin()）。

于 2012-07-20T16:29:21.857 回答
1

这在某种程度上应该由编译器完成。在您的情况下，您应该尝试并行化您的代码。

于 2012-07-20T22:13:33.140 回答
0

You could use a LinkedList instead of a vector. LinkedLists have faster insertion (push_back for vectors) since they never need to resize themselves, which, at large numbers, can be a costly operation.

于 2012-07-20T16:26:04.217 回答
0

我通过了这个线程并查看了问题。但已经有一段时间了。无论如何，我已经尝试使用一些位运算符和 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
于 2013-04-03T03:47:12.673 回答
0

感谢所有帮助，我终于在合理的时间内（大约 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;
}
于 2012-07-22T14:42:34.510 回答
0

我认为你可以摆脱初始循环来填充规则数组，替换为 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));
于 2012-07-20T16:35:41.183 回答