Microsoft
情報処理技術者試験
CCN

【H30春AP午後】「サイクロマティック複雑度」の計測方法が全くわからなかったので調べてみたら超簡単だった件


はじめに

ナイトの順歴問題に続き、先日の応用情報技術者試験に関する投稿です。

問8の情報システム開発では「プログラムの品質評価」がテーマであり、「サイクロマティック複雑度」という指標を中心に出題されました。

ちょうど「知識ゼロから学ぶソフトウェアテスト【改訂版】」という本を読んでいて「サイクロマチック数」という単語は知っていたので、「見覚えがある!これはいける」と思って臨んだら見事に撃沈しました😂

悔しいし、何より仕事にも活かせそうな内容なので、勉強してやりました。

そしたら意外と簡単だということがわかったので、勉強した範囲で「サイクロマティック複雑度」について紹介します。


注意

公式の問題冊子 がすでに公表されているので、問題を読んでから本記事を読むことをおすすめします。

H30 春 AP 午後 p.40 問8


「サイクロマティック複雑度」とは?

「サイクロマティック複雑度(Cyclomatic complexity)」とは、McCabeによって提唱されたプログラムの複雑さを示す指標です。

「サイクロマチック数」や「循環的複雑度」などとも呼ばれています。

メソッド単位で計測し、高いほどプログラムが複雑ということを示します。

簡単にいえば、ifやfor, switchなどの分岐が多いほど値が高くなります。

CCN(Cyclomatic Complexity Number)と略すことが多いので、本記事でもそのように略すことにします。


CCNが高いとどうなる?


①テストケース数が増える

分岐が多いのでその分テストケース数が増え、作成にも実施にも時間がかかるようになります。


②保守しにくい

分岐が多いと可読性が下がり、可読性が下がると修正時の影響範囲がわかりづらくなって保守がしにくくなります。


CCNの計算方法

APの問題には以下のように記述されていました。


プログラムの制御構造を有向グラフで表したときの、グラフ中のノードの数Nとリンク(辺)の数Lを用いて次の式で算出する。

サイクロマティック複雑度C = L - N + 2

プログラムの制御構造を有向グラフで表した例を図1に示す。プログラムの開始位置と終了位置、反復や条件分岐が開始する位置と終了する位置をノードとし、ノード間をつなぐ順次処理の部分をリンクとしてグラフにする。ノードとの間に含まれる順次処理のプログラムの行数は考慮せず、一つのリンクとして記述する。また、図1のリンク1やリンク4のように、処理がない場合も一つのリンクとして記述する。


複雑度の求め方がすでに複雑 です。

案の上、試験時には正しく計測できませんでした。

図1の例が単純過ぎて、if文のelseがない場合やfor文のような繰り返しがある場合の数え方が全くわかりませんでした。

家に帰って調べようと思ったときに、知識ゼロから学ぶソフトウェアテスト【改訂版】に「Microsoftがソースコードのメトリクス(指標)に使っている」と書かれていたのを思い出しました。

そこでまず「マイクロソフト サイクロマティック複雑度」でググってみると、以下のページがヒットしました。

https://msdn.microsoft.com/ja-jp/library/ms182212.aspx

読み進めていくと、衝撃の事実に辿り着きました。


サイクロマティック複雑度の算出方法

サイクロマティック複雑度は、以下のものに 1 を加算して算出されます。


  • 分岐 ( ifwhile 、および do など) の数


  • switch 内の case ステートメントの数。


…ん?

要は 分岐の数に+1するだけで求められる ということでしょうか?

試しにこの方法でAPの問題のCCNを計測してみます。

図1

分岐:if×1のみ

→CCN:1 + 1 = 2

図2

分岐:if×9, for×1

→CCN:(9 + 1) + 1 = 11

図3

分岐:if×3, for×1

→CCN:(3 + 1) + 1 = 5

全て合っています。

CCNは単純に分岐の数を表している と考えてよさそうです。

elseの有無や入れ子になっているかどうかは関係ないようです。

