詳解圈複雜度

詳解圈複雜度

圈複雜度概念

圈複雜度（Cyclomatic complexity，簡寫 CC）也稱爲條件複雜度，是一種代碼複雜度的衡量標準。由托馬斯 ·J· 麥凱布（Thomas J. McCabe, Sr.）於 1976 年提出，用來表示程序的複雜度，其符號爲 VG 或是 M。它可以用來衡量一個模塊判定結構的複雜程度，數量上表現爲獨立現行路徑條數，也可理解爲覆蓋所有的可能情況最少使用的測試用例數。圈複雜度大說明程序代碼的判斷邏輯複雜，可能質量低且難於測試和 維護。程序的可能錯誤和高的圈複雜度有着很大關係。

圈複雜度計算方法

點邊計算法

圈複雜度的計算方法很簡單，計算公式爲：

V(G) = E - N + 2

其中，e 表示控制流圖中邊的數量，n 表示控制流圖中節點的數量。

幾個節點通過邊連接。下面是典型的控制流程，如 if-else，While，until 和正常的流程順序：

節點判定法

其實，圈複雜度的計算還有更直觀的方法，因爲圈複雜度所反映的是 “判定條件” 的數量，所以圈複雜度實際上就是等於判定節點的數量再加上 1，也即控制流圖的區域數，對應的計算公式爲：

V (G) = P + 1

其中 P 爲判定節點數，判定節點舉例：

  1. if 語句

  2. while 語句

  3. for 語句

  4. case 語句

  5. catch 語句

  6. and 和 or 布爾操作

  7. ?: 三元運算符

對於多分支的 CASE 結構或 IF-ELSEIF-ELSE 結構，統計判定節點的個數時需要特別注意一點，要求必須統計全部實際的判定節點數，也即每個 ELSEIF 語句，以及每個 CASE 語句，都應該算爲一個判定節點。

判定節點在模塊的控制流圖中很容易被識別出來，所以，針對程序的控制流圖計算圈複雜度 V(G) 時，一般採用點邊計算法，也即 V(G)=e-n+2；而針對模塊的控制流圖時，可以直接使用統計判定節點數，這樣更爲簡單。

圈複雜度計算練習

練習 1：

 1void sort(int * A)
 2{
 3    int i=0;
 4   int n=4;
 5   int j = 0;
 6   while(i < n-1)
 7   {
 8       j = i +1
 9       while(j < n)
10       {
11           if (A[i] < A[j])
12                swap(A[i], A[j]);
13       }
14       i = i + 1
15   }
16}

使用點邊計算法繪出控制流圖：

其圈複雜度爲：V(G) = 9 - 7 + 2 = 4

練習 2：

 1U32 find (string match){
 2         for(auto var : list)
 3         {
 4             if(var == match && from != INVALID_U32) return INVALID_U32;
 5         }
 6         //match step1
 7         if(session == getName() && key == getKey())
 8         {
 9             for (auto& kv : Map)
10             {
11                 if (kv.second == last && match == kv.first)
12                 {
13                     return last;
14                 }
15             }
16
17         }
18         //match step2
19         auto var = Map.find(match);
20         if(var != Map.end()&& (from != var->second)) return var->second;
21
22         //match step3
23         for(auto var: Map)
24         {
25             if((var.first, match) && from != var.second)
26             {
27                 return var.second;
28             }
29         }
30         return INVALID_U32;
31     };

其圈複雜度爲：V(G) = 1(for) + 2(if) + 2(if) + 1(for) + 2(if) + 2(if) + 1(for) + 2(if) + 1= 14

圈複雜度的意義

在缺陷成爲缺陷之前捕獲它們。

圈複雜度與缺陷

一般來說圈複雜度大於 10 的方法存在很大的出錯風險。圈複雜度和缺陷個數有高度的正相關：圈複雜度最高的模塊和方法，其缺陷個數也可能最多。

圈複雜度與結構化測試

此外，它還爲測試設計提供很好的參考。一個好的用例設計經驗是：創建數量與被測代碼圈複雜度值相等的測試用例，以此提升用例對代碼的分支覆蓋率。

圈複雜度與 TDD

TDD（測試驅動的開發，test-driven development) 和低 CC 值之間存在着緊密聯繫。在編寫測試時，開發人員會考慮代碼的可測試性，傾向於編寫簡單的代碼，因爲複雜的代碼難以測試。因此 TDD 的 “代碼、測試、代碼、測試” 循環將導致頻繁重構，驅使非複雜代碼的開發。

圈複雜度與遺留代碼

對於遺留代碼的維護或重構，測量圈複雜度特別有價值。一般使用圈複雜度作爲提升代碼質量的切入點。

圈複雜度與 CI

