2020 OO 第一单元总结 表达式求导

title: BUAA-OO 第一单元总结
date: 2020-03-19 20:53:41
tags: OO
categories: 学习

OO第一单元通过三次递进式的作业让我们实现表达式求导,在这几次作业中我也有很多收获。下面就回顾一下前三次作业中存在的问题。

在个人看来,表达式求导的难点主要有三部分——对输入的处理、表达式的存储结构以及化简。这三次作业我所采用的表达式存储结构都不相同,不过重构的速度还是比较快的(安慰自己)。

第一次作业

在第一次作业中,我的程序总体架构为提取幂函数为Poly对象,建立Polynomial类解析表达式创建幂函数对象,在主类Derivative中进行部分性能优化工作。

① 程序结构分析

UML类图:

2020 OO 第一单元总结 表达式求导

2020 OO 第一单元总结 表达式求导

第一次作业的幂函数因子较为简单,代码中仅提炼出Poly对象,并在其内部实现求导方法。

Method复杂度:

Method ev(G) iv(G) v(G)
Derivative.main(String[]) 1 1 1
Derivative.printAnswer(HashMap<BigInteger, Poly>) 4 5 7
Poly.Poly(BigInteger,BigInteger) 1 1 1
Poly.addCoef(BigInteger) 1 1 1
Poly.compareTo(Object) 1 1 1
Poly.derivative() 1 2 2
Poly.equals(Object) 2 2 2
Poly.getCoeff() 1 1 1
Poly.getIndex() 1 1 1
Poly.hashCode() 1 1 1
Poly.toString() 1 11 12
Polynomial.Polynomial(String) 1 1 1
Polynomial.getPolyitem() 1 2 2
Polynomial.getfirstitem() 1 9 10

第一次作业中,化简主要在主类Derivative的printAnswer()方法(将第一个正项优先输出)和Poly类的toString()方法中,printAnswer()涉及对表达式的遍历,基本复杂性高;toString()则包含大量条件语句,多次调用了BigInteger中的方法,循环依赖性高。而表达式解析我采用的是正则+状态机的策略(这个策略三次作业均沿用,感觉还是很舒服的),在getfirstitem()中处理不同类型输入并归一化,代码较为复杂。

② 程序Bug分析

第一次作业在强测、互测中均未出现Bug。

③ 互测采用策略

互测时我采用的策略是“补刀”。我先是用简单的自动测试程序跑了下房间内成员的代码,不过貌似没有出现问题;然而圣杯战争发生了转机——Rider竟然拿下了一血!

于是我一一检查其他成员的代码,发现Berserker的正则存在问题:在正则中匹配的是“[+|-]{0,2}(\\d*.)?x(..[+|-]?\\d+)?”,其中的“.”可匹配任意字符,就会错误解析表达式。

第一次互测时认真读了屋内其他同学的代码,感觉还是很有收获的。之后两次大部分都读不下去,可读性实在是让人肝疼……放到评测姬里自生自灭吧!另外这次互测也让我意识到了高工同学的可怕之处(误),全屋子就这一个Bug,大佬换着花样hack……卷卷更健康。

④ 对象创建模式

在第一次作业中,我并没有应用对象创建模式,表达式解析就顺便new了新因子,Polynomial类的紧耦合比较严重。

第二次作业

第二次作业增加了三角函数因子,这个时候我也偷偷看了一下去年的第三次作业题目,新增加的嵌套对于表达式的化简无疑是不小的挑战。所以在规划第二次作业的总体架构时,我就面临着一个选择——是要建立终将在第三次作业重构的四元组项;还是要采用“表达式-项-因子”三层结构,为第三次作业留好迭代的空间?

经过一番挣扎(其实并没有,因为我还不会写三层结构),我选择了势必带来重构的四元组形式,也就是将表达式的每一项以“coeff*x**powindex*sin(x)**sinindex*cos(x)**cosindex”的形式存储,这样处理方式就和第一次作业基本一致。在基本架构沿用第一次作业的情况下,第二次作业给我最大的挑战反而是三角函数的化简,我的化简类Simplify的行数是最多的。

2020 OO 第一单元总结 表达式求导

① 程序结构分析

UML类图

2020 OO 第一单元总结 表达式求导

2020 OO 第一单元总结 表达式求导

架构基本沿用第一次作业,UML也差不多,不过这次的简化更复杂一些。

Method复杂度:

