OO第四单元总结

面向对象第四单元总结


19231166——马祎垚

目录

UML单元的架构设计

在本UML单元中,我针对每一个使用到的类图、顺序图和状态图的element原类,都进行了自己的转换,转变成MyUmlxxx类。这样相当于一个分层剥离,在之后我使用他们的时候,存储和调用的都是我自己写的类,比较便于添加我想定义的属性与方法。

具体而言,由于三次作业是渐进性的,以第三次作业为例。我分别建立了myclass,mystatemysequence三个包,其中装着相应的MyUmlxxx。并且在每个包里会有一个大集合似的类,负责数据的输入整理与分类。根据输入数据的不同类别,可以放到不同的容器里;再根据一些输入的联系(比如继承、关联等),将有联系的两个对象进行一定的连接。在第三次作业的规则检验中,考虑到该类可以直接触碰到所有容器和所有输入元素,我则至极把核心代码写到了这个类中。

在三个包之外,我完成了多个可以真正实现要求的类。即题目中要求的MyUmlInteractionMyUmlGeneralInteraction,考虑到后者代码量较多,我在第二次作业还是保留了前者。具体来说,就是根据题目要求实现的方法,用各种算法,来完成每个函数。

架构其实一共有四层,底层为每个MyUmlxxx,第二层为每种图里的数据输入与分拣类,第三层为每种层里对题目要求实现的函数,第四层为最终的MyUmlGeneralInteraction实现。由于分了四层,每一个类的长度都不会太长,且最终总类基本不用实现,只负责调用,比较清晰。


四个单元的架构设计与OO方法的演进

第一单元

现在回首,多项式求导单元是一个从面向过程到面向对象的转变。虽然当时觉得特别难,现在回顾也真是特别难,但起码它的思想比较好理解,比较容易搭建结构,难在具体实现。当时每次作业出来都很头疼,因为完全想不好怎么架构,对整个单元也是模模糊糊的。

主类

MainClass负责读入数据,并做最初步的处理,将初步优化的字符串传递给下属类解析。最后进行输出。

数据保管

Factor类为一个抽象因子类,其中保存了因子的指数exp(常数的exp为其本身),并有get/set/derive等基础方法;Cos/Sin/Const/power/Poly五个类继承了Factor类,并根据自己特殊需要重写、增加了一些方法;Item类为因子类,保存着一个ArrayList型的factor容器,和系数base;Expression为表达式类,保存着一个ArrayList型的item容器。

运算

MulDerive类实现对项求导并返回表达式。

化简

所有的化简都在ToSimplify中实现,包括在一个项中对因子实现乘法合并;在一个表达式中对项实现减加法合并;三角函数优化等等。

OO第四单元总结


第二单元

电梯单元面向对象的感觉就已经出来了,每个类在干什么、负责什么都很明晰。

并且我算是占了架构合理的便宜。在第一次作业有幸设计了一个比较不错的架构,导致第2、3次作业几乎不用改什么,每次添加的代码行数不过300行(如果不优化甚至可以只添加100行)。比较复杂且核心的调度类在第一次之后就没改过,这全归功于架构的合理性。

这时我也第一次体验到:面向对象编程好香啊。

第二单元也是我OO课程中的巅峰时代,再往后就一路出bug了.....

架构设计

  • 第一次作业

OO第四单元总结

  • InputThread -> 输入类,为单独一个线程。
  • WaitingQueue -> 每一层的等候队列,本质是装着Request的容器。
  • AllQueue -> 整个电梯的等候队列,本质装了20个WaitingQueue。共享对象。
  • Lift -> 电梯类,单独线程。只负责电梯的运动控制。
  • Dispatcher -> 调度类,是Lift电梯类中的一个属性。Lift类开始run时初始化Dispatcher,并把电梯本身传入。调度类根据电梯内的人、电梯等候队列的人、电梯的运行状态和当前pattern来判断下一步做什么运动。

Dispatcher 有一个begin函数,lift线程开启后每次循环都会调用其一次。其中会针对不同pattern选择调用不同函数,如Morning/Night/Random。

OO第四单元总结

? 每一个函数内会根据当前模式的特点来控制电梯下一步运行策略。我主要采用的是Look算法,即如果电梯没满,就去找同方向的最远等候乘客。每移动一层都要判断一次,可以实时改变最优策略。

  • 第二次作业

OO第四单元总结

