max_element & iterator = 3x slower 인 C++ 함수

Question

다음 함수를 호출하면 개발중인 프로그램이 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 소요?

루이스는

Answer 1

편집 : 모두의 범위를 반복하고 있습니다 ...

max_element 및 min_element을 술어의 사용 (! 스페인이 나를 조금을 던졌다) 나에게 몇 분 동안 다시 보자 통지를하지 않았다 때 전체 단계는 하나의 기능으로 수행 될 수 있습니다.

일부 컴파일러는 STL에 minmax_element 기능이 있지만 믿을 수는 없다고 생각합니다. 당신은 당신 자신의 것을 쓸 수 있습니다. 나는 원래 이것을 비판적인 버전으로 썼지 만, 좋은 컴파일러를 가지고 있다면 아무런 차이가 없어야합니다. (테스트되지 않은)이 같은

시도 뭔가

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

단일 std::minmax_element()와 두 통화를 대체 할 수있다.

Answer 3

반대로 다른 사람이 무슨 말을 나는 중요한 방법으로 성능을 개선 할 하나의 minmax_element()로 std::max_element() 및 std::min_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(...); 
    } 
} 

Answer 4

다른 구현과 관련하여 "3 배 느리게"또는이 함수를 호출하지 말아야하나요? 두 번째 경우에는 알고리즘 복잡성으로 인해 속도가 느려질 수도 있습니다.

코드를 정확히 사용하는 방법을 설명하지 않은 경우가 있는데, 루프에서 수행하는 대신 최소/최대 계산을 캐시 할 수있는 경우가 있습니다. 예를 들어, 입력 벡터가 거의 변경되지 않으면 매번 다시 계산해야합니다. 그리고 변경 될 때도 periodos 요소를 거치지 않고 최소/최대를 업데이트 할 수 있습니다 (동적 프로그래밍이 도움이 될 수 있음).

이상한 함수 호출 (예 : 반복기 보안 검사)을 확인하기 위해 생성 된 어셈블리를 검사 할 수도 있습니다. 적어도 MSVC 2005/2008에는 릴리스 모드 (기본값은 _SCL_SECURE 매크로 참조)에서 활성화되어 있습니다.

Answer 5

이것은 성능과 관련하여 특정 질문에 대한 답변이 아니므로 가치가 없습니다. 그러나 excludeWrong 비교 함수는 예기치 않은 또는 구현에 따른 결과를 초래할 수 있습니다. 비교 된 첫 번째 값이 -1이면 모든 경우에 대해 min 및 max로 계산 될 수 있습니다. 필자는 gcc v4.0.2와 Microsoft의 컴파일러 v15.00.21022.08을 모두 테스트했습니다.

min: -1 
max: -1 

은 어쩌면이 원하는 결과이지만, 조금 이상한 것 같다

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; 

인쇄 : 예를 들어, 다음과 같습니다.