c++具有 max_element & 的函数迭代器 = 慢 3 倍

Question

当我调用以下函数时，我正在开发的程序变慢了三倍。 如果不被调用几百万次也不错。

double obterNormLarguraBanda(const std::vector<double>& v, int periodos)
{
    int aa; 
    double maximo, minimo, valor;
    std::vector<double>::const_iterator inicio;
    if (v.size() < periodos)
    {   
        inicio = v.begin();
    }   
    else
    {   
        inicio = v.end() - periodos;
    }   
    maximo = *max_element(inicio, v.end(), excludeWrong);
    minimo = *min_element(inicio, v.end(), excludeWrong);
    return (v.back()-minimo)/(maximo - minimo);
}

bool excludeWrong(double i, double j)
{
    if (i==-1 || j==-1) return false;
    return i<j;
}

periodos 的值为 500。 还有其他方法可以显着加快此功能吗？

Answer 1

当整个步骤可以在一个函数中完成时，max_element 和 min_element 都在范围内迭代。

我相信某些编译器在其 STL 中有一个 minmax_element 函数，但我不相信它在标准中。你可以自己写。我最初将其编写为非模板版本，但如果您有一个好的编译器，那么它应该没有什么区别。

尝试这样的事情（未经测试）

template <typename Iter, typename Pred>
void minmax_element(Iter begin, Iter end, Iter& min, Iter& max, const Pred& comp)
{
    min = begin;
    max = begin;
    
    typedef std::iterator_traits<Iter>::value_type T;
    for (++begin; begin != end; ++begin)
    {
        if (comp(*max, *begin))
            max = begin;
        else if (comp(*begin, *min))
            min = begin;
    }
}

template <typename Iter>
void minmax_element(Iter begin, Iter end, Iter& min, Iter& max)
{
    minmax_element(begin, end, min, max, std::less<std::iterator_traits<Iter>::value_type>());
}

Answer 2

与其他人所说的相反，我不相信用单个 minmax_element 替换对 std::max_element() 和 std::min_element() 的两个调用() 会显着提高性能，因为使用 1 个操作迭代 2*n 次或使用 2 个操作迭代 n 次几乎没有区别。

然而，重要的是从算法中完全消除这两个调用。也就是说，找到最小和最大元素，然后在新数据进入时检查这些元素，而不是再次将新数据与整个容器进行比较。

 double obterNormLarguraBanda(const std::vector<double>& v,
                              double maximo, double minimo)
{
    return (v.back()-minimo)/(maximo - minimo);
}

bool excludeWrong(double i, double j)
{
    if (i==-1 || j==-1) return false;
    return i<j;
}

// usage example
void f()
{
    std::vector<double> v;
    // ...
    double maximo = *max_element(inicio, v.end(), excludeWrong);
    double minimo = *min_element(inicio, v.end(), excludeWrong);
    for( int i = 0; i != 1000; ++i ) {
        // if( ! excludeWrong(new_datum, maximo) ) maximo = new_datum;
        // if( excludeWrong(new_datum, minimo) ) minimo = new_datum;
        double d = obterNormLarguraBanda(...);
    }
}

Answer 3

您可以用一个 std::minmax_element() 替换这两个调用。

Answer 4

“慢 3 倍”相对于什么 - 另一个实现，或者只是不调用这个函数？在第二种情况下，可能只是算法复杂性导致速度变慢。

您没有解释您的代码是如何准确使用的，在某些情况下，您可以缓存最小/最大的计算，而不是在循环中执行此操作。例如，如果输入向量很少改变，那么每次都重新计算是没有意义的。即使它发生变化，您也可以更新最小值/最大值，而无需遍历 periodos 元素（动态编程可能会有所帮助）。

您还可以检查生成的程序集以检查奇怪的函数调用（例如迭代器安全检查），我知道至少 MSVC 2005/2008 即使在发布模式下也默认启用它们（请参阅 _SCL_SECURE 宏）。

Answer 5

这不是有关性能的具体问题的答案，因此也许它没有价值。但似乎 excludeWrong 比较函数会导致意外或可能与实现相关的结果。如果比较的第一个值是-1，那么它可以被计算为所有情况的最小值和最大值。我使用 gcc v4.0.2 和 Microsoft 编译器 v15.00.21022.08 进行了测试。例如，以下内容：

   std::vector<double> v;
   v.push_back( -1 );
   v.push_back( 1 );
   v.push_back( 2 );
   cout << "min: " << *min_element( v.begin(), v.end(), excludeWrong ) << endl;
   cout << "max: " << *max_element( v.begin(), v.end(), excludeWrong ) << endl;

prints:

min: -1
max: -1

也许这就是期望的结果，但看起来有点奇怪。