第二次作业在第一次的基础上增加了电梯数量,在3-5之间不等,但电梯的种类和第一次一样。因此我的的整体架构相对于第一次并没有太大改变。添加了WaitingPool类,用来存储输入的乘客;添加了Scheduler类,用来把等候池里的人一一分配给不同乘客,此类单开一个线程。除此之外,几乎没有太大的改变。

整体思路:通过InputThread类来输入请求,把其中的PersonRequest全部放入WaitingPool中管理的pool里(本质是个ArrayList);把其中的ElevatorRequest放入一个大家都能访问的电梯容器里。Scheduler获取pool里的乘客,根据模式不同、每个电梯状态的不同来把每个乘客放进不同的电梯等候队列里(AllQueue)。只要分配好每个电梯的等候队列,后面的操作就完全不用再管了,优化也仅限于分配策略那几十行,特别清晰。

  • 第三次作业

OO第四单元总结

可以看到,由于第一次作业的架构比较合理,本单元二三次作业的迭代非常顺利。而第三次作业的总体架构与第二次作业没有改动。

后续扩展,如果增删电梯的运动模式。比如除了向上走、向下走,还能有加速上行、加速下行等,类似对电梯本身的改动。只需要在Lift类里增删函数即可。

如果增加电梯的种类,比如除了第三次作业的ABC型电梯,还有其他模式,那只需要更改分配器,针对不同的要求把不同的乘客分配出去。完全不需要修改已经写好的Lift类(因为我一直以来的策略就是,无论针对哪种电梯,电梯本身的属性不改变,只是通过外界对它输入乘客的操控来区分类别)。


第三单元

其实从电梯的最后一次作业开始,OO课程的难度就开始走下坡了。而JML单元则是大家公认的最简单的一单元作业,不过也产生了我强测得分最低的一次作业....

JML的思想很简单,按照JML注释来完成相应的代码,对于某些方法,需要进行图优化。其实对于个体来讲,可能在这一单元对面向对象的认识没那么深刻。

架构设计

由于JML对于设计要求给的已经非常详细了,因此大部分代码仅需将JML语言直接转化为Java。只有小部分的数据结构选择和代码复杂度优化需要自己设计。这里将展示一下需要自行思考的类设计。

Network

  • isCircle函数要求判断id1与id2对应的Person是否成环。如果用递归或栈来实现,时间复杂度较高。因此选择用并查集实现, 每次仅需判断一下二者是否有相同的头结点即可判断是否成环。然而这个方法要冒着后续作业增加删除的风险,不过所幸没增加。
  • sendIndirectMessage则要求求最短路径,首选迪杰斯特拉算法。但是用朴素版的时间复杂度会达到O(n),这里可以使用java自带的数据结构PriorityQueue来存储节点,时间复杂度减少至O(logn)。
  • queryBlockSum要求连通分量。并查集的数据结构使得我们之前一直在维护一个连通分量作为属性,此时直接返回即可。

Group

  • getValueSum的实现如果按照JML的思路,是个O(n^2)复杂度的二重循环。如果10000条指令频繁操作这个方法,CPU时间恐怕难以保证。因此动态维护一个变量valueSum,当增加关系或将人增加进组时改变其值,最后直接返回。

对于大部分的存储结构,我都采用了这种存储方式 。

private HashMap<Integer, Person> people;
private HashMap<Integer, Person> acquaintance;
private HashMap<Integer, Integer> value;

针对社交网络的图模型维护,people存放id-person为点集;acquaintance以邻接表的方式存放id-person为边集;value以邻接表的方式存放id-value的权值。如此构造了一个图模型。

维护的核心在于前述的并查集,当增加一个关系时,如果这两个人曾经不成环,则可以合并两人头结点一个,代表可达。并查集可以实现查询&插入接近O(1)复杂度的速度,且维护十分方便。


第四单元

本次作业的架构设计如上所述:简单来说一共有四层,底层为每个MyUmlxxx,第二层为每种图里的数据输入与分拣类,第三层为每种层里对题目要求实现的函数,第四层为最终的MyUmlGeneralInteraction实现。

到了第四单元,对面向对象的认识已经更深一步了。在写代码的时候已经非常熟练地分层分块分类地写,函数调用和数据管理也比开学清晰多了。


总而来讲,OO课程让我对面向对象的理解是看山是山——看山不是山——看山还是山。一、二单元明确地知道在学习面向对象思想,第三单元不知道在干什么,第四单元转回来才发现其实已经下意识面向对象了。


