Функция C++ с max_element & iterator = в 3 раза медленнее

Программа, которую я разрабатываю, становится в три раза медленнее, когда я вызываю следующую функцию. Это не было бы плохо, если бы его не вызывали пару миллионов раз.

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. Есть ли другой способ значительно ускорить эту функцию?

Луис

Источник

5 ответов

Решение

РЕДАКТИРОВАТЬ: не заметил, что вы используете предикат (испанский немного сбил меня с толку!) Позвольте мне переписать на несколько минут...

max_element а также min_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>());
}
Источник

Вопреки тому, что говорят другие, я не верю замене двух призывов к std::max_element() а также std::min_element() с одним minmax_element() значительно улучшит производительность, потому что итерация 2*n раз с 1 операцией или n итераций с 2 ​​операциями мало что меняет.

Однако, что может изменить ситуацию, так это полностью исключить два вызова из вашего алгоритма. То есть найдите минимальный и максимальный элементы, а затем проверьте их при появлении новых данных, а не сравнивайте новые данные со всем контейнером снова.

 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(...);
    }
}
Источник

Вы можете заменить эти два звонка одним std::minmax_element(),

Источник

Это не ответ на конкретный вопрос о производительности, поэтому, возможно, это не имеет значения. Но похоже, что 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;

печатает:

min: -1
max: -1

Может быть, это желаемый результат, но это кажется немного странным.

Источник

"В 3 раза медленнее" по отношению к чему - к другой реализации или просто не вызывать эту функцию? Во втором случае возможно, что только алгоритмическая сложность делает его медленнее.

Вы не объяснили, как именно используется ваш код, в некоторых случаях вы можете кэшировать вычисление min/max вместо того, чтобы делать это в цикле. Например, если входной вектор редко изменяется, пересчитывать его каждый раз не имеет смысла. И даже когда он меняется, вы можете обновить мин / макс, не переходя periodos элементы (динамическое программирование может помочь).

Вы также можете проверить сгенерированную сборку, чтобы проверить наличие странных вызовов функций (например, проверки безопасности итераторов), я знаю, что по крайней мере в MSVC 2005/2008 они включены по умолчанию даже в режиме Release (см. Макрос _SCL_SECURE).

Источник
Другие вопросы по тегам