圈复杂度

在学习Jacoco覆盖率的时候，看到一项圈复杂度（Cyclomatic Complexity）的统计维度，对此感到不适很理解，因此在查找文章后，进行对圈复杂度的讲解。

什么是圈复杂度

圈复杂度（Cyclomatic complexity，简写CC）也称为条件复杂度，是一种代码复杂度的衡量标准。由托马斯·J·麦凯布（Thomas J. McCabe, Sr.）于1976年提出，用来表示程序的复杂度，其符号为VG或是M。它可以用来衡量一个模块判定结构的复杂程度，数量上表现为独立现行路径条数，也可理解为覆盖所有的可能情况最少使用的测试用例数。圈复杂度大说明程序代码的判断逻辑复杂，可能质量低且难于测试和 维护。程序的可能错误和高的圈复杂度有着很大关系。

圈复杂度计算方法

点边计算法

计算公式为：

1
V(G) = E - N + 2

其中，E表示控制流图中边的数量，N表示控制流图中节点的数量。

image-20201019134314105

几个节点通过边连接。以下是典型的控制流程，如if-else,while,for,switch-case和正常的流程顺序：

image-20201019134941092

节点判定法

圈复杂度的计算还有更直观的方法，因为圈复杂度所反映的是“判定条件”的数量，所以圈复杂度实际上就是等于判定节点的数量再加上1，也即控制流图的区域数，对应的计算公式为：

1
V(G) = P + 1

其中P为判定节点数，判定节点举例：

  • if语句

  • while语句

  • for语句

  • case语句

  • catch语句

  • and和or布尔操作

  • ?:三元运算符

对于多分支的case结构或if-elseif-else结构，统计判定节点的个数时需要特别注意一点，要求必须统计全部的判定节点数，即每个else if语句，以及每个case语句，都应该算为一个判定节点。

判定节点在模块的控制流图中很容易被识别出来，所以，针对程序的控制流图计算圈复杂度V(G)时，一般采用点边计算法，也即V(G)=e-n+2；而针对模块的控制流图时，可以直接使用统计判定节点数，这样更为简单。

圈复杂度计算实例

实例一

