C++函數max_element＆iterator = 3x較慢

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通過一系列既迭代，整個步驟可以在一個功能中完成。

我相信一些編譯器在其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

這不是對性能的具體問題的答案，所以也許它沒有價值。但似乎比較函數會導致意想不到的或可能實現相關的結果。如果比較的第一個值是-1，那麼它可以計算爲所有情況下的最小值和最大值。我測試了gcc v4.0.2和微軟的編譯器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 

也許這就是理想的結果，但它似乎有點奇怪。