Method ev(G) iv(G) v(G)
DeriPrinter.DeriPrinter(HashMap<String, MutiItem>) 1 7 7
DeriPrinter.getAnswer(HashMap<String, MutiItem>) 4 5 7
DeriPrinter.printAnswer() 1 2 2
Item.Item(BigInteger,BigInteger,BigInteger) 1 1 1
Item.compareTo(Object) 3 3 3
Item.equals(Object) 2 4 4
Item.getCosin() 1 1 1
Item.getPowin() 1 1 1
Item.getSinin() 1 1 1
Item.hashCode() 1 1 1
Item.toString() 1 5 8
MainClass.main(String[]) 1 1 1
MutiItem.MutiItem(BigInteger,BigInteger,BigInteger,BigInteger) 1 1 1
MutiItem.MutiItem(BigInteger,Item) 1 1 1
MutiItem.addCoeff(BigInteger) 1 1 1
MutiItem.compareTo(Object) 1 1 1
MutiItem.derivate() 1 5 5
MutiItem.equals(Object) 2 2 2
MutiItem.getCoeff() 1 1 1
MutiItem.getCosin() 1 1 1
MutiItem.getIdentity() 1 1 1
MutiItem.getItem() 1 1 1
MutiItem.getPowin() 1 1 1
MutiItem.getSinin() 1 1 1
MutiItem.hashCode() 1 1 1
MutiItem.toString() 1 5 5
ParseExp.MutiItemSign() 2 3 4
ParseExp.ParseExp(String) 1 5 6
ParseExp.WrongFormat(String) 1 1 1
ParseExp.getExpression() 1 2 2
ParseExp.getFirstitem() 3 13 14
Simplify.Simplify(HashMap<String, MutiItem>) 1 2 2
Simplify.exitmatch(BigInteger,Item,Item,Item,HashMap<Item, BigInteger>) 2 3 4
Simplify.searchcos(HashMap<Item, BigInteger>) 4 6 9
Simplify.simplify() 1 3 4

由于一开始并没有明确的化简思路,在第一遍实现了基本求导功能的代码通过中测之后,我为了实现化简功能,又对代码内类的结构做了很多修改,在这一过程中,尽管我确实用类将表达式中的Item与MulItem做了封装,但我却胡乱修改内部方法,这并不符合面向对象的思想,也导致最后代码可读性极差,也为互测时被发现的Bug埋下了祸根。具体表现到MetricReloaded的分析上,就是ParseExp类的getFirstitem()依然是复杂度重灾区,没有采用工厂模式也使得它与其他类的依赖极为严重,优化输出的内容依然有很高的基本复杂性。

② 程序Bug分析

强测中获得性能分为16.545/20,在处理表达式化简时,我所采用的是暴力搜索的方式,每次搜索到可以合并的项就将其合并,然后进行重新搜索。

这种方法显然只能找到一个极优解,却不能找到最优解,表达式项存储顺序对结果也有很大影响。一种更加可行的方式是采用深度优先搜索,不过当时并没有想出具体的实现方法,只好作罢。

互测时被找出来一个Bug,同时发现Berserker的一个Bug(狂战士日常躺枪)。而我的Bug是HashMap的Key写错,在生成MulItem的Key时,我采用的是将指数拼接为String的方式,在指数较大时,可能会导致不同项被当作同一项存入HashMap中,造成求导错误。

修改也很简单,只需要在生成String的时候给不同指数加个分隔符就好了——

 public MutiItem(BigInteger a, BigInteger b, BigInteger c, BigInteger d) {
     this.coeff = a;
     this.item = new Item(b, c, d);
     // before: identity = "" + b + c + d;
     identity = "" + b + "." + c + "." + d;
 }

可以发现这里我的MutiItem的构造方法是非常混乱的,不过没有发现这么明显的Bug,一方面就是混乱的优化带来的副作用;另一方面也是因为这样的数据出现几率确实很小,同屋里也只有一个同学发现了这个Bug(我后来和hack我的同学交流了下,果然是长时间跑随机自动测试程序才找到的……)

③ 互测采用策略

在这次互测是采用对拍+手动构造样例+Python生成随机数据自动评测的方式。屋内除我只有一个Bug,大家很快找到之后也比较佛系。

