The World of TomasRan

关注代码中的圈复杂度

知己知彼,国际惯例先定义

定义自然是很重要的,知己知彼,所以游刃有余。

定义:

圈复杂度(Cyclomatic Complexity)是软件测试的一个衡量标准,代表程序中线性独立的路径的个数。

线性独立路径是指程序中至少引进一个新的处理语句集合或一个新条件的任一路径。采用流图的术语,即独立路径必须包含一条在定义路径之前不曾用到的边。

圈复杂度是能够定量进行计算的。我们借助程序控制流程图来分析一下它的计算方法。

image

将一个简单的程序控制流程绘图如上,每一个圆圈代表程序的一个执行步骤,命名为‘节点’(命名是为了方便后面的描述);每一个带方向的箭头表示了该程序的执行路径,命名为‘路径’。可以很清晰地看见程序中存在着循环和分支结构。

那么接下来就是圈复杂度的计算公式:

公式1:V(G) = E - N + 2 * P

E代表控制流程图的路径数量,N代表节点数量,那么P代表的是什么?它指的是程序的构成组件的个数。而从程序的控制流图来看,直接反映是节点互相是连通的流程图的个数(每一个独立的程序都有自己的控制流图,公式1可以用来整体分析多个独立程序或方法的圈复杂度)。上例中各个节点都是相连通的,因此只有一个独立组件。

对单个出入口的程序来说,P值始终为1,因此公式可以简写为:

公式2:V(G) = E - N + 2 (适用于单个出入口情况)

现在介绍另一种情况(做图有王小二过年的气势):

强连通图

对于这样一个强连通的控制流图(强连通图是指有向图中的每一个节点都有至少一个流入和流出,数学形式的定义更为严谨,可以问 度娘),计算它的圈复杂度可以采用公式:

公式3:V(G) = E - N + P

控制流图中增加了一条从终点到起点的路径,整个流图形成了一个闭环。采用公式是很正确的做法,但是如果懒到不想计算的话,对于这个闭环我们还可以采取其他的方法得到它的圈复杂度,那就是数数在这个闭环中有多少不同的线性独立回路,说的通俗易懂点,就是控制流图中循环圈圈的个数(注意:必须是可循环的圈圈,并且不包含子圈)。一个简单的图示:

线性独立图示

公式3还有一个听上去很正式的名字叫做 第一贝蒂数(the first Betti number)

在编程的过程中,通过绘制程序的控制流图来计算圈复杂度,进而将其控制在一个较低水平显然是一件极其麻烦的事儿,这里有更便捷的方法来帮助降低程序圈复杂度,当然,捷径的终点必须和我们想要去的地方一致。Thomas J. McCabe 为我们证明了这一点:

如果一个结构化程序只有一个进入点和一个结束点,那么它的圈复杂度等于程序中决策点(分支、条件循环)的个数加 1。

这给我们的实际指导就是在编码的过程中尽量减少使用循环和分支结构。

这个证明已经被推广到单个进入点,多个结束点的情况:

公式4: V(G) = π - s + 2

π 指的是决策点的个数,s 指的是结束点的个数。

到这里,我们可以得出一个等式:

降低圈复杂度 = 减少分支 + 减少循环

程序判定结构的多少与其复杂度呈正相关,而复杂度的高低和程序的质量呈负相关(判定本身就是一件伤脑经的事儿,至少纯粹是与非的判定中你就要不得不设计两种结果,对于测试来说就要增加测试用例)。我们的目标很明确,减少判定,降低圈复杂度,提高程序质量,坚持“看着舒心,用着放心”的可持续发展道路。

对症下药,如何降低 javascript 中的圈复杂度


上面的定义和分析已经为我们在任何结构化语言的编码过程中减少圈复杂度指定了统一的大政方针:减少分支和循环的使用,那么接下来,我们就需要考虑具体的落实措施了。

  • 变量尽量初始化。减少undefined和null的出现,可以消除部分场景中的分支判断。
  • 使用javascript的对象Object帮助减少分支。javascript对象是一张哈希表,直接寻址寻址速度快,用它来减少分支也能提升代码执行效率。举个锤子:

    if (a === 'dog') {
    ......
    } else if (a === 'cat') {
    ......
    } else if (a === 'mice') {
    ......
    } else if (a === 'duck') {
    ......
    } else if (a === 'pig') {
    ......
    } ...

大量的 if-else 看上去丑陋不说,让代码的圈复杂度一路飙升,那么利用javascript的对象,我们可以这样改善代码:

var animals = {
'dog': function() {},
'cat': function() {},
'mice': function() {},
'duck': function() {},
'pig': function() {},
...
};

animals[a]();

效率提升,圈复杂度减少,不二选择。

  • 当定义的函数包含进行分支判断的参数,思考是否可以将路径的选择提前。简单来说,就是判断是否可以交给它的调用函数来选择,甚至交给用户自己去选择。这适用于一部分场景,举个锤子:比如页面上有几个按钮,现在js的处理逻辑是用户点击不同按钮,在js获取点击事件传递过来的参数后判断用户点击了哪一个,然后执行相应路径代码。现在,为了消除js的这个判断过程,我们可以对于不同的按钮绑定不同的点击事件,这样就可以消除js中关于用户究竟点了哪一个的判断。

很多的javascript代码风格检测工具都可以检测程序的圈复杂度,比如 Code Climate等等,它们会单独检测每个函数的圈复杂度(单个函数的圈复杂度不包含其内部调用函数的圈复杂度)。对于圈复杂度过高的函数定义自然就会对你采取丑拒的姿态,比较非专业的解决方法是将内部判断部分提取出来重新定义函数,这样可以骗过分析器,但是从根本上来讲是投机取巧万万不可取也。最佳途径自然是优化代码,减少分支、循环的数量。

友情推荐,工欲善其事必先利其器

那么,如何去检测javascript代码的圈复杂度呢?画流程图自然不可取,数代码中的循环和分支的个数显然也不是懒惰的程序员喜欢做的(稍微复杂的代码就能让你眼冒金星)。自然去寻找一些好用的工具帮助我们提升效率,这里有两个推荐:

  1. 在线检测网站:JSComplexity
  2. 命令行检测工具:complexity-report