C ++: производительность цикла в шаблоне выражений

Я использую шаблоны выражений в векторном классе для преобразований, таких как скользящие средние. Здесь, в отличие от стандартных арифметических операций, operator[](size_t i) не делает ни единого доступа к элементу iно, скорее, существует целый цикл, который необходимо оценить, например, для скользящего среднего вектора v

double operator[](size_t i) const
{
double ad=0.0;
for(int j=i-period+1; j<=i; ++j)
ad+=v[j];
return ad/period;
}

(это не настоящая функция, потому что нужно заботиться о неотрицательных показателях, но сейчас это не имеет значения).

Используя такую ​​конструкцию скользящего среднего, я боюсь, что код становится довольно неэффективным, особенно если взять двойное или тройное скользящее среднее. Затем получают вложенные циклы и, следовательно, квадратичное или кубическое масштабирование с размером периода.

У меня вопрос, настолько ли умны компиляторы, чтобы как-то оптимизировать такие избыточные циклы? Или это не тот случай, и нужно вручную позаботиться о промежуточном хранении (что я и думаю)? Как можно сделать это разумно в приведенном ниже примере кода?


Пример кода, адаптированы из Википедия, компилируется с Visual Studio 2013:

CRTP-базовый класс и фактический вектор:

#include <vector>

template <typename E>
struct VecExpression
{
double operator[](int i) const { return static_cast<E const&>(*this)[i]; }
};

struct Vec : public VecExpression<Vec>
{
Vec(size_t N) : data(N) {}
double operator[](int i) const { return data[i]; }
double& operator[](int i) { return data[i]; }

std::vector<double> data;
};

Класс скользящей средней:

template <typename VectorType>
struct VecMovingAverage : public VecExpression<VecMovingAverage<VectorType> >
{
VecMovingAverage(VectorType const& _vector, int _period) : vector(_vector), period(_period) {}
double operator[](int i) const
{
int s = std::max(i - period + 1, 0);
double ad = 0.0;
for (int j = s; j <= i; ++j)
ad += vector[j];
return ad / (i - s + 1);
}

VectorType const& vector;
int period;
};

template<typename VectorType>
auto MovingAverage(VectorType const& vector, int period = 10) -> VecMovingAverage<VectorType>
{
return VecMovingAverage<VectorType>(vector, period);
}

Теперь мои вышеупомянутые страхи возникают с такими выражениями, как это,

Vec vec(100);
auto tripleMA= MovingAverage(MovingAverage(MovingAverage(vec,20),20),20);
std::cout << tripleMA[40] << std::endl;

я полагаю, что требуется 20^3 оценки для одного operator[] …?


РЕДАКТИРОВАТЬ: Одним из очевидных решений является сохранение результата. Переехать std::vector<double> data в базовый класс, затем измените класс Moving Average на что-то вроде (не проверено)

template <typename VectorType, bool Store>
struct VecMovingAverage : public VecExpression<VecMovingAverage<VectorType, Store> >
{
VecMovingAverage(VectorType const& _vector, int _period) : vector(_vector), period(_period) {}
double operator[](int i) const
{
if(Store && i<data.size())
{
return data[i];
}
else
{
int s = std::max(i - period + 1, 0);
double ad = 0.0;
for (int j = s; j <= i; ++j)
ad += vector[j];
ad /= (i - s + 1)

if(Store)
{
data.resize(i+1);
data[i]=ad;
}
return ad;
}
}

VectorType const& vector;
int period;
};

Затем в функции можно сохранить результат:

template<typename VectorType>
auto MovingAverage(VectorType const& vector, int period = 10) -> VecMovingAverage<VectorType>
{
static const bool Store=true;
return VecMovingAverage<VectorType, Store>(vector, period);
}

Это может быть расширено таким образом, что хранилище применяется только для нескольких приложений и т. Д.

0

Решение

Задача ещё не решена.

Другие решения


По вопросам рекламы [email protected]