How to optimize getting maximum values ​​in an array?

Question

There is a function that gets the maximum values ​​of each period -length interval in an array.

 void f(const std::vector<double> &v, std::vector<double> &vv, size_t period) { vv.resize(v.size()); for (size_t i = period; i <= v.size(); ++i) { vv[i - 1] = *std::max_element(v.begin() + i - period, v.begin() + i); } } 

How can I optimize this feature for performance?

Answer 1

You can check whether the previous calculated maximum value matches the first value of the previous range: if not, the new max will become std::max between the old max and the last position of the new interval.

Something like (caution: code not verified)

 void f(const std::vector<double> &v, std::vector<double> &vv, size_t period) { vv.resize(v.size()); bool oldMaxFirst = false; for (size_t i = period; i <= v.size(); ++i) { if ( oldMaxFirst ) vv[i - 1] = std::max(vv[i - 2], v[i - 1]); else vv[i - 1] = *std::max_element(v.begin() + i - period, v.begin() + i); oldMaxFirst = vv[i - 1] == v[i - period]; } } 

or also (but the code gets a little confusing)

 void f(const std::vector<double> &v, std::vector<double> &vv, size_t period) { vv.resize(v.size()); bool oldMaxFirst = false; for (size_t i = period; i <= v.size(); ++i) { oldMaxFirst = v[i - period] == (vv[i - 1] = (oldMaxFirst ? std::max(vv[i - 2], v[i - 1]) : *std::max_element(v.begin() + i - period, v.begin() + i) ); } }