プログラムの複雑さを測る方法～どうやって数値化しよう？～

仕事であれ趣味であれ、プログラマーの方であれば、プログラムの修正作業をすることになってしまうかと思います。最初に考えていた設計をまったく変更せずに済むのが理想的なんですが、そうは問屋が卸さないのがプログラミングの世界です。

そもそもの仕様が変わったり、テストに引っ掛かって作り直す必要が出てきたり、色んな原因で書いてたプログラムを書きなおすという作業が必要になってきます。で、気が付いたらとんでもなく複雑になってて、「いつの間にかパンドラの箱を作っちゃってた…」なんてことがあるかと思います。（僕はしょっちゅうです^^;）

そうならないためには、プログラムの構造をそもそも複雑にしすぎないことが重要だったりします。ただし、その「プログラムの複雑さ」を判断するときに、主観に頼る方も多いかと思います。

適切な判断や改善ができるのであれば、主観に頼っていてもまったく問題はないんですが、人間の主観だけでは信頼に劣ってしまいます。複雑さが適切かどうかを判断するときの材料として使うときには、やっぱり客観的な数値として示したいところ。

というわけで、

「複雑さを客観的な数値として表すにはどうすればいいでしょうか？」

というのが、今回の記事のメインテーマになります。

ちなみにですが、数値化できれば、「複雑さが解消されたプログラム」を定義できたり、プログラムの複雑さを解消するにはどうすればいいのかを明確化できるようになるので、プログラムの改善作業も進めやすくなるかと思います。

リファクタリングをするかどうかの判断基準にするのもアリかもですな。

「複雑さ」という感覚を数値として測る方法
実際問題として便利な複雑度
まとめ

「複雑さ」という感覚を数値として測る方法

さて、いきなり「プログラムの複雑さを数値で表せ」と言われても、戸惑ってしまう方も居るのではないでしょうか？

その原因は、そもそも複雑さをどうやって測ればいいのか分からないって辺りにあるかと思います。プログラムのどんな特徴を測定すればいいのか、どんな単位で測ればいいのかが分からないってことですな。

この問題について、今回はMcCabe氏による1976年の論文『A Complexity Measure』に面白いことが書かれていたので、こちらの論文を紹介していきます。

こちらの論文は、ざっくりと2つのことが書かれていまして、

制御フローグラフにグラフ理論を適用して複雑さを測ろうぜ
その複雑さの原因を整理して考察してみようぜ

っていうような内容になっています。複雑さの測り方だけでなく、その複雑さに関する考察まで推し進めてくれてるのはありがたいっすなぁ。

グラフ理論ってのは数学の一分野で、点と点を線で結んでできた図に関する性質なり、成り立つ定理なりを研究する分野です。

論文の内容ですが、まず複雑さは「サイクロマティック複雑度」という指標を使えば測れるよって話になっていました。「循環的複雑度」と呼ばれたりもします。このサイクロマティック複雑度ですが、分岐数に1を足せば測れます。例えばC言語とかC++言語で言えば、if文の数とか、while文の数なんかを数えることになります。

サイクロマティック複雑度を$ V $、分岐数を$ \pi $とすると、サイクロマティック複雑度の計算式は次のようになります。

$$ サイクロマティック複雑度V = \pi + 1 $$

式にするまでもないくらいに単純な求め方ですが、この式はグラフ理論を使ってサイクロマティック複雑度の定義を式変形していった結果の式になります。なので、上の式はサイクロマティック複雑度の本来の定義ではありません。ただ、実用上はそれで問題ないかと思うので、本来の定義は割愛します。

で、上の定義だけだと分かりづらいかと思うので、次のC++で書かれたプログラムの例を考えてみます。

#include <iostream>

using namespace std;

int main()
{
  int a;

  a = 10;

  cout << "aは" << endl;

  if(a >= 10){
    cout << "10以上" << endl;

    if(a >= 100){
      cout << "100以上" << endl;
    }
    else
    {
      cout << "100未満" << endl;
    }
  }
  else
  {
    cout << "10未満" << endl;
  }

  return 0;
}

この場合、サイクロマティック複雑度は3になります。if文が2つあるので、それに1を足せば、2+1となってサイクロマティック複雑度は3になります。

こうして求められるサイクロマティック複雑度ですが、上の求め方の式を見ても分かるように、分岐数（if文の数）が増えるほど、サイクロマティック複雑度の数値も大きくなっていきます。

ただし、サイクロマティック複雑度は条件分岐の”総数”だけを反映しているので、ネスト数には関係ないという点にはご注意くださいませ～。

条件分岐の数が増えるほどサイクロマティック複雑度も大きくなっていくというのは間違いないことなんですが、一言で「条件分岐」と言っても、その使われ方によって重大な問題になったり、それほど大きな問題にはならなかったりするよーってところまで突き止めてくれているのが、この論文の面白いところです。

実際問題として便利な複雑度

上の節で例として出したプログラムですが、次のような感じでif文のブロックをサブルーチンとしてmain()関数の外に出すことが出来ます。

#include <iostream>

using namespace std;


void judge100(int i)
{
  if(i >= 100){
    cout << "100以上" << endl;
  }
  else
  {
    cout << "100未満" << endl;
  }
}

void judge10(int i)
{
  if(i >= 10){
    cout << "10以上" << endl;

    judge100(i);
  }
  else
  {
    cout << "10未満" << endl;
  }
}

int main()
{
  int a;

  a = 10;

  cout << "aは" << endl;
  judge10(a);

  return 0;
}

こんな感じで、条件分岐の中には、外部に分離できる条件分岐なんてのも存在します。サブルーチン化できるってことですな。

処理を分離できる場合、大本のプログラムの複雑度は小さくなると考えるのが妥当でしょう。というのも、分離元のプログラム（今回はmain()関数）の中での条件分岐は無くなるわけなので。

論文ではその考え方から、サイクロマティック複雑度からサブルーチン化できる処理の個数を引いた「本質的複雑度」という複雑度も提唱されておりました。本質的複雑度をevとして、サブルーチン化できる処理の個数を$ m $とすると、次のような式になります。

$$ 本質的複雑度ev = V – m $$

本質的複雑度が大きすぎると、サイクロマティック複雑度がサブルーチン化できる処理に対して大きすぎるということになります。なので、もしも本質的複雑度が大きすぎたらもっと関数化した方が分かりやすいプログラムになる可能性が高いと言えるでしょうな。