在持續集成環境中，可以基於時間變化維度來評估模塊或函數的複雜度和增長值。如果 CC 值在不斷增長，那麼應該開展兩項活動：

  1. 確保相關測試的有效性，減少故障風險。

  2. 評估重構必要性和具體方式，以降低出現代碼維護問題的可能性。

圈複雜度和軟件質量

BcUrbN

降低圈複雜度的方法

重新組織你的函數

技巧 1 提煉函數

有一段代碼可以被組織在一起並獨立出來:

 1void Example(int val)
 2{
 3    if( val > MAX_VAL)
 4    {
 5        val = MAX_VAL;
 6    }
 7
 8    for( int i = 0; i < val; i++)
 9    {
10        doSomething(i);
11    }
12}

將這段代碼放進一個獨立函數中，並讓函數名稱解釋該函數的用途:

 1int getValidVal(int val)
 2{
 3       if( val > MAX_VAL)
 4    {
 5        return MAX_VAL;
 6    } 
 7    return val;
 8}
 9
10void doSomethings(int val)
11{
12    for( int i = 0; i < val; i++)
13    {
14        doSomething(i);
15    }
16}
17
18void Example(int val)
19{
20    doSomethings(getValidVal(val));
21}

最後還要重新審視函數內容是否在統一層次上。

技巧 2 替換算法

把某個算法替換爲另一個更清晰的算法：

 1string foundPerson(const vector<string>& peoples){
 2  for (auto& people : peoples) 
 3  {
 4    if (people == "Don"){
 5      return "Don";
 6    }
 7    if (people == "John"){
 8      return "John";
 9    }
10    if (people == "Kent"){
11      return "Kent";
12    }
13  }
14  return "";
15}

將函數實現替換爲另一個算法:

 1string foundPerson(const vector<string>& people){
 2  std::map<string,string>candidates{
 3        { "Don", "Don"},
 4        { "John", "John"},
 5        { "Kent", "Kent"},
 6       };
 7  for (auto& people : peoples) 
 8  {
 9    auto& it = candidates.find(people);
10    if(it != candidates.end())
11        return it->second;
12  }
13}

所謂的表驅動。

簡化條件表達式

技巧 3 逆向表達

在代碼中可能存在條件表達如下：

1if ((condition1() && condition2()) || !condition1())
2{
3    return true;
4}
5else
6{
7    return false;
8}

應用逆向表達調換表達順序後效果如下：

1if(condition1() && !condition2())
2{
3    return false;
4}
5
6return true;

技巧 4 分解條件

在代碼中存在複雜的條件表達：

1if(date.before (SUMMER_START) || date.after(SUMMER_END))
2    charge = quantity * _winterRate + _winterServiceCharge;
3else 
4    charge = quantity * _summerRate;

從 if、then、else 三個段落中分別提煉出獨立函數：

1if(notSummer(date))
2    charge = winterCharge(quantity);
3else 
4    charge = summerCharge (quantity);

技巧 5 合併條件

一系列條件判斷，都得到相同結果:

