Вдохновленный Herb Sutter убедительной лекцией Не ваш отец С++, я решил еще раз взглянуть на последнюю версию С++ с помощью Microsoft Visual Studio 2010. Мне было особенно интересно по утверждению Herb, что С++ "безопасен и быстр", потому что я пишу много критически важных для работы кода.
В качестве эталона я решил попытаться написать один и тот же простой алгоритм БПФ на разных языках.
Я придумал следующий код С++ 11, который использует встроенный тип complex
и vector
:
#include <complex>
#include <vector>
using namespace std;
// Must provide type or MSVC++ barfs with "ambiguous call to overloaded function"
double pi = 4 * atan(1.0);
void fft(int sign, vector<complex<double>> &zs) {
unsigned int j=0;
// Warning about signed vs unsigned comparison
for(unsigned int i=0; i<zs.size()-1; ++i) {
if (i < j) {
auto t = zs.at(i);
zs.at(i) = zs.at(j);
zs.at(j) = t;
}
int m=zs.size()/2;
j^=m;
while ((j & m) == 0) { m/=2; j^=m; }
}
for(unsigned int j=1; j<zs.size(); j*=2)
for(unsigned int m=0; m<j; ++m) {
auto t = pi * sign * m / j;
auto w = complex<double>(cos(t), sin(t));
for(unsigned int i = m; i<zs.size(); i+=2*j) {
complex<double> zi = zs.at(i), t = w * zs.at(i + j);
zs.at(i) = zi + t;
zs.at(i + j) = zi - t;
}
}
}
Обратите внимание, что эта функция работает только для векторов n
-элементов, где n
является интегральной степенью двух. Любой, кто ищет быстрый код FFT, который работает для любого n
, должен смотреть на FFTW.
Как я понимаю, традиционный синтаксис xs[i]
из C для индексации a vector
не выполняет проверку границ и, следовательно, не является безопасным для памяти и может быть источником ошибок памяти, таких как детерминированное повреждение и нарушения доступа к памяти. Поэтому я использовал xs.at(i)
.
Теперь я хочу, чтобы этот код был "безопасным и быстрым", но я не эксперт на С++ 11, поэтому я хотел бы попросить улучшения этого кода, которые сделают его более идиоматичным или эффективным?