軟體複雜度

McCabe複雜度 McCabe複雜度的用途 Design

在硬體的可靠性設計中，有一條基本原則“簡單就是可靠”。這個原則同樣也適合軟體，與功能的增多或增強相伴的是不斷升級與補丁。現在已經有若干種軟體複雜性的度量方法可供參考，其中McCabe QA是比較出色和實用的方法，它能夠計算出多種軟體複雜度，由此可對軟體進行檢查、分析和查明那些可能導致錯誤的代碼。
複雜度
70年代，軟體系統已經變得極其複雜，無論是開發還是維護都是一項成本高昂的工作。人們意識到必須使軟體模組化，以便於開發、測試和維護。為此，成立於1976的McCabe&Associates公司開發出了McCabe Cyclomatic Complexity Metric（圈複雜度）技術對軟體進行結構測試。Metric以軟體複雜度測量的數目為基礎，能幫助工程師識別難於測試和維護的模組，圈複雜度已經成為評估軟體質量的一個重要標準。人們可以用圈複雜度對軟體的複雜度和質量進行衡量，來安排工程進度，在成本、進度和性能之間尋求平衡。
複雜度的種類
有模組、類和程式三類複雜度。模組複雜度包含了關於模組的複雜度信息；類複雜度是針對那些使用McCabe面向對象特性的程式，它包含了關於類的複雜度信息；程式複雜度包含了關於程式的複雜度信息。
集成複雜度報告
對應於三種複雜度的是三種複雜度報告。如果一個報告的複雜度信息不只一種，那么就把這些複雜度信息組合成新的報告。
集成複雜度信息只收集一個部件及其下級的信息。例如：如果一個程式級報告包含一個類複雜度，那么只報告組成程式的類的信息，而不包含類組成的信息。
McCabe複雜度
McCabe複雜度是對軟體結構進行嚴格的算術分析得來的，實質上是對程式拓撲結構複雜性的度量，明確指出了任務複雜部分。McCabe複雜度包括：圈複雜度、基本複雜度、模組設計複雜度、設計複雜度、集成複雜度、行數、規範化複雜度、全局數據複雜度、局部數據複雜度、病態數據複雜度。
McCabe複雜度的用途
在軟體工程中，有三種使用McCabe複雜性度量的方式。
作為測試的輔助工具。McCabe複雜性度量的結果等於通過一個子程式的路徑數，因而需要設計同樣多的測試案例以覆蓋所有的路徑。如果測試案例數小於複雜性數，則有三種情況一是需要更多的測試；二是某些判斷點可以去掉；三是某些判斷點可用插入式代碼替換。
作為程式設計和管理指南。在軟體開發中，需要一種簡單的方式指出可能出問題的子程式。保持子程式簡單的通用方法是設定一個長度限制，例如50行或2頁，但這實際上是在缺乏測試簡明性的有效方法時無可奈何的替代方法。不少人認為McCabe度量就是這樣一種簡明性度量。但是要注意，McCabe度量數大的程式，不見得結構化就不好。例如，Case語句是良結構的，但可能有很大的McCabe度量數（依賴於語句中的分支數），這可能是由於問題和解決方案所固有的複雜性所決定的。使用者應當自己決定如何使用McCabe度量所提供的信息。
作為網路複雜性度量的一種方法。Hall和Preiser提出了一種組合網路複雜性度量，用於度量可能由多個程式設計師組按模組化原理建立的大型軟體系統的複雜性。他們提出的組合度量公式為
式中 C1,...,Ck是各個模組的複雜性；CN是網路複雜性；W1和W2為權值。
McCabe複雜度即可用於度量各個模組的複雜性，也可用於度量網路複雜性。
Cyclomatic Complexity (v(G))圈複雜度
圈複雜度是用來衡量一個模組判定結構的複雜程度，數量上表現為獨立路徑的條數，即合理的預防錯誤所需測試的最少路徑條數，圈複雜度大說明程式代碼可能質量低且難於測試和維護，經驗表明，程式的可能錯誤和高的圈複雜度有著很大關係。
計算方法
節點是程式中代碼的最小單元，邊代表節點間的程式流。如果一個模組流程圖有e條邊n個節點，它的圈複雜度V(G)=e-n+2，典型的V(G)max=10。圖1中示例的圈複雜度是2。
優點
避免軟體中的錯誤傾向；指出極複雜模組，這樣的模組也許可以進一步細化；度量測試計畫，確定測試重點；在開發過程中通過限制程式邏輯，指導測試過程；指出將要測試的區域；幫助測試人員確定測試和維護對象；與所用的高級程式設計語言類型無關。
套用
圈複雜度指出為了確保軟體質量應該檢測的最少基本路徑的數目。在實際中，測試每一條路經是不現實的，測試難度隨著路徑的增加而增加。但測試基本路徑對衡量代碼複雜度的合理性是很必要的。McCabe & Associates建議圈複雜度到10，因為高的圈複雜度使測試變得更加複雜而且增大了軟體錯誤產生的機率。
提示：
圈複雜度度量是測量在一個軟體模組中的分支數目，在所有的開發周期中都要使用。
圈複雜度度量以軟體的結構流程圖為基礎。控制流程圖描述了軟體模組的邏輯結構。一個模組在典型的語言中是一個函式或子程式，有一個入口和一個出口，也可以通過調用/返回機制設計模組。軟體模組的每個執行路徑，都有與從模組的控制流程圖中的入口到出口的節點相符合的路徑。
“Cyclomatic”來源於非直接連線基本測試周期的數目，更重要的是，也通過直接相連的圖表給出獨立路徑的數目。通過圖表的相關性，一個節點可到達另一個節點。
圈複雜度度量也可作為模組基本流程圖路徑的數目，其重點在於模組線形組合後，所產生的路徑數目是最小的。
對圈複雜度的限制
現在有許多好方法可以用來限制圈複雜度。過於複雜的模組容易出錯，難於理解、測試、更正，所以應當在軟體開發的各個階段有意識地限制複雜度，許多開發者已經成功地實現把對軟體複雜度的限制作為軟體項目的一部分，儘管在確切的數目上略微有些爭議。最初支持的數目是10，現在支持數目可達15。但是，只應當在條件較好的情況下使數目大於10，例如開發者非常有經驗，設計合乎正式標準，使用現代化的程式語言、結構程式、代碼預排和先進的測試計畫。換句話說，開發團隊可以選擇超過10的限制數目，但是必須根據經驗進行一些取捨，把精力花在比較複雜的模組上。
Essential Complexity (ev(G))基本複雜度
基本複雜度是用來衡量程式非結構化程度的，非結構成分降低了程式的質量，增加了代碼的維護難度，使程式難於理解。因此，基本複雜度高意味著非結構化程度高，難以模組化和維護。實際上，消除了一個錯誤有時會引起其他的錯誤。
計算方法
將圈複雜度圖中的結構化部分簡化成一個點，計算簡化以後流程圖的圈複雜度就是基本複雜度。
優點
衡量非結構化程度；反映代碼的質量；預測代碼維護量，輔助模組劃分；與所用的高級程式設計語言類型無關。
套用
當基本複雜度為1，這個模組是充分結構化的；當基本複雜度大於1而小於圈複雜度，這個模組是部分結構化的；當基本複雜度等於圈複雜度，這個模組是完全非結構化的。
Module Design Complexity (iv(G))模組設計複雜度
模組設計複雜度是用來衡量模組判定結構，即模組和其他模組的調用關係。軟體模組設計複雜度高意味模組耦合度高，這將導致模組難於隔離、維護和復用。
計算方法
模組設計複雜度是從模組流程圖中移去那些不包含調用子模組的判定和循環結構後得出的圈複雜度，因此模組設計複雜度不能大於圈複雜度，通常是遠小於圈複雜度。
優點
衡量模組對其下層模組的支配作用；衡量一個模組到其子模組進行集成測試的最小數量；定位可能多餘的代碼；以複雜的計算邏輯和設計來區分模組；是設計複雜度（S0）和集成複雜度(S1)計算的基礎；與所用的高級程式設計語言類型無關。
Design Complexity (S0)設計複雜度
設計複雜度以數量來衡量程式模組之間的相互作用關係，它提供了系統級模組設計複雜度的概況，有助於衡量進行自底向上集成測試的效果，而且提供了全面衡量程式設計規格和複雜度的數據，不反映獨立模組的內部情況。高設計複雜度的系統意味著系統各部分之間有著複雜的相互關係，這樣系統將難以維護。
S0是程式中所有模組設計複雜度之和，計算公式如下：
優點
可套用於完整的軟體，也可套用於任何子系統；衡量代碼的質量；指出一個模組整體的複雜度，反映了每個模組和其內部模組的控制關係；揭示了程式中模組調用的複雜度；有助於集成複雜度的計算。
Integration Complexity (S1)集成複雜度
集成複雜度是為了防止錯誤所必須進行的集成測試的數量表示，另一種說法是程式中獨立線性子樹的數目，一棵子樹是一個有返回的調用序列。就像圈複雜度是測試路徑的數目，而集成複雜度是程式或其子系統的獨立線性子樹。
計算方法
一個程式的集成複雜度和一個模組的圈複雜度是非常相似的，必須計算對程式進行完全測試所需集成測試的數目。S1的計算公式：
S1=S0-N+1
N是程式中模組的數目。
優點
有助於集成測試的實施；量化集成測試工作且反映了系統設計複雜度；有助於從整體上隔離系統複雜度。
Number of Lines (nl)行數
行數是模組中總的行數，包括代碼和注釋。
優點：
計算簡單；與所用的高級程式設計語言類型無關；指出了模組的行數（即模組的規模），規模小的模組易於理解和維護。
Normalized Complexity (nv)規範化複雜度
規範化複雜度是圈複雜度除以行數。
計算方法
nv=v(G)/nl
優點
與所用的高級程式設計語言類型無關；定義那些有著顯著判定邏輯密度的模組，這些模組相對於其他常見規範模組需要做更多的維護工作。
Global Data Complexity (gdv(G))全局數據複雜度
全局數據複雜度（需有McCabe Data）量化了模組結構和全局數據變數的關係，它說明了模組對外部數據的依賴程度，同時度量了全局數據的測試工作，也描述了模組之間的耦合關係，能反映潛在的維護問題。
對於如何跟蹤全局數據使用情況的更多信息，可以參考《McCabe Data in Using McCabe IQ Add-Ons》。
Specified Data Complexity (sdv(G))局部數據複雜度
局部數據複雜度（需有McCabe Data）量化了模組結構和用戶局部數據變數的關係，同時度量了局部數據的測試工作。
我們能夠使用McCabe Data的數據字典選擇單獨的數據元素，指出每個數據元素具體的數據類型。局部數據複雜度還提供了其他的數據選擇準則，量化了每個模組中相應數據對模組控制結構的影響。
關於數據字典的更多信息，參考文檔《McCabe Data in Using McCabe IQ Add-Ons.》。
Pathological Complexity (pv(G))病態數據複雜度
病態數據複雜度衡量一個模組包含的完全非結構化成份的程度，標出向循環內部跳入的問題代碼，而這些部分具有最大的風險度，通常需要重新設計。
計算方法
所有的非結構部分除去向循環內跳入的結構，轉化為線結構，病態複雜度就等於簡化以後流程圖的圈複雜度。
優點
與所用的高級程式設計語言類型無關；指出了可靠性的問題，降低了維護風險；幫助識別極不可靠的軟體。
（Halstead 複雜度）
McCabe QA能夠為所選擇的語言產生Halstead Metrics複雜度。Halstead複雜度是以程式中出現的運算符和運算元為計數對象，以它們出現的次數作為計數目標（直接測量指標），然後據以計算出程式容量、工作量。
優點
不要求對程式結構進行深層次分析；能夠預測錯誤率；預測維護工作量；有利於項目規劃，衡量所有程式的複雜度；計算方法簡單；與所用的高級程式設計語言類型無關；眾多研究結構研究表明Halstead複雜度對於預測程式工作計畫和程式的Bug非常有用。
Line Count複雜度描述了Line Count複雜度並列出了它們的優點
Line Count Metrics（Line Count複雜度）
優點
軟體物理規模的度量；定義了具體的Line Count數據，例如注釋行和空行；協助指出難於理解的模組。