Быстрое двоичное добавление C++

Question

Я хочу улучшить скорость моей текущей проблемы с добавлением двоичных файлов. То, что он делает, это создать 2 вектора с размером K и первым добавить 1. Возможно, он не может быть быстрее, но если это возможно, сообщите мне.

Edit: Модифицированный для изменения константный вектора & а, Const вектор & б

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

Answer 1

Прежде всего, это:

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

должно быть:

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

Вы копирование входных параметров векторов без причины, передайте их по ссылке а не по значению, что требует копирования.

Еще одна вещь, которую вы могли бы попробовать, которая может улучшить скорость, - это простой метод, называемый loop unwinding (or unrolling). Это, конечно же, не сделает ваш код более читабельным или красивым, но может на самом деле ускорить его - но сравните его с простой скомпилированной версией с максимальной оптимизацией (обычно опция компилятора -O3), может случиться так, что ваш компилятор уже выполняет ту же оптимизацию (или другую, с лучшим эффектом).

Answer 2

Я просто сделал быстрый хак, чтобы сделать очевидное решение:

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.05ms медленнее. Тем не менее, это измерение только фактического добавления, а не всего вектора, а для двоичного числа, которое составляет 35000 целых чисел, - и это все равно занимает всего 0,1 мс за добавление на моем довольно древнем четырехъядерном процессоре AMD.

В моем тестировании создание/инициализация массива занимает около половины общего времени в качестве измерения общего времени. Добавление ссылки const делает ее примерно в два раза быстрее для функции фактического добавления. Это определенно быстрее, чем функция ORIGINAL, но, как я уже сказал, она немного медленнее - но яснее.