互测中阅读了同屋子大佬处理简化的DFS,确实厉害;另外还拜读了另一个房间Alterego的架构,类似Sympy的表达式结构简直叫人拍案叫绝,计算方式优美,让我看到了什么是真正的封装、多态、继承,也有更多信心去面对第三次作业。(不过听说在那个屋Alterego被hack的很惨,悲)

④ 对象创建模式

在第二次作业中,由于使用的是和第一次作业类似的四元组项,我依然没有应用对象创建模式,表达式解析里又new了新因子,紧耦合依然严重。这在第三次作业中有一定改善。

第三次作业

前两次作业都没有对表达式进行结构化处理,导致了第三次作业表达式的存储结构必须大改。

好在表达式求导的三大难点——对输入的处理、表达式的存储结构以及化简,这次都处理得比较好——

  • 对输入的处理上,有了前两次作业中采用的正则表达式加有限状态机读入的经验,修改很快;

  • 表达式的存储结构上吸取了Alterego的架构(感谢Alterego!!!!),在进行重构的时候思路比较清晰,避免了第二次作业惨剧的重演;

  • 化简上,层次化的表达式存储方式发挥出了它的优越性,通过统一的接口进行因子类型的转换,效果好;

在第三次作业我也首次采用了Package来管理类,也是一个小进步。

① 程序结构分析

UML类图:2020 OO 第一单元总结 表达式求导

表达式解析为ItemAdd和ItemMul两层(内部有大量简化方法),以及因子,都实现了求导接口,以抽象类约束。

2020 OO 第一单元总结 表达式求导

这一次的类图很乱,主要原因还是在于表达式也可以作为一个因子嵌套进三角函数中,类之间的相互调用也比较明显。

Method复杂度:

