1

我想提高当前二进制加法问题的速度。它所做的是创建 2 个大小为 K 的向量，并在第一个向量上添加 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)

您无缘无故地复制输入参数向量，通过引用而不是值传递它们，这需要复制。

您可以尝试的另一件可能会提高速度的方法是一种称为循环展开（或展开）的简单技术，这肯定不会使您的代码更具可读性或更漂亮，但实际上可能会加快一些速度 - 但请将其与简单版本进行比较以最大优化（通常是编译器的选项-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;
}

这实际上比原始问题中发布的不太清楚的异或/或变体慢了一小部分——慢了大约 0.05 毫秒。然而，这只是测量实际加法，而不是整个向量，并且对于一个 35000 整数长的二进制数 - 在我相当古老的 AMD 四核处理器上，每次加法仍然只需要 0.1 毫秒。

在我的测试中，数组的创建/初始化大约需要总时间的一半作为总时间的测量。添加const引用使实际添加功能的速度提高了大约两倍。这绝对比 ORIGINAL 函数快，但就像我说的，它稍微慢一些 - 但更清晰。

于 2013-05-23T09:21:47.043 回答