1

当我调用以下函数时，我正在开发的程序会慢三倍。如果它没有被调用几百万次，那还不错。

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。是否有另一种方法可以显着加快此功能？

路易斯

4

5 回答 5

3

编辑：没有注意到你使用谓词（西班牙语让我有点失望！）让我重写几分钟......

max_elementmin_element当整个步骤可以在一个函数中完成时，两者都在迭代范围。

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

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

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>());
}
于 2011-02-24T15:24:25.647 回答
3

与其他人所说的相反，我不相信将两个调用替换为std::max_element()单个std::min_element()调用minmax_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(...);
    }
}
于 2011-02-24T15:27:31.623 回答
1

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

于 2011-02-24T15:24:04.260 回答
0

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

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

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

于 2011-02-24T15:42:14.840 回答
0

这不是关于性能的具体问题的答案，所以它可能没有价值。但似乎excludeWrong比较函数会导致意外或可能依赖于实现的结果。如果比较的第一个值是-1，那么它可以计算为所有情况下的最小值和最大值。我用 gcc v4.0.2 和微软的编译器 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;

印刷：

min: -1
max: -1

也许这是想要的结果，但似乎有点奇怪。

于 2011-02-24T15:56:00.920 回答