2019年北航OO第1单元(表达式求导)总结

2023-01-05,,,,

2019年北航OO第1单元(表达式求导)总结

1 基于度量的程序结构分析

量化指标及分析

以下是三次作业的量化指标统计:

关于图中指标在这里简要介绍一下:

ev(G):基本复杂度,用来衡量程序非结构化程度。基本复杂度高意味着非结构化程度高,难以模块化和维护。
Iv(G):模块设计复杂度,用来衡量模块判定结构,即模块和其他模块的调用关系。模块设计复杂度高意味模块耦合度高,这将导致模块难于隔离、维护和复用。
v(G):模块判定结构复杂度,数量上表现为独立路径的条数。

从上面三张图可以看出,整体上3个复杂度指标基本都是随着作业进度的推进而逐渐降低。另外,异常值超出正常范围的程度也在逐渐降低。第2次作业中由于需求更加复杂,然而程序结构并没有跟上这种变化,使得其中出现了模块设计复杂度和模块判定结构复杂度高达23的方法。到了第3次作业,虽然也存在一些过于复杂的结构,但是和前两次相比能看出明显的优化。这大致上可以说明第1单元的3次程序设计在向着一个更加合理、结构更加优化、耦合度更低的方向前进。

类图及分析

由于第一次作业我仅构造了一个类,故在下面只放了第2次和第3次作业的类图:

从类图的变化可以明显看出,随着作业进度的推进,程序的结构越来越模块化,程序的逻辑越来越清晰明了。这种变化的趋势也和我自身的感觉很接近。第1次用面向对象的语言写程序时,我还待在“舒适区”里,从思考的方式到具体的实现都是沿袭的C语言和面向过程的思路。

在第2次作业中,我开始尝试将最开始的一个大类分裂为功能更加集中的三个类,并尝试了更多的Java提供的数据结构来帮助对数据进行管理。不过这种分裂还不够彻底。从代码量上来看,Poly类依然占据着整个程序绝大部分的比例。Poly类中的方法也依然很多,相互联系也不够紧密。

经过了前两次的训练,到了第3次作业,我才算是真正地构造出了面向对象的程序结构。每个类内部都很紧凑,类之间的连接逻辑又很简单、很“线性”。具体地,Sin、Power等类是代表一种类型的因子,而Factor接口则是这些因子的一个汇总;Term和Expr分别代表项和表达式,其中Expr既是表达式同时也是表达式因子;最后InputOutput类则是专门负责输入字符串的检查、预处理以及求导后输出字符串的化简。

2 程序bug分析

需要提前指出的一点是,由于高工的OO课程并没有互测环节,因此以下的分析都是基于我自己在调试过程中找到的bug以及未通过公测用例的情况。

2.1 bug的特征与位置

如上文所说,第1次作业的需求很单一,因此程序结构也非常简单,bug并不多,而且即便遇到错误也可以很快地定位到相应的代码。我认为出现问题相对较多的部分是语法分析方法parsePoly()。第一次作业我并没有使用正则表达式来提取输入字符串的信息,而是仿照上学期编译器实现中的自顶向下的语法分析器来进行字符串的解析。这种做法导致的一个问题是方法内的复杂度和体积都非常大,而且逻辑交错,处于一种“非线性”的状态。

我自己找到的bug里占主要部分的就是,忽略了某一语法分支的走向而导致程序进入异常状态。举例来说,由于空白字符的存在,在取下一个字符时会自动跳过它们,但是对于wrong format的输入,程序就可能在判断下一个字符的时候突然发现字符串已经读完了,进而报错。下面所示的是加入“结束判断”后的代码:

while (i < polystr.length && Character.isDigit(getchr(polystr))) {
// blah blah blah
}

第2次作业和第3次作业的程序相近,所以我就在这里一起总结了。

最容易出错的地方,正则表达式(regex)绝对算是其中一个。这类bug的特征是:

分散在各个类中,定位有难度;
纠错手段有限,目前我知道的方法只有“定位到具体regex后用肉眼检查”;

除去手抖打错的情况,其实regex问题归根结底是设计时思考得不够全面,有些情况没有考虑到。我能想到的一种解决方法就是尽可能地缩短每一个regex的长度,再用其他策略把regex结合起来。

此外,在一些条件多且复杂的if-else语句块内也比较容易出现bug,这类bug一般都是typo,但是其产生的原因是设计和架构问题。例如,在第二次作业中的求导函数derivativePoly()中我将三种类型的函数(x, sin, cos)放在了一起进行求导,所以需要判断是否有某一种函数指数为0的情况。这样以来就会出现8种情况需要判断。解决这类问题还是要从源头改变,让这种语句块根本就不出现。

更高层面上,有时对于需求的错误分析会导致程序结构出错。在第3次作业中,需要对表达式(expression)进行分裂,得到项(term)。起初我单纯地认为只需以加减号作为标志分裂即可,后来在公测和自测样例未通过后才想到需要加入“括号深度判断”,并且排除“指数内的符号”和“无符号整数内的符号”这些情况。代码如下所示:

