在循環之前選擇較少或較大運算符的最佳方法

我有兩個包含x，y vales（y = f（x））的數組。我想提供一個函數來查找對應於y的最小或最大采樣值的x的值。在循環之前選擇較少或較大運算符的最佳方法

在循環數組中的值之前，選擇適當的比較運算符的有效方法是什麼？

例如，我想這樣做如下：

double FindExtremum(const double* x, const double* y, 
        const unsigned int n, const bool isMin) { 
    static std::less<double> lt; 
    static std::greater<double> gt; 
    std::binary_function<double,double,bool>& IsBeyond = isMin ? lt : gt; 
    double xm(*x), ym(*y); 
    for (unsigned int i=0; i<n; ++i, ++x, ++y) { 
     if (IsBeyond()(*y,ym)) { 
     ym = *y; 
     xm = *x; 
    } 
    } 
}

不幸的是，基類std::binary_function沒有定義虛擬運營商（）。

像g ++ 4.8這樣的編譯器能夠優化最直接的實現嗎？

double FindExtremum(const double* x, const double* y, 
        const unsigned int n, const bool isMin) { 
    double xm(*x), ym(*y); 
    for (unsigned int i=0; i<n; ++i, ++x, ++y) { 
     if ((isMin && (*y<ym)) || 
      (!isMin && (*y>ym))) { 
     ym = *y; 
     xm = *x; 
    } 
    } 
}

是否有另一種方式來安排的東西，使編譯器優化很容易？有這樣一個衆所周知的算法嗎？

如果可能，我寧願避免使用模板化函數。

來源

2014-02-05 Corey

什麼是'min'在您的兩個例子嗎？ – 0x499602D2

@ 0x499602D2 - 謝謝，將'min'改爲'isMin' – Corey

*我寧願避免使用模板化函數，如果可能的話。 –

您需要將比較函子作爲模板函數參數傳遞，例如，

template <typename Compare> 
double FindExtremum(const double* x, const double* y, 
        const unsigned int n, Compare compare) { 
    double xm(*x), ym(*y); 
    for (unsigned int i=0; i<n; ++i, ++x, ++y) { 
     if (compare(*y,ym)) { 
     ym = *y; 
     xm = *x; 
    } 
    } 
}

然後，如果你需要運行時的選擇，寫這樣的事：

if (isMin) { 
    FindExtremum(x, y, n, std::less<double>()); 
} else { 
    FindExtremum(x, y, n, std::greater<double>()); 
}

避免模板化的功能是不是真的有可能在這種情況下。性能最佳的代碼將直接將比較操作嵌入到循環中，避免函數調用 - 您可以編寫模板或編寫該函數的兩個副本。模板化功能顯然是更好的解決方案。

來源

2014-02-05 23:39:04

這是大多數STL算法實現的方式。 –

爲了達到最終效率，請讓比較運算符或比較運算符選擇一個模板參數，並且不要忘記度量值。

當爭取最大限度的微效率時，進行虛擬呼叫並不符合目標的方向。

這就是說，這是最有可能的過早優化，其高德納正是如此描述的情況：

「過早的優化是所有惡」

的根（I省略他的保留，這聽起來更有力：:-)）

而不是從事微型優化狂潮，哪些收益你幾乎沒有什麼，浪費你的時間，我建議更有成效地嘗試使代碼儘可能清晰和可證實的正確。例如，使用std::vector而不是原始數組和單獨傳遞的大小。並且，例如，不要按照另一個答案中的建議調用布爾比較運算符compare，因爲這是三值比較的常規名稱（例如，在std::string::compare中）。

來源

2014-02-05 23:36:44

這當然是不成熟的優化。 :)我主要想看看是否有一個標準的算法，因爲它似乎是一個必須有很多的情況。 – Corey

@Corey - 是的，它出現了很多。這是泛型編程發明的衆多原因之一。爲什麼你需要一個非模板函數，當這正是醫生的命令？ –

@DavidHammen - 在開頭的問題中看到我上面的評論。主要是因爲我想看看是否有一個我沒有想到的更聰明的解決方案。 :) – Corey

這裏出現了一些問題。首先，我認爲你過於複雜的情況。例如，有兩個函數比較容易，一個計算最小值，另一個計算最大值，然後根據isMin的值調用其中的任意一個。

更多的話，請注意如何在每個迭代你正在做，看看測試是否isMin是真的還是假的，（至少在你看最後「優化」的代碼），而且比較可能已經完成只有一次。

現在，如果isMin可以在編譯時以任何方式推導出來，您可以使用一個模板類來選擇針對該案例優化的正確實現，並且沒有任何運行時間開銷（未經測試，從內存寫入）：

template<bool isMin> 
class ExtremeFinder 
{ 
static float FindExtreme(const double* x, const double* y, 
        const unsigned int n) 
{ 
    // Version that calculates when isMin is false 
} 
}; 

template<> 
class ExtremeFinder<true> 
static float FindExtreme(const double* x, const double* y, 
        const unsigned int n) 
{ 
    // Version that calculates when isMin is true 
} 
};

，並稱呼其爲ExtremeFinder<test_to_know_isMin>::FindExtreme(...);，或者，如果你不能在編譯時決定，你總是可以做：

if (isMin_should_be_true) 
    ExtremeFinder<true>::FindExtreme(...); 
else 
    ExtremeFinder<false>::FindExtreme(...);

來源

2014-02-05 23:40:53

如果你有2級間斷的標準，如<和>=，你可以使用一個bool less函數參數和循環使用XOR：

if (less^(a>=b))

不知道性能，但很容易寫。

或不覆蓋，所有的可能性，間斷<和>：

if ((a!=b) && (less^(a>b))

來源

2014-02-05 23:52:28 mb84

在循環之前選擇較少或較大運算符的最佳方法

回答

相關問題