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

ジャックは、ベクトル内のメモリ割り当てがかなりのコストになる可能性があることを正しく認識しています。そのため、ベクトルをループの外に移動し、clear()まったく新しいものを作成する代わりに単純にします。

これにより、反復ごとにベクトルごとに少なくとも 1 つの割り当て/割り当て解除が節約されます。

ベクトルを値で渡さないでください。代わりにconst vector<vector<int>>&、 のパラメータ タイプとして使用してくださいca2step。これにより、内部ループの反復ごとに大量のベクトル コピー (およびメモリの割り当てと解放) が節約されます。

内部では、ベクトルの代わりにca2stepスタック配列 (おそらく ) を使用します。std::arrayこれにより、動的メモリ割り当てがさらに節約されます。 begin(arrayb)配列とベクトルの両方で機能します ( の代わりにarrayb.begin())。

于 2012-07-20T16:29:21.857 に答える
1

すべてのベクトルをca2step関数の外に移動します。それらをグローバル変数にします。vector::reserve()あなたがそれらに入る前にそれらのサイズを拡張するために使用してくださいpush_back()。あなたはすべてのサイズを知っています. 外部の配列で機能するようになったためca2step、何も返す必要がないため、2 つのベクトルのベクトルは必要ありません。これらの 2 つのベクトルを直接使用するだけですvector::clear()

unsigned longまた、ループ変数の型をorに変更する必要があるかもしれませんunsigned long long

于 2012-07-20T17:10:03.243 に答える
1

配列へのアクセスが多すぎます。これらの再フェッチされた配列要素を表すには、プリフェッチまたは複数のローカルが必要です。キャッシュフレンドリー。ほらこれ読んで

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

于 2012-07-20T16:51:42.597 に答える
1

これは、コンパイラによってある程度行われるべきです。あなたの場合、コードを並列化してみてください。

于 2012-07-20T22:13:33.140 に答える
1

たとえば、10 万回または 100 万回の反復でコードを計測/プロファイルして実行します。かなりの実行時間が費やされているコードの部分を特定します。それらの部分のパフォーマンスを試して改善してください。繰り返す。これ以上改善できないと確信した場合にのみ、40 億回以上実行を試みる必要があります。

于 2012-07-20T16:44:01.413 に答える
0

ベクトルの代わりにLinkedListを使用できます。LinkedListは、サイズを変更する必要がないため、挿入が高速になります(ベクターの場合は、push_back)。これは、多くの場合、コストのかかる操作になる可能性があります。

于 2012-07-20T16:26:04.217 に答える
0

r: のビット テストに置き換えて、rulearray を埋めるための最初のループを取り除くことができると思います: 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 に答える
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 に答える