ただ、使用例のサイクロマティック複雑度3にあるように、分岐がif×1のみでも、判定条件が複数ある場合はその分プラスするようです。

このあたりは勉強中なのでまだわかりません。


CCNの適正値は?

CCNの適正値はいくつなのでしょうか?

低ければ低いほどよさそうですが、全メソッドのCCNが1や2だとメソッド数が増え過ぎてかえって保守しづらそうです。

先ほどのMicrosoftのページには次のように記載されています。


サイクロマティック複雑度が 25 を超えると、この規則違反がレポートされます。


どうやらMicrosoftの規則では、CCNは25以下にするよう定められているようです。

下限については特に記載されていませんでした。

さらにググってみると、以下のページに非常に興味深いことが書いてあります。

https://www.infoq.com/jp/news/2008/04/cyclomaticcomplexity


Enerjyが発見したのは、CCNが1から25のルーチンは、CCNが大きくなるとエラーになる可能性が高くなるという予想される結果にはならないこと である。もっと正確に言うならば、CCNが1から11までについては、CCNが大きくなればなるほど、バグの可能性は低くなるということである。CCNが 25に到達してはじめて、CCNが1のルーチンのエラーの可能性までエラーの可能性が上昇した。


まとめると、 CCNが11のときに不具合の潜在率が最も少なく、25と1が同等で、25を超えるとそれに比例して不具合の潜在率が上がる ということです。


Enerjyによる研究結果によって、CCの数え方に関して多少の混乱が生じた。Keith Braithwaite氏(source)は、Enerjyの研究ではメソッドレベルではなく、ファイルレベルでCCを数えている、と指摘した。


Enerjyという方はメソッド単位でなくファイル単位でCCNを数えていたようです。

こちらの文献にはメソッド単位のCCNについて以下のように記載されています。

https://blog.codecentric.de/en/2011/10/why-good-metrics-values-do-not-equal-good-quality/



  • methods between 1 and 10 are considered simple and easy to understand and test

  • values between 10 and 20 indicate more complex code, which may still be comprehensible; however testing becomes more difficult due to the greater number of possible branches the code can take

  • values of 20 and above are typical of code with a very large number of potential execution paths and can only be fully grasped and tested with great difficulty and effort

  • methods going even higher, e. g. >50, are certainly unmaintainable


簡単に訳すとこのようになります。


  • 1〜10:シンプルで理解しやすく、テストも簡単

  • 10〜20:複雑だけどまだ理解しやすい。テストは難しくなる

  • 20〜:多数の潜在的な処理経路があり、完全に理解してテストするには大きな困難と努力がいる

  • 50〜:確実に保守できない

これらを踏まえて自分なりにまとめると、 メソッド単位のCCNは10以下にするのが望ましく、最低でも25以下に抑える ということです。


CCN計測ツールの紹介

CCNの計測方法と適正値がわかったのはいいのですが、手動で全メソッドのCCNを計測するのは手間がかかります。

そこで、私が知っている2つのCCN計測ツールを簡単に紹介します。


lizard

フリーの計測ツール。コマンドライン。

https://github.com/terryyin/lizard

こちらのツールについては別記事で紹介しているので、そちらをご参照ください。


Understand

有償の計測ツール。おそらくGUI。

https://www.techmatrix.co.jp/product/understand/index.html

サーモグラフィー的な感じで、CCNの高いクラスの色を濃くする図を生成することができます。

CCNの計測以外にも様々なソースコードの解析が行えます。

ただ、私は使ったことがありません。

もし使ったことがある方がいらっしゃいましたら、使い勝手などを教えていただけると嬉しいです。


CCNを下げるには?

CCNを下げる ≒ 分岐を減らす ことだと思うので、パッと2つの方法が思いつきました。


  • ①メソッドを分割し、1メソッドあたりの分岐を少なくする

  • ②早期リターンしてその後の分岐を減らす


おわりに

CCNについていろいろ知ることができました。

まずは開発しているソフトウェアのCCNを計測するところから始め、今後新しくメソッドを実装する際は分岐を増やし過ぎないように心掛けようと思います。


参考リンク