对测试的理解与实践的演进

非常惭愧地讲,这四个单元我在测试上下的功夫是递减的(可能归功于我身边的大佬同学们的帮助

第一单元中,我还能根据每次作业不同的复杂性,采用不同的测试方法

  • 全自动测试程序->第一次作业。

    由于第一次作业表达式较为简单,运算复杂度较低,因此我采用了全自动测试方法。

    在Python中根据表达式可能的正则构造出长度不同、侧重点不同的测试数据,并链接外部java文件读入结果,进行格式处理,与Python自己计算结果进行比对。因为对两个结果做过一样的格式处理,因此每一个表达式只有唯一的标准答案。最后利用python的diff库来比对,如果不匹配,可以以可视化的形式显示出差异位置。

  • 半自动测试程序->第二次与第三次作业。

    在二、三次作业中,由于表达式逐渐复杂,考虑到自动生成的覆盖面窄形式统一等问题,我采用了半自动测试方法。即不生成测试样例,但是对我输入的样例进行验证。

    在朋友的指导与推荐下,我学会了将java文件打包成jar格式的方法,这样可以达到同时对7个同学进行测试的效果。且为了减轻评测机负担,验证正确性的方法从之前的形式比对验证,转换成了输入多个x值,验证标答与同学答案计算出结果的差异,失误率较低,且快捷。

  • 构造测试样例->从一般到特殊

    在每次作业完成后,我首先会人为构造一些测试样例来进行验证,此时要保证样例的全面性和特殊性,也要覆盖一些所谓的阴间数据

    例如,第一次作业的测试数据,涵盖了基础测试、大数、前导0、各种优化验证等方面。

而到了第二单元,由于第一次作业难度真的很高,把代码写出来就已经很艰难了,实在没有时间再写测试程序。而第二次、第三次作业又因为自己没怎么添加代码,所以很有信心不会出锅,就也没测试....

第三单元的JML正赶上OS课程的难度巅峰,再加上身边的一些朋友详尽的测试程序和JML本身的难度不太高,因此也放弃了自行测试....

在测试这一领域,我做的的确还是不太够,//自我检讨。希望在以后的其他课程中,我可以把测试做到位...


课程收获

OO课真的真的是我进入计算机专业后对代码能力最有帮助的一门课了!

大二上的课,包括计组,对高级语言的代码能力训练都没有OO这么强。虽然是面向对象,但是在JML中顺带涉及了算法,在UML中涉及了对代码能力的考察,在电梯中学了多线程,而多项式则对整体架构思路有比较强的要求。OO教会了我许多面向对象之外的内容,也训练了我面对debug需要沉着冷静不慌不躁的心态。

当然了,除了知识与能力上的提升,OO的评测机制还训练了我对意料之外的错误怀有一种安然释怀的心态。JML单元,因为对评测数据没有认真研究,导致不知道人的id可以是负,最终导致了第三次作业强测分数拉胯。这个错误甚至10行代码就可以解决,而且完全意料之外。但是这也直接教会了我:人生不可预测的错误还会犯很多,吸取教训和逐渐释然才是最有效的解决办法。对于挽回不了的,没必要过分纠结。

OO课的氛围真的很好,感谢我的理论课老师纪一鹏老师,虽然语速很快,但讲课从来不让人犯困;也感谢助教们的辛勤努力与付出;更感谢我的好朋友们——徐逸飞/朱绍铭/邹杨/汪婧昀等等等等,没有你们的帮助和对算法优化的建议,我在OO课可能只是完成要求,做不到每一次都最大化精进代码、提高能力。


改进建议

  • 首先,对于UML单元的题目说明,希望可以更完善、统一、详细一点。
  • 其次,希望以后的评测更多考察同学们对面向对象的理解和对算法的掌握。尤其是JML和UML单元。JML突然出来id为负也就罢了,但是实在无法理解UML最后一次作业出现两个id不同但内容一模一样的继承关系的意义何在...感觉这个点考察的就是语文阅读?这和架构、设计和复杂度方面分析似乎关系的确不大....
  • 第三,多项式单元的重构经历非常不愉快...似乎第一次作业指导书建议用正则表达式来解析,但是到了后面就是递归下降了。这个改动涉及到整个代码的重写。希望以后助教们可以在最开始就引导用比较好做的方法//递归下降//做?

OO第四单元总结

上一篇:redash -"Error running query: Can't query private addresses.


下一篇:sudo:Operation not permitted事件