OO第三单元总结

刘兆薰 19373345

 

设计策略

JML相当于一份规格严肃的针对程序员的说明书，相比自然语言描述更加严谨，但也更加冗长且具有专业性。自然语言通常能显式地描述类与方法、方法与方法之间的层次关系（如调用关系、继承关系）。但是JML通常不能很好地体现出上述关系，需要程序员自己去挖掘；如果无脑进行JML的直接翻译，虽然正确性可以保证，但是很有可能造成性能上的不理想。因此，我在作业完成中先通读一遍JML，理解其本质的功能，再思考更优性能的实现方法。

我在实现JML规格时，是先把比较类似的异常类实现了，再去实现相对比较独立的person，group，message类，最后实现各个类之间交互最多的network类，实现策略是先严格按照JML翻译理解功能，然后再对性能可以优化的地方进行更改，具体优化见下文。

 

架构设计

首先在network类中有三个HashMap，三个分别是person，group，message根据独一无二的ID找对应对象的HashMap，设计到三者之间的交互关系时，我一般是在对应类里添加相关方法，然后根据network类中方法的需要调用person，group或是message类里的方法去管理他们之间的交互关系，如person类里有管理一个messageMap，groupMap，管理这个人的message和加入了哪些group，group类里有很多需要动态管理维护的变量，不多赘述，emoji类中有messageMap管理那些是这个emoji的message，删除冷门表情时需要，而node和edge类是为了边存储person之间关系设置的类，以便最短路的查询。除此之外整体设计几乎是按照规格一一实现的，其实后来思索，可以把一些算法例如Dijkstra、并查集等的方法将他单独分为一个类，在network里直接调用类方法结构会更清晰，这样也便于后续修改。

 

测试分析

我们在测试时就可以先不考虑性能，照着JML翻译，这样出错的可能会比直接写小很多，然后可以找同学进行对拍（可以多找几个，避免出现两人犯同一错误的可能性），确保基本正确性没有问题，然后可以把这份代码作为正确性测试基准，与之后自己提升性能后的代码再进行对拍确保正确性没问题。至于数据生成，我们可以先根据题目要求先进行随机性测试，即按照题目要求随机生成符合要求的数据，当发现在某一条指令出现问题后，根据JML规格去构造针对某个方法各个情况的数据，看具体是哪一条判断或者处理出现了问题。

 

容器选择与相关方法总结

本次作业里容器选择十分重要，因为不同的容器可能带来的时间开销相差巨大，从而可能出现因容器选择不佳导致超时的情况，我最初采用的TreeMap来管理person，group，message等ID对应的关系，因为考虑到后续可能会排序操作，而TreeMap维护的有序数据非常合适，而TreeMap内部是红黑树算法实现的，所以查询时也很搞笑，可是当第一次我和同学代码对拍时，发现我的时间是其他同学两倍多，而基本算法思想是一模一样的，我就开始找问题，最终发现是TreeMap背锅了，我将TreeMap换成了查询效率更高的HashMap，效率提升两倍不止，的确，我们此次的人际关系网络对于各种id的查询异常值多，所以用HashMap来进行管理，效率提升显著。当然除了用到HashMap容器还有ArrayList容器，对于无顺序要求和查询要求的数据用ArrayList查询非常方便，例如我的emoji类中一个ArrayList用来储存所有emoji message，ID是当前emoji对象的emojiId的messageId，因为在后续delete时需要在network的message net（一个key为messageId，value为message的HashMap容器）中删除那些是冷门emoji对应的message，这样无论是遍历还是增加删除元素，ArrayList都很方便。

 

BUG总结

第一次作业

在第一次作业中容易出现性能问题的是isCircle和queryBlockSum方法，isCircle这个方法主要是判断无向图里的两点是否处于同一个连通块，而queryBlockSum是查询图里有多少个连通块，这两个方法如果是朴素的深搜，时间开销会非常的高，所以这里我才用的是并查集算法，使用并查集时加上了启发式合并与路径压缩，启发式合并可以让树的高度尽可能小，路径压缩实际上是把一棵树的根节点设置为所有节点的父亲。在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针都指向根结点，所以只需要​的复杂度来判断两点是否是同一连通块。第一次作业就顺利解决了，强测和互测都未发现bug，效率也很高。

第二次作业

在第二次作业中容易出现性能问题的地方在于对group中几个量的动态查询，稍微复杂一点的是ValueSum的更新，如果是按照JML规格写的每次​去查询，这时间复杂度非常高，很容易就被卡掉了，所以我依旧是采用的动态维护的方法，首先是在加入person时遍历group里现有哪些人，如果与该person有关联则更新ValueSum，删除时同理，第二个需要注意到的是，可能新加关系带来ValueSum的变化，我的处理是在person类中加入了一个元素是group的ArrayList容器，用来记录某人加入了哪些group，在addRelation时，是要遍历person1的这个list，如果里面某个group同时有person2，那么更新这个group的ValueSum。这样维护的复杂度不算很高并且每次查询可以以​的复杂度查询。第二次作业也就顺利解决了，强测和互测都未发现bug。

第三次作业

在第三次作业中容易出现性能问题的地方在于deleteColdEmoji和sendIndirectMessage方法，deleteColdEmoji方法要求删除热度小于limit的表情，所以一开始是想把emoji按照热度排序然后遍历最小的直到limit删除，但仔细思索后发现维护有序代价也挺高，于是便决定直接遍历所有emoji找到热度小于limit的，然后去遍历emoji里的messageMap去删除是该表情的message，表面上看是一个二重循环，其实不然，因为该循环执行的总次数一定不会超过指令条数，只要删除后下一次便不需要再次遍历，除非有新的message加入。

sendIndirectMessage就是两点之间求最短路，最常用的就是Dijkstra算法，然而Dijkstra算法是​的算法，每次查询都是​，查询指令如果接近一万就很容易超时，所以考虑用Dijkstra加堆算法，加堆的复杂度为​(m为边数)，的确，当图接近于完全图时，加堆的算法复杂度会达到​，那为什么加堆在这里会更优呢，因为我们限制了指令数，加人和加边都需要一条指令，例如我们要想图接近于完全图，加70人和4900条边便已接近于5000条指令，Dijkstra加堆复杂度也并不高，但如果5000条加人的话，朴素算法复杂度将会非常高，所以这里选择Dijkstra加堆，我这里还选择了存边进行优化，即为了在更新dist[]时只会选择与当前讨论节点有关联的点，极大节省了时间，另一个可优化的地方就是我们只需要查询例如a到b的距离，而Dijkstra运行完是将a到所有点距离都求出来，所以我们实际并不需要它运行完，当从优先队列里取出的点是b是，即a到b的距离不可能再被更新了，此时我们便可以break掉了。

第三次作业强测中出现了一个bug，是在第二次作业实现时几个query指令时间复杂度稍微高了一些所致，所以采用了分散到每一次add和delete的策略，大大降低了时间复杂度。