eslint 有个圈复杂度底配置,于是就顺便看了看。圈复杂度(Cyclomatic, CC),又称条件复杂度,是一种衡量代码复杂度底标准,其标记为 V(G) 。

相比于认知复杂度,圈复杂度更倾向于用数学模型来构建对代码复杂度底描述。与认知复杂度类似的是,圈复杂度越越高,程序出错底风险也就越大,其缺陷个数也可能越多。圈复杂度的说明程序代码底判断逻辑复杂,可能质量低,且难于测试和维护。

圈复杂度与出错风险

圈复杂度 代码情况 可测性 维护成本
1 ~ 10 清晰
10 ~ 20 复杂
20 ~ 30 非常复杂
> 30 不可读 不可测 非常高

一般来说,圈复杂度大于 10 底方法存在很大的出错风险。

计算方法

任何一个程序都可以被表达为一个流程图,由此我们可以构建出一幅有向图。

1
2
3
4
5
6
7
8
9
+------+ +------+ +-----+
| if | --> | else | --> | end |
+------+ +------+ +-----+
| ^
| |
v |
+------+ |
| then | -------------------+
+------+

圈复杂度底计算公式为: V(G) = E - N + 2 ,其中 E 为边数, N 为节点数。

根据公式,我们可以得知,一个 if else 底圈复杂度为 V(G) = 4 - 4 + 2 = 2 。

我们再计算其他流程底圈复杂度。

1
2
3
+-------+ +-----+
| start | --> | end |
+-------+ +-----+

顺序流程, V(G) = 1 - 2 + 2 = 1 。

1
2
3
4
5
6
7
8
9
+---------+ +-----+
+> | test | --> | end |
| +---------+ +-----+
| |
| |
| v
| +---------+
+- | process |
+---------+

while 循环, V(G) = 3 - 3 + 2 = 2 。

不过这个计算也比较复杂,每次需要画流程图,圈复杂度有个更直观计算方法, V(G) = P + 1 ,其中, P 为被判定的节点数。

常见的被判定节点有:

  • if
  • while
  • for
  • case
  • catch
  • and 和 or 布尔操作
  • 三元操作符

举个例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void sort(int *A)
{
int i = 0;
int n = 5;
int j = 0;
while (i < (n - 1))
{
j = i + 1;
while (j < n)
{
if (A[i] < A[j])
{
swap(A[i], A[j]);
}
}
i = i + 1;
}
}

有两个 while 和一个 if ,因此 V(G) = 2 * 1 + 1 + 1 = 1 。

1
2
3
4
5
6
7
8
9
10
int find (int match)
{
for (int var in list)
{
if (var == match && var != NAN)
{
return var;
}
}
}

有一个 for ,一个 if ,一个 and ,因此 V(G) = 1 + 1 + 1 + 1 = 4 。

圈复杂度与认知复杂度

可以说,在经过简化之后,圈复杂度底计算相比认知复杂度要简单许多,但圈复杂度仍然面临一个问题:圈复杂度高的代码真的代码复杂程度高吗?举个简单的反例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sumOfPrimes(int max) {
int total = 0;
for(int i = 1; i <= max; ++i) {
for (int j = 2; j < i; ++j) {
if (i % j == 0) {
continue;
}
}
total += i;
}
return total;
}
// 代码 1
// V(G) = 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
String getWords(int number) {
switch(number) {
case 1:
return "one";
case 2:
return "two";
case 3:
return "a few";
default:
return "lots";
}
}
// 代码 2
// V(G) = 4

虽然以上两段代码,其圈复杂度相同,显然,代码 2 比代码 1 更易于理解。因此,认知复杂度的提出就是为了解决这个问题。但认知复杂度因此也就放弃圈复杂度简洁的计算模式,使得认知复杂度难于计算,而且认知复杂度也不能说完全解决了这个问题,双方各有优劣。

如何降低圈复杂度

常用的方法有:

  • 简化、合并条件表达式
  • 将条件判定提炼出独立函数
  • 将大函数拆成小函数
  • 以明确函数取代参数
  • 替换算法
  • 逆向表达
  • 移除控制标记
  • 以多态取代条件式
  • 参数化方法

总的来说,降低圈复杂最重要的,不仅仅是缩减代码而将代码变得零碎,最重要的目的,是为了增加代码底自解释性。不然就又会从一个陷阱跳到另一个陷阱中去。但长代码的可读性总是很糟糕的,适当缩略代码是很必要的。