我目前正在进行一个涉及大量迭代(确切地说是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;
}
除了C++性能外,您还应该考虑并行化代码并利用多核架构。在我看来,你的问题是一个典型的例子。
Jack已经正确地识别出向量内部的内存分配可能是一个巨大的成本。因此,将向量移动到循环之外,并简单地clear()
它们,而不是创建全新的向量。
这将在每次迭代中为每个向量至少保存一个分配/解除分配。
不要按值传递矢量,而是使用const vector<vector<int>>&
作为ca2step
的参数类型。这将为内部循环的每次迭代保存一大堆向量副本(以及内存分配和释放),这是一大堆。
在ca2step
中,使用堆栈数组(可能是std::array
)而不是矢量。这样可以节省更多的动态内存分配。begin(arrayb)
将同时适用于阵列和矢量(而不是arrayb.begin()
)。
仪器/配置文件并运行您的代码进行十万次或一百万次迭代。识别代码中花费大量执行时间的部分。试着提高这些部分的性能。重复只有当你对自己无法进一步改进感到满意时,你才应该尝试运行它超过4亿次。
有太多的数组访问。您需要一个预取或多个局部值来表示那些重新蚀刻的数组元素。缓存友好。此处阅读此
http://www.research.scea.com/research/pdfs/GDC2003_Memory_Optimization_18Mar03.pdf
将所有向量移动到ca2step
函数之外;使它们甚至成为全局变量。使用vector::reserve()
来扩展它们的大小,然后再开始使用push_back()
,您知道所有的大小。由于ca2step
现在将在其外部的数组上工作,因此它不需要返回任何内容,因此不需要两个向量的向量;直接使用这两个向量,完成后,只需vector::clear()
即可。
此外,您可能需要将循环变量类型更改为unsigned long
或unsigned long long
。
这在一定程度上应该由编译器完成。在您的情况下,您应该尝试并行化代码。
您可以使用LinkedList而不是矢量。LinkedList具有更快的插入速度(矢量为push_back),因为它们从不需要调整自己的大小,而在大量情况下,这可能是一项成本高昂的操作。
我认为你可以去掉填充规则数组的初始循环,代之以r上的比特测试:要测试第n个比特,你可以使用
(r & (1 << nth)) ? 1 : 0 ...
那么规则数组的使用可以被取代
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));
感谢您的帮助,我终于在合理的时间内(大约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;
}
我路过这个线程,看看这个问题。但这已经有很长一段时间了。无论如何,我已经尝试过使用一些位运算符和openmp。
我的假设:1。二进制数的处理2.所有32位
我用一个int替换了所有数组,因为您的32宽数组只包含"0"one_answers"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