Я использую шаблоны выражений в векторном классе для преобразований, таких как скользящие средние. Здесь, в отличие от стандартных арифметических операций, 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);
}
Это может быть расширено таким образом, что хранилище применяется только для нескольких приложений и т. Д.
Задача ещё не решена.