oo课程的第一单元结束了,第一单元,以多项式求导程序为中心,不断增加新的功能,我学到了很多:
因为下面要用到复杂度分析,所以先在此给出一些相关概念。
我们需要使用的主要是方法和类的复杂度分析。
方法的复杂度分析主要基于循环复杂度的计算。循环复杂度是一种表示程序复杂度的软件度量,由程序流程图中的“基础路径”数量得来。
ev(g):即essentail complexity,用来表示一个方法的结构化程度,范围在[1,v(g)]之间,值越大则程序的结构越“病态”,其计算过程和图的“缩点”有关。
iv(g):即design complexity,用来表示一个方法和他所调用的其他方法的紧密程度,范围也在[1,v(g)]之间,值越大联系越紧密。
v(g):即循环复杂度,可以理解为穷尽程序流程每一条路径所需要的试验次数。
对于类,有ocavg和wmc两个项目,分别代表类的方法的平均循环复杂度和总循环复杂度。
下面我将从程序结构,公测、互测以及bug分析几个方面来总结我第一单元的三次作业。
实现简单多项式的格式判断和求导,其中多项式由项相加减组成,项是幂函数或带符号整数。
读入时用arraylist存储多项式的每一项,用公式求导后输出。
第一次作业代码规模如下图。
第一次作业类图如下,其中main是主类,polylist是多项式类,polynode是多项式项类。
第一次作业的复杂度分析如下。
可以看出polylist的构造方法和print方法的复杂度很高,因为这两个方法有一个共同点,就是用了很复杂的if/else条件判断语句。
而polylist的构造方法条件语句复杂,是对正则表达式应用不熟练导致。
笔者的程序在公测中没有出现正确性错误,但是由于优化输出的时候忘记-1*x中的1可以省略,导致一个点性能分不满。
笔者的程序在互测中被发现一个bug,原因是笔者在做输出优化时,只考虑了最后只剩一个系数为0的项,如果出现类似0*x^3+0*x^4,这种两个系数为0的项,就会没有输出。
笔者在互测中,hack了其他人17次,大部分都是正则表达式的错误使用导致的,主要表现在对输入各种情况考虑不周全。
实现简单多项式的格式判断和求导,其中多项式由项相加减组成,项是由因子相乘组成,因子包括sin(x),cos(x),幂函数,带符号整数。
存储多项式:采用hashmap,其中key采用三元组(x的指数,sin(x)的指数,cos(x)的指数),value存放每一项的系数。
化简:dfs + 三角函数性质化简。
第二次作业的代码规模如下图。
第二次作业类图如下,其中polylist存储多项式,itemdegs为自定义的三元组的key。
第二次作业的复杂度分析如下。
其中几个方法复杂度稍高,下面给出分析:
笔者的程序在公测中,未出现正确性错误,但由于只进行了三角函数合并,未进行贪心拆项优化,故性能分未能拿到满分。
笔者的程序在互测中被发现4个bug,主要来源于几个方面:
笔者在本次互测时未发现他人bug,主要是因为对拍器出了问题(捂脸),sympy的equals方法有时候不能正确判断表达式的等价性,因此在第三次作业笔者重写了对拍器,代值进行计算来判断正确与否。
实现简单多项式的格式判断和求导。其中多项式由项相加减组成,项是由因子相乘组成,因子包括幂函数,带符号整数,三角函数,表达式因子,其中表达式因子为一个表达式外面加括号,三角函数可以嵌套因子。
第三次作业的代码规模如下图。
第三次作业类图如下,其中poly是表达式类,item是表达式项类,calculatetree是表达式树类,node是表达式树节点类。
第三次作业的复杂度分析如下。
对于其中几个比较复杂的方法,分析如下:
结合三次作业的复杂度分析,仔细思考了可能的解决方法:
笔者的程序在公测中未出现正确性错误,但是也没有拿到性能分,原因可能是:
对多余括号的去除还没有做的很好,只是做了简单的优化。
公测数据都是精心构造,这样做过精心优化的同学能得到更短的输出。
笔者的程序在互测中没有被发现bug
笔者发现其他人3个bug,分别是:
而其中前两个bug是笔者用手动造的测试集发现的,这也说明了自动数据生成有时候并不好用,手动造的数据才更具有针对性。
由于第三次代码较为复杂,所以采取完全黑箱测试,采用随机数生成带n层嵌套的项,并结合第二次作业的生成器,生成表达式。正确性验证是模拟评测机,采用sympy带入100个数计算,wrong format判定采用python的异常处理机制。
在第一单元的学习中,自我感觉对继承和接口方面的知识,以及对工厂模式还没有完全掌握,所以第三次作业没使用工厂模式。利用这周闲暇时间,又仔细研究了一下,感受到了工厂模式+借口的方便和强大。在之后的多线程学习中,进一步深化自己面向对象设计模式是必须的。
如对本文有疑问, 点击进行留言回复!!
详解SpringBoot修改启动端口server.port的四种方式
网友评论