C++性能之戰（6）--優化代碼邏輯

0. 寫在最前面

本文持續更新位址：https://haoqchen.site/2020/07/11/sequence-optimize/

很多人寫代碼很随意，先把功能實作了，等性能不夠再來刻意地優化，但其實很多優秀的習慣能幫助我們一步到位，寫出更高效的代碼。

本文将總結遇到的一些例子，同一個功能，優化一下邏輯，換個寫法性能就有很大提升的。

如果覺得寫得還不錯，可以找我其他文章來看看哦～～～可以的話幫我github點個贊呗。

你的Star是作者堅持下去的最大動力哦～～～

1. 函數放在循環内VS函數放在循環外

例子：判斷一組二維的點中有哪些是滿足一定條件的，比如在一個box内：

以下代碼顯示了關鍵代碼，詳細代碼請參考github sequence_optimize.cpp這個檔案

bool isInBox(const std::pair<int, int>& point, 
             std::pair<int, int> box_pose, std::pair<int, int> box_size)
{
    return ((std::abs(point.first - box_pose.first) < (box_size.first / 2)) 
         && (std::abs(point.second - box_pose.second) < (box_size.second / 2)));
}

void findPointInBox(std::vector<std::pair<int, int>>& src, 
                    std::vector<std::pair<int, int>>& dst, 
                    std::pair<int, int> box_pose, std::pair<int, int> box_size)
{
    for (auto& point : src){
        if ((std::abs(point.first - box_pose.first) < (box_size.first / 2)) 
         && (std::abs(point.second - box_pose.second) < (box_size.second / 2))) {
            dst.push_back(point);
        }
    }
}

// （1）對每個點，調用判斷函數進行判斷
mul.start();
for (auto& point : data){
    if (isInBox(point, std::make_pair<int, int>(500, 1000), std::make_pair<int, int>(600, 600))){
        result.push_back(point);
    }
}
mul.stop();
// （2）将所有點傳到函數中，在函數中循環進行判斷
result.clear();
plus.start();
findPointInBox(data, result, std::make_pair<int, int>(500, 1000), std::make_pair<int, int>(600, 600));
plus.stop();
           

不開啟編譯器優化（或者O1也可以，但O2兩者的時間相差不大，可能是因為判斷的函數太短，使用O2優化個别編譯器會将其内聯），使用以下指令進行編譯：

g++ ./sequence_optimize.cpp -std=c++11 -O0

得到結果如下：

因為調用函數會有很多的花銷，比如将目前狀态壓棧等，甚至比判斷本身都要多，由上面可以看出，将函數放到循環中将會導緻時間增加很多。可以考慮将一些非常耗時的操作放在循環外。

當然，這裡的耗時操作不僅限與函數，還有一些無關緊要的判斷：

bool is_save data = false;

for (auto d : data){
    if (is_save_data){ // 判斷和跳轉本身也會占很多的資源，應盡可能減少
        saveData(d);
    }
}

// VS
if (is_save_data){
    for (auto d : data){
        saveData(d);
    }
}
           

一些常數的計算，比如我第一個例子中的

box_size.first / 2

，就可以将他用一個變量存起來，不用每個循環都進行計算

2. 根據命中成本調整判斷順序

2.1 &&和||運算

根據C++關于邏輯運算的定義，對于内置的

&&

運算和

||

運算，如果第一個值已經能知道結果，将不再判斷第二個值。

Builtin operators && and || perform short-circuit evaluation (do not evaluate the second operand if the result is known after evaluating the first), but overloaded operators behave like regular function calls and always evaluate both operands

是以，将哪個條件放在第一就顯得尤為重要了，考慮下面兩種情況：

if (is_ok || checkData()) // 情況1

if (checkData() || is_ok) // 情況2
           

is_ok

是個bool變量。

• checkData

  是個很複雜的運算，每次需要花費很多的時間，而

  is_ok

  很大機率是true，情況1明顯更大機率可以減少時間。
• 如果

  is_ok

  比較大機率是false，

  checkData

  又很簡單，那麼情況2會更合适。

不要以為一個判斷無關緊要，之前做騰訊的題，就是多一個判斷和少一個判斷決定了能不能AC～～（雖然有了面試機會，最後崗位也不合适，沒影響最終結果）。

2.2 if和else

考慮将機率大的放在前面，這樣能盡量減少跳轉的次數。

3. 通過推導降低複雜度

3.1 邏輯推導

每一個暴力周遊都可以有一個更優的替代方案。

經常刷LeetCode或者企業題庫的同學應該深有體會，暴力搜尋往往是TLE(Time Limit Exceed)的，需要你另謀出路，降低複雜度。

之前刷的兩題就真的深有體會：

• 三根木棒湊三角形問題
• 等差數列偶數被除2删除後的恢複問題

3.2 數學推導

純數學推導往往是不考慮計算成本的，但要代碼實作，就需要一些技巧來重寫公式了：

• 能不能重用一些計算子產品，比如一個複雜的公式有很多

  sin(alpha) * cos(beta)

  ，那我就可以将這個變成一個局部變量來重用了。
• 能否變成遞推的形式，這樣每次更新就可以減少計算量了。
• 能否化簡或者将某些部分變成常量，減少運算

參考

喜歡我的文章的話Star一下呗Star

版權聲明：本文為白夜行的狼原創文章，未經允許不得以任何形式轉載