循環的複雑度

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

循環的複雑度: Cyclomatic complexity)とは、ソフトウェア測定法の一種である。Thomas McCabe が開発したもので、プログラムの複雑度を測るのに使われる。プログラムのソースコードから、線形的に独立した経路の数を直接数える。

手法としてではなく、そのコンセプトは文章の可読性(複雑度)を測定する Flesch-Kincaid Readability Test に似ている。

循環的複雑度は、プログラムの制御フローグラフとして描くことで計算される。グラフのノードはプログラムのコマンドに相当する。2つのノードを結ぶ有向エッジは、第一のコマンドを実行後、次に第二のコマンドが実行される可能性があることを示している。

定義[編集]

M = EN + 2P

ここで

M = 循環的複雑度
E = グラフのエッジ数
N = グラフのノード数
P = 連結されたコンポーネントの数

"M" の別の定義として、モジュール(サブルーチンプロシージャ、その他)やシステム全体の制御フローの分岐点数とする場合がある。

個々のサブルーチンは、プログラムの制御フローグラフ上では独立した別々のコンポーネントとして扱われる。

別の定義[編集]

v(G) = en + p
G = プログラムの制御フローグラフ
e = 制御グラフ内のエッジ数
n = 制御グラフ内のノード数
p = 連結されたコンポーネントの数

他の手法[編集]

他にも、循環的複雑度の値を決定する単純な方法がある。制御フローグラフ内の閉じたループの個数を数え、それに 1 を加えた値である。

すなわち、

M = 閉じたループの数 + 1

ここで、

M = 循環的複雑度

ソフトウェアテストにおける意味[編集]

  • M は、制御フローグラフ上でとりうる経路数の下限である。
  • M は、完全な分岐網羅率を達成するのに必要なテストケース数の上限である。

例えば、次のような if-then-else 文が2つ連続しているプログラムを考えてみよう。

if (c1) {
    f1();
} else {
    f2();
}
if (c2) {
    f3();
} else {
    f4();
}
  • 完全な分岐網羅率を達成するには、2個のテストケースで十分である。
  • 完全な経路網羅率を達成するには、4個のテストケースが必要である。
  • 循環的複雑度 M は 3 であり、上記の2つの値の間にある。これはどんなプログラムでも成り立つ。

語源など[編集]

循環的複雑度(Cyclomatic Complexity)という名称は、単にプログラム内のループの個数を数えるものであると誤解されやすい。この名称は、プログラムの制御フローグラフ内の閉じたループの個数に、最終ノードから開始ノードへとエッジを追加することで得られる仮想的なループを加えた値であることから来ている。より実情に近い用語として条件複雑度(Conditional Complexity)がある[1]

主な概念[編集]

ソースコードの一部の循環的複雑度は、ソースコード内の線形独立な経路の数である。実際、if文for文のような分岐点のないソースコードの場合、その複雑度は 1 であり、そのコードには1つの経路しかない。コードに1つのif文が含まれていれば、コードには2つの経路があることになる。つまり、一方はif文での条件が真となる場合の経路で、もう一方はそれが偽となる場合の経路である。

循環的複雑度は、ソースコードの各行をノードとし、実行の流れをノード間の有向エッジで表したグラフを描くことで計算できる。プログラミング言語によっては非常に簡潔でコンパクトであるため、ソースコードの1行がグラフでは複数のノードで表されることもある(例えば、C言語C++C#Javaなどにあるif文を式にしてしまう三項演算子 "?:" )。

一般に、あるモジュールを完全にテストしようとした場合、全ての実行経路を通す必要がある。これの意味するところは、循環的複雑度の大きいモジュールの方が経路数が多く、従ってテストケースも多く必要になるということである。また、複雑度の大きいモジュールは、ソースコードの意味を理解するのに多くの経路を追わなければならず、読解がより困難になる。

また、複雑度の大きいモジュールは凝集度が低いと予想される。この相関を想定する理由は、分岐点(判断ポイント)が多いモジュールは、単一の機能以上のものを詰め込もうとしている可能性が高いためである。しかし、凝集度とは関係なく、モジュールの種類によっては必然的に複雑度が大きくなることもある。例えば、ユーザインタフェース・モジュールに入力データの妥当性確認とエラー復旧のコードが含まれている場合などである。

関連項目[編集]

脚注[編集]

  1. ^ A Complexity Measure - McCabe's original paper (1976)

外部リンク[編集]