Cyclomatic Complexity

在討論到程式複雜度時, 大家都覺得很抽象, 什麼是程式複雜度?這種東西是可以被計算嗎? 讓我來跟大家介紹介紹.

首先, 想想程式碼裡面有什麼東西. 我想你會說出有if ... then, while, for等控制指令, 以及一堆library供你使用. 因此科學家就想到, 是否可以來看看這些控制指令來決定程式有多複雜呢? 因為你通常用越多if, while 或是for等指令, 通常代表你的程式邏輯越複雜. 因此其中一種程式複雜的的評量方法就產生了.

這個方法是由Thomas J. McCabe, 在1976年提出的, 這裡有他原先投稿的論文, 大家可以欣賞一下. (其實不會太難, 有空真的可以看一下)

http://www.literateprogramming.com/mccabe.pdf

它的想法很簡單, 要算一個程式有多複雜, 只要將if, while, for 和do while出現的次數加1,  這就是代表這個程式的cyclomatic complexity. 即

cyclomatic complexity = P + 1,  P就是分支節點(if, while, for...)的個數

那你會問說為何要加一呢?
你想想每當出現一個分支點, 就會至少有兩種執行路徑 (execution path)要考慮. 例如:

if (a > 0 )
 do TRUE part
else
 do FALSE part

你需要測試 a > 0和 a<= 0這兩條執行路徑. 若是有兩個支點, 就會至少有三種執行路徑 (execution path)要考慮.

這時候你想一下, 這個東西是否和branch coverage的概念有關聯.  如果有N 個分支點, 那就代表至少有 N+ 1的execution path 要測試, 才會滿足100%的branch coverage. 所以你有了cyclomatic complexity的值(N)之後, 你就知道你至少要測N +1 條path才能滿足 all branch coverage. 也就是你至少要有N+1 組test cases, 才能滿足all branch coverage. (因為每條path要一組test case)

看到這裡, 你有沒有覺得發明cyclomatic complexity這傢伙很厲害, 把software mertic 和software testing結合起來, 並且公式又不會太複雜.

其實光是公式不太複雜這點, 就讓他留名千古了. 就像LOC(line of code), 比他複雜, 或是更有道理, 更準確的 metric不是沒有, 但是最後大家都只記得LOC而已

根據SEI的統計資料, cyclomatic complexity的解讀是這樣的
Cyclomatic Complexity     Risk Evaluation
1 to 10                            a simple program, without very much risk
11 to 20                          a more complex program, moderate risk
21 to 50                          a complex, high risk program
> 50                               an un-testable program (very high risk)


Cyclomatic complexity的優點
    * It is very easy to compute as illustrated in the example.
    * Unlike other complex measurements, it can be computed immediately in the development cycle (which makes it agile friendly).
    * It provides a good indicator of the ease of code maintenance.
    * It can help focus testing efforts.
    * It makes it easy to find complex code for formal review.
    
Reference:
1. Cyclomatic Code Complexity Analysis for Microsoft .NET Applications
http://www.codeproject.com/KB/architecture/Cyclomatic_Complexity.aspx

2. WiKi: Cyclomatic complexity
http://en.wikipedia.org/wiki/Cyclomatic_complexity

Note
可能有人會問我說, 你講的公式和McCabe講的不一樣. 它的是V(G) = E- N + 2
V(G): Cyclomatic complexity
E: the number of flow graph edges
N: the number of flow graph nodes
其實這兩個值算出來是一樣的, 只是我講的公式比較好記, 比較直覺. 不過可能在switch case時, 它的公式比較不會搞混.
arrow
arrow
    全站熱搜

    kojenchieh 發表在 痞客邦 留言(2) 人氣()