функция c ++ с max_element & iterator = в 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 итерируютчерез диапазон, когда весь шаг мог бы быть выполнен в одной функции.

Я полагаю, что некоторые компиляторы имеют функцию minmax_element в своих STL, но я не верю, что это стандарт.Вы можете написать свой собственный.Первоначально я написал это как не публиковавшуюся версию, но если у вас есть хороший компилятор, это не должно иметь никакого значения.

Answer 2

Вопреки тому, что говорят другие, я не верю, что замена двух вызовов на std::max_element() и std::min_element() на один minmax_element() значительно повысит производительность, поскольку повторение 2 * n раз за 1 операцию илиповторение 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

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

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

Answer 5

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

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

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