5

There is a function which is getting maximum values of each period-length interval in 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 function by performance?

ivan_pozdeev
  • 33,874
  • 19
  • 107
  • 152
Ufx
  • 2,595
  • 12
  • 44
  • 83
  • Why multiple C++ standards tagged? Is the code required to conform to all of them or something? – ivan_pozdeev Mar 31 '18 at 09:51
  • 1
    @ivan_pozdeev I mean c++11-17 is allowed for my project. – Ufx Mar 31 '18 at 09:52
  • 1
    As a naive solution you can try to keep sorted multiset and update it while moving to the next period. This should give you O(N*logN) performance for adding / removing elements and O(1) to get max element – awesoon Mar 31 '18 at 09:52
  • 1
    See range maximum query – Passer By Mar 31 '18 at 09:58
  • 2
    https://stackoverflow.com/questions/12190184/can-min-max-of-moving-window-achieve-in-on/12195098#12195098 – MBo Mar 31 '18 at 10:12

1 Answers1

0

You could check if the preceding calculated max value coincide with the first value of the preceding range: if not, the new max become the std::max between the old max and the last position of the new interval.

Something as (caution: code not tested)

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 become a little obfuscated)

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) );      }
}
max66
  • 65,235
  • 10
  • 71
  • 111