Method ev(G) iv(G) v(G)
homework.MainClass.main(String[]) 1 2 2
homework.expression.ExpFunction.Exception.Exception(String) 1 1 1
homework.expression.ExpFunction.deleteSpace(String) 3 7 10
homework.expression.ExpFunction.matchParentheses(String,int) 6 6 7
homework.expression.ExpFunction.readIndex(String) 2 1 2
homework.expression.ExpFunction.simplifyExpParentheses(String) 9 11 14
homework.expression.ExpFunction.simplifyParentheses(String,int[]) 1 1 8
homework.expression.ExpFunction.simplifySign(String) 4 3 4
homework.expression.ExpParser.Exception.Exception(String) 1 1 1
homework.expression.ExpParser.ExpParser(String) 3 2 3
homework.expression.ExpParser.getItemAdd(String,boolean) 5 6 9
homework.expression.ExpParser.getItemMul(String) 4 3 5
homework.expression.ExpParser.matchParentheses() 7 4 8
homework.expression.ExpParser.readOneItem(String) 6 9 12
homework.expression.ExpParser.spliter() 1 1 1
homework.expression.ExpSimplify.ExpSimplify(Derivable) 1 2 2
homework.expression.ExpSimplify.OnlyOneDiff(Derivable,Derivable) 9 17 26
homework.expression.ExpSimplify.getDiff(boolean,int,int,ItemMul,ItemMul) 1 4 6
homework.expression.ExpSimplify.searchSimplify(ItemAdd) 4 4 4
homework.expression.ExpSimplify.simplify() 2 2 4
homework.polyitem.factor.Factor.Factor() 1 1 1
homework.polyitem.factor.Factor.Factor(BigInteger) 1 1 1
homework.polyitem.factor.Factor.getIndex() 1 1 1
homework.polyitem.factor.Factor.setIndex(BigInteger) 1 1 1
homework.polyitem.factor.Factor.updateIndex(BigInteger) 1 1 1
homework.polyitem.factor.FactorExp.FactorExp() 1 1 1
homework.polyitem.factor.FactorExp.FactorExp(ItemAdd) 1 1 1
homework.polyitem.factor.FactorExp.FactorExp(ItemAdd,BigInteger) 1 1 1
homework.polyitem.factor.FactorExp.clone() 1 1 1
homework.polyitem.factor.FactorExp.derivate() 4 4 5
homework.polyitem.factor.FactorExp.equals(Object) 3 3 4
homework.polyitem.factor.FactorExp.equalsZero() 1 1 1
homework.polyitem.factor.FactorExp.getExpression() 1 1 1
homework.polyitem.factor.FactorExp.identity() 1 1 1
homework.polyitem.factor.FactorExp.toString() 1 4 4
homework.polyitem.factor.FactorFactory.readPower(Matcher) 1 2 2
homework.polyitem.factor.FactorFactory.readTrian(Matcher) 1 2 3
homework.polyitem.factor.FactorFactory.simplifyFunc(Derivable) 2 4 5
homework.polyitem.factor.FuncConst.FuncConst() 1 1 1
homework.polyitem.factor.FuncConst.FuncConst(BigInteger) 1 1 1
homework.polyitem.factor.FuncConst.FuncConst(String) 1 1 1
homework.polyitem.factor.FuncConst.clone() 1 1 1
homework.polyitem.factor.FuncConst.derivate() 1 1 1
homework.polyitem.factor.FuncConst.equals(Object) 2 2 2
homework.polyitem.factor.FuncConst.equalsOne() 1 1 1
homework.polyitem.factor.FuncConst.equalsZero() 1 1 1
homework.polyitem.factor.FuncConst.getValue() 1 1 1
homework.polyitem.factor.FuncConst.identity() 1 1 1
homework.polyitem.factor.FuncConst.setValue(BigInteger) 1 1 1
homework.polyitem.factor.FuncConst.toString() 1 1 1
homework.polyitem.factor.FuncConst.updateValue(BigInteger) 1 1 1
homework.polyitem.factor.FuncPower.FuncPower() 1 1 1
homework.polyitem.factor.FuncPower.FuncPower(BigInteger) 1 1 1
homework.polyitem.factor.FuncPower.clone() 1 1 1
homework.polyitem.factor.FuncPower.derivate() 1 1 2
homework.polyitem.factor.FuncPower.equals(Object) 2 2 2
homework.polyitem.factor.FuncPower.equalsZero() 1 1 1
homework.polyitem.factor.FuncPower.identity() 1 1 1
homework.polyitem.factor.FuncPower.toString() 1 1 2
homework.polyitem.factor.FuncTrian.FuncTrian() 1 1 1
homework.polyitem.factor.FuncTrian.FuncTrian(boolean) 1 1 1
homework.polyitem.factor.FuncTrian.FuncTrian(boolean,BigInteger) 1 1 1
homework.polyitem.factor.FuncTrian.FuncTrian(boolean,ItemAdd) 1 1 1
homework.polyitem.factor.FuncTrian.FuncTrian(boolean,ItemAdd,BigInteger) 1 1 1
homework.polyitem.factor.FuncTrian.clone() 1 2 2
homework.polyitem.factor.FuncTrian.derivate() 4 4 6
homework.polyitem.factor.FuncTrian.equals(Object) 6 4 8
homework.polyitem.factor.FuncTrian.equalsZero() 3 3 4
homework.polyitem.factor.FuncTrian.identity() 1 4 5
homework.polyitem.factor.FuncTrian.toString() 1 2 3
homework.polyitem.item.ItemAdd.ItemAdd() 1 1 1
homework.polyitem.item.ItemAdd.ItemAdd(Derivable...) 1 3 3
homework.polyitem.item.ItemAdd.ItemAdd(HashMap<String, Derivable>) 1 1 1
homework.polyitem.item.ItemAdd.ItemAddPut(Derivable) 1 4 4
homework.polyitem.item.ItemAdd.PutItemMul(ItemMul) 1 5 5
homework.polyitem.item.ItemAdd.clone() 1 2 2
homework.polyitem.item.ItemAdd.derivate() 2 2 3
homework.polyitem.item.ItemAdd.equals(Object) 3 2 3
homework.polyitem.item.ItemAdd.equalsZero() 3 2 3
homework.polyitem.item.ItemAdd.getAdditem() 1 1 1
homework.polyitem.item.ItemAdd.getOnlyOne() 4 2 4
homework.polyitem.item.ItemAdd.identity() 1 1 1
homework.polyitem.item.ItemAdd.onlyContainOne() 1 1 1
homework.polyitem.item.ItemAdd.toString() 6 5 7
homework.polyitem.item.ItemMul.ItemMul() 1 1 1
homework.polyitem.item.ItemMul.ItemMul(Derivable...) 3 3 3
homework.polyitem.item.ItemMul.ItemMulPut(Derivable) 3 5 6
homework.polyitem.item.ItemMul.PutFactor(Factor) 6 10 10
homework.polyitem.item.ItemMul.PutItemMul(ItemMul) 1 2 2
homework.polyitem.item.ItemMul.clone() 1 2 2
homework.polyitem.item.ItemMul.derivate() 6 2 7
homework.polyitem.item.ItemMul.equals(Object) 3 2 3
homework.polyitem.item.ItemMul.equalsZero() 3 2 3
homework.polyitem.item.ItemMul.getCoeff() 2 2 2
homework.polyitem.item.ItemMul.getMutiitem() 1 1 1
homework.polyitem.item.ItemMul.getOneExp() 5 2 5
homework.polyitem.item.ItemMul.identity() 2 3 4
homework.polyitem.item.ItemMul.negateCoeff(boolean) 1 2 2
homework.polyitem.item.ItemMul.onlyOneExp() 3 3 7
homework.polyitem.item.ItemMul.onlyOneFactor() 4 3 7
homework.polyitem.item.ItemMul.removeItem(Derivable) 1 2 2
homework.polyitem.item.ItemMul.setCoeffOne() 1 1 1
homework.polyitem.item.ItemMul.toString() 1 7 7
homework.polyitem.item.ItemMul.updateCoeff(BigInteger) 1 1 1

