c++algorithmconst-iterator

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


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?


Solution

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