if ((exprArr[i] == '+' || exprArr[i] == '-') && depth == 0 && exprArr[i - 1] != '^' && exprArr[i - 1] != '*') {
splitLoc = i; // split point
break;
}

最后一个bug的来源是对于Java语言的不理解或不熟练,有时会错误理解函数的功能和使用方法。这种bug和程序结构、程序内容关系不大,但我认为仍是一个值得注意的问题。

2.2 bug位置与设计结构之间的相关性

从以上对于bug位置和特征的总结来看,大多数bug都是和设计与结构息息相关的。

一般情况下,bug大多产生在程序结构复杂、逻辑混乱、数据类型繁杂、代码执行上下跳动不可预测的地方。这些部分的代码在某种程度上违背了“线性”的设计原则,使得在写代码时容易写错,在检查代码时也不容易发现问题。更严重地,有时程序结构本身就存在问题,bug只是这类问题的表现形式。比如说,程序可能运行到某些分支但是代码却没有对相应分支进行处理,进而导致进入不可预测的异常状态。

一句话来说,结构设计既有可能是bug的催化剂,也有可能是bug的直接原因。

2.3 从分类树角度分析程序在设计上的问题

分类树是指测试内容依据某些特征进行分类形成的树状层次结构,非叶子结点代表分类条件,叶子结点代表一些相似测试用例的集合。事实上一个程序里类的继承关系和接口关系也可以构成一棵树,而这两棵树之间并不是完全独立的。如果能在设计架构时让程序的类树尽可能地贴近测试内容的分类树,那么不仅程序的结构会很清晰,同时在调试的过程中也更加容易发现bug。我觉得,这种设计方法就算作是Test Driven Development(TDD)的一种应用。

3 发现bug所采用的策略

同样的,由于高工的OO课程并没有互测环节,因此只在这里介绍一下我发现自己程序里bug所采用的策略——静态检查和设计测试样例。

3.1 静态检查

静态检查通过肉眼检查和发现代码中的缺陷,依赖程序员对代码的理解和逻辑推理。我认为静态检查可以分为代码风格检查和代码逻辑检查。代码风格检查旨在发现“高危区域”,像是未初始化的变量、过长的条件判断语句等,都是容易出错的地方,对于这些代码要格外注意,多检查几遍。而代码逻辑检查则是按照代码的执行顺序阅读代码,查看是否有”悬空“的分支或者死循环的分支等等。

3.2 设计测试样例

正如上文2.3节提到的,在设计测试样例是需对于分类树的每个分支均有覆盖,同时还要考虑到不同测试样例组合的情况。以带符号整数为例,不仅需要测试各种符号和整数的组合以及在不同位置插入空格的情况,还要考虑带符号整数出现在指数位置、出现在常量因子位置、出现在sin()/cos()函数内部、出现在表达式内部等等情况。

4 Applying Creational Pattern

其实我个人认为,某种程度上在第3次作业中我已经应用了工厂模式的流程来创建和管理类,尤其是各种因子类。在因子的上一层级的“项(Term)”类的构造方法里,我通过正则表达式来判断某一个因子属于哪种类型,随后创建一个该类型的类。代码如下:

// figure out which factor it is
if (factorList.get(i).startsWith("sin(x)")) {
// class Sin
Factor f = new Sin(factorList.get(i));
factors.add(f);
} else if (factorList.get(i).startsWith("cos(x)")) {
// class Cos
Factor f = new Cos(factorList.get(i));
factors.add(f);
} else if (factorList.get(i).startsWith("sin(")) {
// class SinEmbed
Factor f = newSinEmbed(factorList.get(i));
factors.add(f);
} else if(factorList.get(i).startsWith("cos(")) {
// class CosEmbed
Factor f = newCosEmbed(factorList.get(i));
factors.add(f);
} else if (Pattern./matches/("[+-]?\\d+", factorList.get(i))) {
// class Constant
Factor f = newConstant(factorList.get(i));
factors.add(f);
} else if (Pattern./matches/("x(\\^[+-]?\\d+)?", factorList.get(i))) {
// class Power
Factor f = newPower(factorList.get(i));
factors.add(f);
} else if (Pattern./matches/("\\(.+\\)", factorList.get(i))) {
// class Expr
Factor f = newExpr(factorList.get(i).substring(1, factorList.get(i).length() - 1));
factors.add(f);
} else {
System.out.print("WRONG FORMAT!");
System.exit(0);
}

至于涉及到任意一种因子的求导等计算时,我通过Factor接口来实现这些操作。每个因子类都implements该接口,并分别实现求导函数derivative()和输出函数toStr()的具体实现。这些设计可以高效地分离各部分代码,降低各模块之间的耦合度。

5 Coda

第一次撰写博客,难免会有疏漏之处,还烦请大家指出错误啦。谢谢~

2019年北航OO第1单元(表达式求导)总结的相关教程结束。

《2019年北航OO第1单元(表达式求导)总结.doc》

下载本文的Word格式文档,以方便收藏与打印。