MetricReloaded分析程序复杂度更加病态了,大量方法的结构化程度存在问题,并且集中在与化简有关的方法中。表达式解析中的readOneItem()方法三项均超标,虽然我已经进行了采用了一部分的工厂模式、将正则表达式存入单独的类中以被调用的解耦合的努力。

Package复杂度:

Package v(G)avg v(G)tot
homework 2 2
homework.expression 6.68 127
homework.polyitem.factor 1.86 93
homework.polyitem.item 3.38 115

通过分包,将几大功能区分开(不过这次看到20%的性能分,增加了暴力搜索提取公因式的简化方法,还是放在Exp处理中,所以耦合度也有点高)。

② 程序Bug分析

“OO中最惨的,不是被同屋hack了50个同质Bug,而是在截止提交的下一秒意识到了自己的Bug”

——沃茨基·硕德

在第三次作业中,我为了简化做了不少工作,也用随机数据自动测试程序做了大量的检验。然而就在周六晚上截止提交后的几秒,我突然意识到我的输出是有问题的——对于表达式因子,我将其设置为继承了Factor类,同样拥有指数Index属性,在输出时,采用的是和幂函数、三角函数一样的输出方式——“(exp)**index”,但在输入时表达式因子是不允许有指数的,因此属于WF。但对于Sympy,表达式的格式限定很宽松,通过计算并不能找到错误。

那能咋办……周六晚上看番转移注意力,周日在互测中尽可能挽回损失……最后发现强测没有出现这种输出,但互测时被同屋两名Servent发现了这个Bug。好在修复工作也比较简单,实在是侥幸。

③ 互测采用策略

在这次互测依然是采用对拍(对军宝具)+手动构造样例(我自己构造了可能会TLE的样例,也分享到了群里)+Python生成随机数据自动评测的方式。

在这次对Python生成随机数据做了优化,比如Caster在指数为0时会出现各种吊诡的错误,然而互测限定指数>0,于是我将对Caster的随机数据设为指数始终>0,其他成员照旧,避免了反复查看不能hack的Bug带来的失落感。

最后稍微吐槽一下“不优化就不会Die”,在这次互测中,房间内8名成员,4名优化输出4名不优化,最后出Bug的都是那4名优化输出的……其中Berserker还会在表达式嵌套过多时陷入死循环,截止至本文发稿时已被修好。

④ 对象创建模式

在这次的作业中终于用到了工厂模式!虽然原因是表达式解析方法太长,不得不将生成项的代码独立开来。不过我也只用工厂模式处理了幂函数、不含嵌套因子的三角函数、常数,含嵌套因子的三角函数的生成与我的状态机密切相关,难以抽象出来,这也是我的架构中的不足。

心得体会

在寒假的时候,我曾看到知乎上@HansBug学长关于OO课程改革的回答,而通过这一个多月的实际体验,OO给我的感受还是很赞的,通过互测阅读同学代码、与舍友们的交流(感谢@VOIDMalkuth!!!)、水讨论区以及学习理论课,收获很大。

第一单元也只是从面向过程到面向对象的过渡篇章,通过这次反思,我也发现了过去几次代码中自己结构较为不合理的部分,希望能够在接下来多线程等知识的学习中进一步改善。

上一篇:【作业1.0】OO第一单元作业总结


下一篇:linux下USB串口,minicom