1

現在の 2 進数の加算問題の速度を改善したいと考えています。サイズが K の 2 つのベクトルを作成し、最初のベクトルに 1 を追加します。これ以上速くなることはありませんが、可能であればお知らせください。

編集：const vector& a、const vector& bを変更するために修正

#include <stdio.h>
#include <windows.h>
#include <iostream>
#include <vector>

using namespace std;

vector<int> BinaryAddition(const vector<int>& a, const vector<int>& b, int tam){
    vector<int> c(tam);
    int ac = 0;

    for(int i=tam-1; i>-1; i--){
        c[i] = ((a[i] ^ b[i]) ^ ac); //a xor b xor c
        ac = ((a[i] & b[i]) | (a[i] &ac)) | (b[i] & ac); 
    }

    return c;
}

/* retorna "a - b" en segundos */
double performancecounter_diff(LARGE_INTEGER *a, LARGE_INTEGER *b)
{
    LARGE_INTEGER freq;
    QueryPerformanceFrequency(&freq);
    return (double)(a->QuadPart - b->QuadPart) / (double)freq.QuadPart;
}

int main(int argc, char *argv[])
{
    LARGE_INTEGER t_ini, t_fin;
    double secs;

    QueryPerformanceCounter(&t_ini);

    int k=15;

    vector<int> uno1 (k,0);
    vector<int> pro (k,0);
    vector<int> pro1(k,0);

    uno1[k-1] = 1;

    pro1 = BinaryAddition(pro, uno1, k);

    QueryPerformanceCounter(&t_fin);

    secs = performancecounter_diff(&t_fin, &t_ini);
    printf("%.16g milliseconds\n", secs * 1000.0);

    return 0; 
}
4

2 に答える 2

3

まず第一に、これ：

vector<int> BinaryAddition(vector<int> a, vector<int> b, int tam)

次のようにする必要があります。

vector<int> BinaryAddition(const vector<int>& a, const vector<int>& b, int tam)

理由もなく入力パラメーターのベクトルをコピーしています。コピーが必要な値ではなく参照で渡します。

速度を向上させるために試すことができるもう 1 つの方法は、ループの巻き戻し (または展開)と呼ばれる単純な手法です。これにより、コードが読みやすくなったりきれいになったりすることはありませんが、実際には少し速度が向上する可能性があります。ただし、単純なバージョンと比較してください。最大の最適化 (通常はコンパイラーのオプション-O3) でコンパイルすると、コンパイラーが既に同じ最適化 (またはより良い効果を持つ別の最適化) を行っている可能性があります。

于 2013-05-23T08:44:18.610 に答える
1

明らかな解決策を作るために簡単なハックを行いました：

vector<int> BinaryAddition3(const vector<int> &a, const vector<int> &b, int tam){
    vector<int> c(tam);
    int ac = 0;

    for(int i=tam-1; i>-1; i--){
       int t = a[i]+b[i] + ac;
       ac = t > 1;
       c[i] = t & 1;
    }

    return c;
}

これは実際には、元の質問に投稿された明確でない xor/or バリアントよりもわずかに遅く、約 0.05 ミリ秒遅くなります。ただし、これはベクトル全体ではなく実際の加算のみを測定しており、35000 整数の長さの 2 進数を測定しています。私のかなり古い AMD クアッド コア プロセッサでは、加算ごとに 0.1 ミリ秒しかかかりません。

私のテストでは、アレイの作成/初期化には、合計時間の測定として合計時間の約半分がかかりました。参照を追加constすると、実際の追加関数の約 2 倍の速度になります。これは ORIGINAL 関数よりも間違いなく高速ですが、前述のように、わずかに遅くなりますが、より明確になります。

于 2013-05-23T09:21:47.043 に答える