Поэлементное векторное искажение
Что может быть более быстрой (с точки зрения времени, требуемого кодом) альтернативой следующему методу для умножения двух n целое число элемента векторы:
{
// code for obtaining two n element int vectors, a and b
}
int temp = 0; // a temporary variable
for (int ii = 0; ii < n; ++ii)
temp += a[ii]*b[ii];
Редактировать:
Получил несколько приятных идей. Я должен был бы проверить каждого из них, чтобы увидеть, какой из них лучший. Конечно, каждый из ответов говорит мне что-то новое.
Решение
Единственный способ сделать это быстрее в C ++ — это исправить «зависимость, переносимую циклом», что означает, что каждая итерация должна ждать, пока предыдущее временное значение не станет доступным для суммы. Это может быть достигнуто путем развертывания и использования нескольких переменных накопления:
int t0=0, t1=0, t2=0, t3=0;
for (int ii = 0; ii < n; ii += 4) {
t0 += a[ii]*b[ii];
t1 += a[ii+1]*b[ii+1];
t2 += a[ii+2]*b[ii+2];
t3 += a[ii+3]*b[ii+3];
}
int temp = t0 + t1 + t2 + t3;
Современные процессоры могут выполнять несколько операций за цикл, но только при отсутствии зависимости в пути. В моей системе это дает улучшение примерно на 20%. Примечание: n должно быть кратным 4, или вам нужно добавить цикл «эпилог», который заканчивает оставшиеся элементы. Проверьте и измерьте! Я понятия не имею, является ли 4 «правильным» количеством развертывания.
Вы можете добиться гораздо большего улучшения, вызывая встроенные функции SIMD для конкретного процессора, но это не стандарт C ++.
Другие решения
#include <valarray>
int main() {
std::valarray<int> a {1, 2, 3, 4, 5};
std::valarray<int> b {3, 4, 5, 6, 7};
auto c = (a * b).sum();
}
valarray может использовать SIMD и другие векторные инструкции, хотя в обычных реализациях им, похоже, регулярно пренебрегают.
Просто используйте стандартную библиотеку C ++:
#include<algorithm>
#include<iostream>
#include<vector>
int main() {
std::vector<double> x = {1, 2, 3};
std::vector<double> y = {4, 5, 6};
double xy = std::inner_product(x.begin(), x.end(), y.begin(), 0);
std::cout<<"inner product: "<<xy<<std::endl;
return 0;
}
Изменить: добавлена информация о времени.
Просто из любопытства я добавил следующую информацию о времени.
Исходный код:
#include<algorithm>
#include<iostream>
#include<vector>
#include<random>
#include<boost/timer/timer.hpp>
int main(int argc, char* argv[]) {
// get the desired number of elements
if(argc!=2) {
std::cerr<<"usage: "<<argv[0]<<" N"<<std::endl;
return EXIT_FAILURE;
}
int N = std::stoi(argv[1]);
// set-up the random number generator
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<> dis(-100, 100);
// prepare the vectors
std::vector<double> x, y;
// fill the vectors with random numbers
auto rgen = [&dis, &gen]() { return dis(gen); };
std::generate_n(std::back_inserter(x), N, rgen);
std::generate_n(std::back_inserter(y), N, rgen);
// Heat-up the cache (try commenting-out this line and you'll see
// that the time increases for whatever algorithm you put firts)
double xy = std::inner_product(x.begin(), x.end(), y.begin(), 0.0);
std::cout<<"heated-up value: "<<xy<<std::endl;
{ // start of new timing scope
// write a message to the assembly source
boost::timer::auto_cpu_timer t;
asm("##### START OF ALGORITHMIC APPROACH #####");
double xy = std::inner_product(x.begin(), x.end(), y.begin(), 0.0);
asm("##### END OF ALGORITHMIC APPROACH #####");
std::cout<<"algorithmic value: "<<xy<<std::endl<<"timing info: ";
} // end of timing scope{ // start of new timing scope
// write a message to the assembly source
boost::timer::auto_cpu_timer t;
asm("##### START OF HAND-CODED APPROACH #####");
double tmp = 0.0;
for(int k=0; k<N; k++) {
tmp += x[k] * y[k];
}
asm("##### END OF HAND-CODED APPROACH #####");
std::cout<<"hand-coded value: "<<tmp<<std::endl<<"timing info: ";
} // end of timing scopereturn EXIT_SUCCESS;
}
Окружающая среда: 2,7 ГГц Intel Core i7; OS X 10.7.4; gcc 4.8.1;
Команда компиляции: g++ -O3 inner-product-assembly.cpp -std=c++11 -lboost_timer -lboost_system
Образцы прогонов:
[11:01:58 ~/research/c++] ./a.out 10
heated-up value: 8568.75
algorithmic value: 8568.75
timing info: 0.000006s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
hand-coded value: 8568.75
timing info: 0.000004s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
[11:01:59 ~/research/c++] ./a.out 100
heated-up value: -13072.2
algorithmic value: -13072.2
timing info: 0.000006s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
hand-coded value: -13072.2
timing info: 0.000004s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
[11:02:03 ~/research/c++] ./a.out 1000
heated-up value: 80389.1
algorithmic value: 80389.1
timing info: 0.000010s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
hand-coded value: 80389.1
timing info: 0.000007s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
[11:02:04 ~/research/c++] ./a.out 10000
heated-up value: 89753.7
algorithmic value: 89753.7
timing info: 0.000041s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
hand-coded value: 89753.7
timing info: 0.000039s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
[11:02:05 ~/research/c++] ./a.out 100000
heated-up value: -461750
algorithmic value: -461750
timing info: 0.000292s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
hand-coded value: -461750
timing info: 0.000282s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
[11:02:07 ~/research/c++] ./a.out 1000000
heated-up value: 2.52643e+06
algorithmic value: 2.52643e+06
timing info: 0.002702s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
hand-coded value: 2.52643e+06
timing info: 0.002660s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
[11:02:09 ~/research/c++] ./a.out 10000000
heated-up value: 6.04128e+06
algorithmic value: 6.04128e+06
timing info: 0.026557s wall, 0.030000s user + 0.000000s system = 0.030000s CPU (113.0%)
hand-coded value: 6.04128e+06
timing info: 0.026335s wall, 0.030000s user + 0.000000s system = 0.030000s CPU (113.9%)
[11:02:11 ~/research/c++] ./a.out 100000000
heated-up value: 2.27043e+07
algorithmic value: 2.27043e+07
timing info: 0.264547s wall, 0.270000s user + 0.000000s system = 0.270000s CPU (102.1%)
hand-coded value: 2.27043e+07
timing info: 0.264346s wall, 0.260000s user + 0.000000s system = 0.260000s CPU (98.4%)
Таким образом, преимущество в скорости при использовании подхода с ручным кодированием имеет значение, только если вы используете меньшие массивы. После отметки в 10000 я бы посчитал их время выполнения идентичным, но я предпочитаю алгоритмический подход, потому что его проще писать и поддерживать, и он может выиграть от обновлений библиотеки.
Как обычно, эта информация о времени должна быть взята с зерном соли.
Быстрый ответ: это, вероятно, самое быстрое решение.
Длинный ответ: есть два определения поста.
Если вы ищете быстрое и несложное решение, приведенный выше код должен хорошо подойти.
Если вы ищете быстро работающий код, я не знаю, поможет ли повторное выполнение цикла for с помощью цикла while или использование библиотек / пакетов.
Удачи!