面向对象第四单元总结
19231166——马祎垚
目录
UML单元的架构设计
在本UML单元中，我针对每一个使用到的类图、顺序图和状态图的element原类，都进行了自己的转换，转变成MyUmlxxx类。这样相当于一个分层剥离，在之后我使用他们的时候，存储和调用的都是我自己写的类，比较便于添加我想定义的属性与方法。
具体而言，由于三次作业是渐进性的，以第三次作业为例。我分别建立了myclass,mystate和mysequence三个包，其中装着相应的MyUmlxxx。并且在每个包里会有一个大集合似的类，负责数据的输入整理与分类。根据输入数据的不同类别，可以放到不同的容器里；再根据一些输入的联系（比如继承、关联等），将有联系的两个对象进行一定的连接。在第三次作业的规则检验中，考虑到该类可以直接触碰到所有容器和所有输入元素，我则至极把核心代码写到了这个类中。
在三个包之外，我完成了多个可以真正实现要求的类。即题目中要求的MyUmlInteraction和MyUmlGeneralInteraction，考虑到后者代码量较多，我在第二次作业还是保留了前者。具体来说，就是根据题目要求实现的方法，用各种算法，来完成每个函数。
架构其实一共有四层，底层为每个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中实现，包括在一个项中对因子实现乘法合并；在一个表达式中对项实现减加法合并；三角函数优化等等。
第二单元
电梯单元面向对象的感觉就已经出来了，每个类在干什么、负责什么都很明晰。
并且我算是占了架构合理的便宜。在第一次作业有幸设计了一个比较不错的架构，导致第2、3次作业几乎不用改什么，每次添加的代码行数不过300行（如果不优化甚至可以只添加100行）。比较复杂且核心的调度类在第一次之后就没改过，这全归功于架构的合理性。
这时我也第一次体验到：面向对象编程好香啊。
第二单元也是我OO课程中的巅峰时代，再往后就一路出bug了.....
架构设计
- 第一次作业
- InputThread -> 输入类，为单独一个线程。
- WaitingQueue -> 每一层的等候队列，本质是装着Request的容器。
- AllQueue -> 整个电梯的等候队列，本质装了20个WaitingQueue。共享对象。
- Lift -> 电梯类，单独线程。只负责电梯的运动控制。
- Dispatcher -> 调度类，是Lift电梯类中的一个属性。Lift类开始run时初始化Dispatcher，并把电梯本身传入。调度类根据电梯内的人、电梯等候队列的人、电梯的运行状态和当前pattern来判断下一步做什么运动。
Dispatcher 有一个begin函数，lift线程开启后每次循环都会调用其一次。其中会针对不同pattern选择调用不同函数，如Morning/Night/Random。
? 每一个函数内会根据当前模式的特点来控制电梯下一步运行策略。我主要采用的是Look算法，即如果电梯没满，就去找同方向的最远等候乘客。每移动一层都要判断一次，可以实时改变最优策略。
- 第二次作业
第二次作业在第一次的基础上增加了电梯数量，在3-5之间不等，但电梯的种类和第一次一样。因此我的的整体架构相对于第一次并没有太大改变。添加了WaitingPool类，用来存储输入的乘客；添加了Scheduler类，用来把等候池里的人一一分配给不同乘客，此类单开一个线程。除此之外，几乎没有太大的改变。
整体思路：通过InputThread类来输入请求，把其中的PersonRequest全部放入WaitingPool中管理的pool里（本质是个ArrayList）；把其中的ElevatorRequest放入一个大家都能访问的电梯容器里。Scheduler获取pool里的乘客，根据模式不同、每个电梯状态的不同来把每个乘客放进不同的电梯等候队列里（AllQueue）。只要分配好每个电梯的等候队列，后面的操作就完全不用再管了，优化也仅限于分配策略那几十行，特别清晰。
- 第三次作业
可以看到，由于第一次作业的架构比较合理，本单元二三次作业的迭代非常顺利。而第三次作业的总体架构与第二次作业没有改动。
后续扩展，如果增删电梯的运动模式。比如除了向上走、向下走，还能有加速上行、加速下行等，类似对电梯本身的改动。只需要在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不同但内容一模一样的继承关系的意义何在...感觉这个点考察的就是语文阅读？这和架构、设计和复杂度方面分析似乎关系的确不大....
- 第三，多项式单元的重构经历非常不愉快...似乎第一次作业指导书建议用正则表达式来解析，但是到了后面就是递归下降了。这个改动涉及到整个代码的重写。希望以后助教们可以在最开始就引导用比较好做的方法//递归下降//做？