如何优化在数组中获取最大值？

Question

有一个函数可以获得period数组中每个长度间隔的最大值.

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);
    }
}

如何通过性能优化此功能？

Answer 1

您可以检查前面计算的最大值是否与前面范围的第一个值一致：如果不一致，新的最大值将成为std::max旧最大值和新区间的最后位置之间的值。

类似（警告：代码未经测试）

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];
    }
}

或者也（但是代码变得有点混乱）

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) );      }
}