c++ function with max_element & iterator = 3x slower

Question

The program I am developing gets three times slower when I call the following function. It wouldn't be bad if it was not called a couple million of times.

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 takes the value 500. Is there another way to speed up significantly this function?

Answer 1

max_element and min_element are both iterating through the range, when the entire step could be done in one function.

I believe some compilers have a minmax_element function in their STL, but I do not believe it is in the standard. You could write your own. I originally wrote this as an untemplated version, but if you have a good compiler it should make no difference.

Try something like this (untested)

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

You could replace those two calls with a single std::minmax_element().

Answer 3

Contrary to what others say, I don't believe replacing the two calls to std::max_element() and std::min_element() with a single minmax_element() would improve performance in a significant manner, because iterating 2*n times with 1 operation or iterating n times with 2 operations makes little to no difference.

What would make a difference however is to eliminate the two calls altogether from your algorithm. That is, find the minimum and maximum elements and then check against those when new data comes in, rather than comparing new data against the entire container again.

 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 4

"3 times slower" with respect to what - to another implementation, or to just not calling this function? In the second case it is possible that it is just algorithmic complexity that makes it slower.

You didn't explain how your code is used exactly, in some cases you could cache the calculation of the min/max instead of doing that in a loop. For example, if the input vector is rarely changed, it doesn't make sense to recalculate that every time. And even when it changes, you can update min/max without going over periodos elements (dynamic programming might help).

You could also check the generated assembly to check for strange function calls (eg iterators secure checks), I know that at least MSVC 2005/2008 has them enabled by default even in Release mode (see the _SCL_SECURE macro).

Answer 5

This isn't an answer to the specific question about performance, so maybe it has no value. But it seems that the excludeWrong compare function would cause unexpected or possibly implementation-dependent results. If the first value compared is -1, then it may be computed as both the min and the max for all cases. I tested with both gcc v4.0.2 and Microsoft's compiler v15.00.21022.08. For example, the following:

   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

Maybe that is the desired result, but it seems a bit odd.