首页 > 技术文章 > 第三单元

BuniQ 2022-05-31 16:48 原文

1. 架构设计

1.1 第一次作业

在这里插入图片描述
​ 此次作业的架构比较简单,首先依据Person接口和JML规格来实现MyPersonMyPerson类生成的每个对象都会有id(编号)、name(姓名)、character(性格)、age(年龄)、acquaintAndVaule(认识的Person和两人关系的权重)和circleFlag(所处的连通块编号)等属性,其中,因为id是独一无二,可以作为equals的判断依据;acquaintAndValueHashMap容器实现,Person作为key,两人关系的权重作为value。

然后依据Network接口和JML规格来实现MyNetwork,其中people属性用来表示社交网络中的Person,用HashMap容器实现,id作为key,Person作为value。在判断两人是否间接认识即isCircle时,采用的是并查集算法。每个人初始的circleFlag是其id,每次addRelation时,都将其中一人的circleFlag变成另一人的circleFlag,基于QuickUnion实现并查集,并通过高度低的树向高度高的数合并和路径压缩,就可以高效查询网络中两个节点的连接状态。

1.2 第二次作业

在这里插入图片描述
​ 这次作业的架构则是在上次作业的架构上作了扩展,首先依据Person接口和JML规格来实现MyPerson,和上次作业大致相同,其中MyPerson类中的acquaintAndValue拆分成了acquaintancevalue,都用HashMap容器实现,用id作为key,用Personvalue分别作为value。

然后依据Group接口和JML规格来实现MyGroupMyGroup类生成的每个对象都会有id(群组编号)、people(群组中的人)、peopleSize(群组中的人员数)、ageSum(群组内所有人的年龄之和)、conflictSum(群组内所有人的异或和)、relationSum(群组内关系的数量之和)和valueSum(群组内关系的权重之和)等属性。其中,peopleHashMap容器实现,id作为key,Person作为value。其中peoplepeopleSizeageSumconflictSum都是在addPerson时动态维护的,relationSumvalueSum都是在addPersonaddRelation时动态维护的。

最后依据Network接口和JML规格来实现MyNetwork,在上次作业的基础上增加了groups属性,用来记录Network中所有的群组,用HashMap来实现,群组编号id作为key,群组Group作为value。

1.3 第三次作业

在这里插入图片描述
​ 这次作业则是在上次作业的基础上做了进一步的扩展。其中,MyGroup类中增加delPerson方法,在执行该方法时,要动态维护peoplepeopleSizeageSumconflictSum等属性。

MyNetwork相较于上次作业增加了很多新方法,为了更好地实现,增加了Relation类,记录一个Relation中的两个人的编号和关系权重。其中,queryMinPath要求两人间最短社交路径,本次作业使用了Dijkstra算法来实现;queryStrongLinked要求两人间是否有两条不相交的社交路径,本次作业使用了tarjan算法来寻找点双连通分量;queryBlockSum要求连通块数目,由于使用了并查集,所以不同的circleFlag数量就是连通块数目。

2. Bug修复情况

本单元只在第三次作业中出现3个点CTLE的情况,这三个点的特征是大量的queryMinPath的命令。在求最短路径时,本人采用的是Dijkstra算法,所以重新提交后,bug修复。

3. 心得体会

第三单元的作业是JML规格下进行代码的实现,在具体实现时,数据的实现方式、容器的选择、方法的实现算法都是值得仔细考察的内容。JML规格像是签订了一份“契约”,在未来的工程实践中也会十分有用。经过整个单元的学习,我对JML规格有了更深的认识,但是在工具链的使用和单元测试等方面还需要进一步的了解和学习。

推荐阅读