以冒泡排序为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int[] bubbleSort(int[] arr) {
  // 数组的长度
  int l = arr.length;

  // 外层循环是排序的趟数
  for (int i = 0; i < l - 1; i++) { 
    // 内层循环是当前趟数需要⽐较的次数
    for (int j = 0; j < l - i - 1; j++) {
      //前⼀位与后⼀位与前⼀位⽐较，如果前⼀位⽐后⼀位要⼤，那么交换
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr; 
}

根据上面所述的计算方式：

  • 第一种：点边计算法，一个for循环是3个点，代码中有两个for循环，一个if是1个点，因此点数为7，一个for循环的边是4，两个for循环是8，一个if判断边是1，则边的数量是9，带入公式如下：

    1
    V(G) = 9 - 7 + 2 = 4

    点边计算法绘出控制流图：

    image-20201019143748926

  • 第二种：节点判定法，一个for循环一个节点，有两个for循环节点为2，一个if为一个节点，在带入公式如下：

    1
    V(G) = 3 + 1 = 4

从上面两个公式看，发现节点判定法和点边计算法相比起来，节点判定法更容易些。

实例二

代码如下，代码逻辑简单，主要查看if嵌套的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public String demo(int index, String str) {
  String result = null;
  if (index < 0) {
    throw new IndexOutOfBoundsException("exception<0");
  }
  if (index == 1) {
    if (str.length() < 2) {
      return str;
    }
    result = "return str1";
  } else if (index == 2) {
    if (str.length() < 5) {
      return str;
    }
    result = "return str2";
  } else {
    throw new IndexOutOfBoundsException("exception>2");
  }
  return result;
}

控制流程图如下：

image-20201019145756608

还是根据两种公式来计算

  • 第一种：点边计算法，根据上面的流程图，数边边和点点啦，数得的点数是11个（注意：throw、return这样的节点为end节点，因此每种只能记作一个，有4个throw记作1个，有2个return记作1个，因此点数因为8），边得的数是12，带入公式如下：

    1
    V(G) = 12 - 8 + 2 = 6

  • 第二种：节点判定法，这个就根据代码中的判定节点数啦，只需关注 if 、if-else即可，数到的节点为5个，带入公式如下

    1
    V(G) = 5 + 1 = 6

为什么要关注圈复杂度呢？

一般来说圈复杂度大于10的话，就存在很大的出错风险。圈复杂度和缺陷个数有高度的正相关：圈复杂度最高的模块和方法，其缺陷个数也可能最多。因此，在成为缺陷前就要捕获它们。

圈复杂度与软件质量

测试

为测试设计提供很好的参考。一个好的测试用例设计经验是：创建数量与被测试代码圈复杂度值相等的测试用例，以此提升用例对代码的分支覆盖率。

软件质量

圈复杂度 代码状况 可测性 维护成本
1-10 清洗、结构化 高 低
10-20 复杂 中 中
20-30 非常复杂 低 高
>30 不可读 不可测 非常高

圈复杂度与开发

TDD

TDD（测试驱动的开发，test-driven development)和低CC值之间存在着紧密联系。在编写测试时，开发人员会考虑代码的可测试性，倾向于编写简单的代码，因为复杂的代码难以测试。因此TDD的“代码、测试、代码、测试” 循环将导致频繁重构，驱使非复杂代码的开发。

遗留代码（代码优化）

对于遗留代码的维护或重构，测量圈复杂度特别有价值。一般使用圈复杂度作为提升代码质量的切入点。

圈复杂度检测工具

常用工具 说明
Jacoco Java语言，生成的报告有圈复杂度的维度统计，直观查看
checkstyle 配置规则，进行代码的扫描
SonarQube 一个用于代码质量管理的开源平台，支持20多种语言。通过插件机制可集成不同的测试工具，代码分析工具及持续集成工具

以上整理内容来源于以下文章：

http://kaelzhang81.github.io/2017/06/18/详解圈复杂度/

降低圈复杂度的方法

把子程序的一部分提取成另一个子程序，不会降低整个程序的复杂度，只是把决策点移到其他地方，但是这样做可以降低你在同一时间必须关注的复杂度水平。由于重点是要降低你需要在头脑中同时考虑的项目的数量，所以降低一个给定程序的复杂度是有价值的。

img

重新组织函数

  • 提炼函数

    1
    2
    3
    4
    5
    6
    7
    8
    public static void test(int number) {
      if (number < minNumber) {
        number = minNumber;
      }
      for (int i=0;i<number;i++) {
        // some code
      }
    }

    可以替换为以下代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public static void test(int number) {
      number = getMin(number);
      for (int i=0;i<number;i++) {
        // some code
      }
    }

    public static int getMin(int number) {
      if (number < minNumber) {
        return minNumber;
      }
      return number;
    }
  • 替换算法（把复杂算法替换为另一个更清晰的算法）

简化条件表达式

  • 逆向表达（调换条件表达顺序达到简化复杂度）

    1
    2
    3
    4
    5
    if((条件1 && 条件2) || !条件1) {
      return true;
    } else {
      return false;
    }

    变成这样：

    1
    2
    3
    4
    if(条件1 && !条件2) {
      return false;
    }
    return true;

  • 分解条件（对复杂条件表达式（if、else）进行分解并提取成独立函数）

  • 合并条件（将这些判断合并为一个条件式，并提取成独立函数）

  • 移除控制标记（可以使用break和return取代控制标记。）

  • 以多态取代条件式（将整个条件式的每个分支放进一个子类的重载方法中，然后将原始函数声明为抽象方法。由于php是弱类型语言，这里体现的有点模糊）

简化函数调用

  • 参数化方法（建立单一函数，以参数表达那些不同的值）
  • 明确函数取代参数（针对该参数的每一个可能值，建立一个独立函数）