1double disabilityAmount() 
2{
3    if (_seniority < 2) return 0;
4    if (_monthsDisabled > 12) return 0;
5    if (_isPartTime) return 0;
6    // compute the disability amount
7    ......

將這些判斷合併爲一個條件式，並將這個條件式提煉成爲一個獨立函數:

1double disabilityAmount() 
2{
3    if (isNotEligableForDisability()) return 0;
4    // compute the disability amount
5    ......

技巧 6 移除控制標記

在代碼邏輯中，有時候會使用 bool 類型作爲邏輯控制標記：

 1void checkSecurity(vector<string>& peoples) {
 2    bool found = false;
 3    for (auto& people : peoples) 
 4    {
 5        if (! found) {
 6            if (people == "Don"){
 7                sendAlert();
 8                found = true;
 9            }
10            if (people == "John"){
11                   sendAlert();
12                   found = true;
13            }
14        }
15    }
16}

使用 break 和 return 取代控制標記：

 1void checkSecurity(vector<string>& peoples) {
 2    for (auto& people : peoples)
 3    {     
 4        if (people == "Don" || people == "John")
 5        {
 6            sendAlert();
 7            break;
 8        }
 9    }
10}

技巧 7 以多態取代條件式

條件式根據對象類型的不同而選擇不同的行爲：

 1double getSpeed() 
 2{
 3    switch (_type) {
 4        case EUROPEAN:
 5            return getBaseSpeed();
 6        case AFRICAN:
 7            return getBaseSpeed() - getLoadFactor() *_numberOfCoconuts;
 8        case NORWEGIAN_BLUE:
 9            return (_isNailed) ? 0 : getBaseSpeed(_voltage);
10    }
11    throw new RuntimeException ("Should be unreachable");
12}

將整個條件式的每個分支放進一個子類的重載方法中，然後將原始函數聲明爲抽象方法：

 1class Bird
 2{
 3public:
 4    virtual double getSpeed() = 0;
 5
 6protected:
 7    double getBaseSpeed();
 8}
 9
10class EuropeanBird
11{
12public:
13    double getSpeed()
14    {
15        return getBaseSpeed();
16    }
17}
18
19class AfricanBird
20{
21public:
22    double getSpeed()
23    {
24        return getBaseSpeed() - getLoadFactor() *_numberOfCoconuts;
25    }
26
27private:
28    double getLoadFactor();
29
30    double _numberOfCoconuts;
31}
32
33class NorwegianBlueBird
34{
35public:
36    double getSpeed()
37    {
38        return (_isNailed) ? 0 : getBaseSpeed(_voltage);
39    };
40
41private:
42    bool _isNailed;
43}

簡化函數調用

技巧 8 讀寫分離

某個函數既返回對象狀態值，又修改對象狀態:

1class Customer
2{
3    int getTotalOutstandingAndSetReadyForSummaries(int number);
4}

建立兩個不同的函數，其中一個負責查詢，另一個負責修改:

1class Customer
2{
3    int getTotalOutstanding();
4    void SetReadyForSummaries(int number);
5}

技巧 9 參數化方法

若干函數做了類似的工作，但在函數本體中卻 包含了不同的值:

 1Dollars baseCharge()
 2 {
 3    double result = Math.min(lastUsage(),100) * 0.03;
 4    if (lastUsage() > 100)
 5    {
 6        result += (Math.min (lastUsage(),200) - 100) * 0.05;
 7    }
 8    if (lastUsage() > 200)
 9    {
10        result += (lastUsage() - 200) * 0.07;
11    }
12    return new Dollars (result);
13}
14

建立單一函數，以參數表達那些不同的值：

 1Dollars baseCharge() 
 2{
 3    double result = usageInRange(0, 100) * 0.03;
 4    result += usageInRange (100,200) * 0.05;
 5    result += usageInRange (200, Integer.MAX_VALUE) * 0.07;
 6    return new Dollars (result);
 7}
 8
 9int usageInRange(int start, int end) 
10{
11    if (lastUsage() > start) 
12        return Math.min(lastUsage(),end) -start;
13
14    return 0;
15}

技巧 10 以明確函數取代參數

函數實現完全取決於參數值而採取不同反應：

1void setValue (string name, int value) 
2{
3    if (name == "height")
4        _height = value;
5    else if (name == "width")
6        _width = value;
7    Assert.shouldNeverReachHere();
8}

針對該參數的每一個可能值，建立一個獨立函數：

1void setHeight(int arg) 
2{
3    _height = arg;
4}
5void setWidth (int arg) 
6{
7    _width = arg;
8}

實戰練習

還是以之前統計 CC 值的例子：

 1 U32 find (string match){
 2         for(auto var : List)
 3         {
 4             if(var == match && from != INVALID_U32) 
 5            return INVALID_U32;
 6         }
 7         //match step1
 8         if(session == getName() && key == getKey())
 9         {
10             for (auto& kv : Map)
11             {
12                 if (kv.second == last && match == kv.first)
13                 {
14                     return last;
15                 }
16             }
17
18         }
19         //match step2
20         auto var = Map.find(match);
21         if(var != Map.end()&& (from != var->second)) return var->second;
22
23         //match step3
24         for(auto var: Map)
25         {
26             if((var.first, match) && from != var.second)
27             {
28                 return var.second;
29             }
30         }
31         return INVALID_U32;
32     };

綜合運用降低 CC 值的技巧後：

  1namespace
  2{
  3    struct Matcher
  4    {
  5        Matcher(string name, string key);
  6        U32 find();
  7
  8    private:
  9        bool except();
 10        U32 matchStep1();
 11        U32 matchStep2();
 12        U32 matchStep3();
 13
 14        bool isTheSameMatch();
 15
 16        string match;
 17        U32 from;
 18    };
 19
 20    Matcher::Matcher(string name, string key):
 21        match(name + key)
 22    {
 23        from = GetFrom();
 24    }
 25
 26    U32 Matcher::find()
 27    {
 28        if (except())
 29            return INVALID_U32;
 30
 31        auto result = matchStep1();
 32        if (result != INVALID_U32)
 33            return result;
 34
 35        result = matchStep2();
 36        if (result != INVALID_U32)
 37            return result;
 38
 39        return matchStep3();
 40    }
 41
 42    bool Matcher::except()
 43    {
 44        for(auto var : List)
 45        {
 46            if(var == match && from != INVALID_U32)
 47                return true;
 48        }
 49
 50        return false;
 51    }
 52
 53    U32 Matcher::matchStep1()
 54    {
 55        if(!isTheSameMatch())
 56        {
 57            return INVALID_U32;
 58        }
 59
 60        for (auto& kv : Map)
 61        {
 62            if ( last == kv.second && match == kv.first)
 63            {
 64                return last;
 65            }
 66        }
 67
 68        return INVALID_U32;
 69    }
 70
 71    bool Matcher::isTheSameMatch()
 72    {
 73        return match == getName() + getKey();
 74    }
 75
 76    U32 Matcher::matchStep2()
 77    {
 78        auto var = Map.find(match);
 79        if(var != Map.end()&& (from != var->second))
 80        {
 81            return var->second;
 82        }
 83
 84        return INVALID_U32;
 85    }
 86
 87    U32 Matcher::matchStep3()
 88    {
 89        for(auto var: Map)
 90        {
 91            if(keyMatch(var.first, match) && from != var.second)
 92            {
 93                return var.second;
 94            }
 95        }
 96
 97        return INVALID_U32;
 98    }
 99}
100
101U32 find (string match)
102{
103    Matcher matcher;
104
105    return matcher.find(match);
106}
107

該例子將匹配算法都封裝到 Matcher 類中，並將原有邏輯通過提煉函數（技巧 1）和合並條件（技巧 6）將匹配邏輯抽象成能力查詢、粘滯、精確匹配及模糊匹配四個步驟，這樣將循環和條件分支封入小函數中，從而降低接口函數（findPno）的圈複雜度，函數職責也更加單一和清晰。整體圈複雜度從單個函數的 14 降到多個函數最高的 5。

圈複雜度思辨

思辨 1 高複雜度的代碼是否可維護性差

在實際項目中爲了調試方便，經常會把消息號對應的名稱打印出來：

 1string getMessageName(Message msg)
 2{
 3    switch(msg)
 4    {
 5        case MSG_1:
 6            return "MSG_1";
 7        case MSG_2:
 8            return "MSG_2";
 9        case MSG_3:
10            return "MSG_3";
11        case MSG_4:
12            return "MSG_4";
13        case MSG_5:
14            return "MSG_5";
15        case MSG_6:
16            return "MSG_6";
17        case MSG_7:
18            return "MSG_7";
19        case MSG_8:
20            return "MSG_8";
21        default:
22            return "MSG_UNKNOWN"
23    }
24}

這段代碼無論從可讀性來說，還是從可維護性來說都是可以接收的。因此，當因爲” 高” 複雜度就進行重構的話（例如：技巧 2 或技巧 6），在降低圈複雜度的同時會帶來不必要的邏輯複雜度。

當然，如果出現下面的情況的話，還是有必要進一步降低圈複雜度的：

  1. 消息數過多。

  2. switch…case… 多處重複。對於消息過多的情況，可以考慮將消息進行分類，然後採用技巧 1 進行重構。對於出現多處重複的情況，可以通過技巧 6 將同樣 case 的內容內聚到一個具體的類的方法中，然後通過多態的方式來使用。

思辨 2 複雜度相同的代碼是否是一致的

例如下面兩個代碼片段的圈複雜度都是 6。代碼片段 1：

 1string getWeight(int i) {
 2        if (i <= 0) 
 3        {
 4                return "no weight";
 5        }
 6        if (i < 10) 
 7        {
 8                return "light";
 9        }
10        if (i < 20) 
11        {
12                return "medium";
13        }
14        if (i < 30) 
15        {
16                return "heavy";
17        }
18        if (i < 40)
19        {
20            return "very heavy";
21        }
22
23        return "super heavy"
24}

代碼片段 2

 1int sumOfNonPrimes(int limit) {
 2        bool bAdd = false;
 3        int sum = 0;
 4        for (int i = 0; i < limit; ++i) {
 5                if (i <= 2) 
 6                    continue;
 7
 8                for (int j = 2; j < i; ++j) 
 9                {
10                    if (i % j == 0) 
11                    {
12                            bAdd = false;
13                            break;
14                    }
15                    bAdd = true;
16                }
17                if (bAdd)
18                    sum += i;
19        }
20        return sum;
21}

但是它們的代碼無論從可讀性上來說，還是從可維護性來說，代碼片段 1 應該都優於代碼片段 2，代碼片段 2 的壞味道更加濃郁。因此，圈複雜度還需要具體情況具體分析，其只能作爲重構的一個度量指標，作爲決策的一個參考依據。

圈複雜度工具

圈複雜度的工具有很多，大致有三類：

uzdUYH

source: //kaelzhang81.github.io/2017/06/18 / 詳解圈複雜度

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/o05LuZB3DTXGrmQeQJxBEw

猜你喜歡