BUAA_OO_2021_第三单元总结

BUAA_OO_2021_第三单元总结

OO第三单元以一个社交关系模拟系统为主题,学习了JML形式化规格语言。我觉得JML是一个非常适合于开发的工具,规格化的设计比直接进行程序设计出现错误的可能性小得多,并且对于比较大的项目来说,按照规格完成代码比较容易,每一个类的方法都很清晰,便于扩展功能和debug。

根据规格采取的设计策略

完成这三次作业的过程大概是这样的:粗读JML,大概明白每一个方法要做什么,整体要实现什么->找到其中的关键部分(优化部分),通过查阅资料/和同学交流确定优化方法->完成规格->测试。

对于这部分其实没有什么设计策略,直接就按每个方法的规格严格地完成代码,除了需要优化的地方进行了一些设计,感觉这部分对于Java容器的应用会对设计起到莫大的帮助。

基于JML规格来设计测试的方法和策略

课程组推荐的Junit单元测试是一个比较好的测试工具,但由于比较懒,对这么多方法去造代码感觉太麻烦就没有尝试。
我感觉基于JML的测试主要就是对一些并没有完全按JML实现的方法进行测试,也就是一些优化的方法进行测试,然后通过一些简单的样例来测试那些比较简单的方法就可以。
我的测试方法主要是利用了第一次作业的强测数据对第二次作业的qbr,第三次作业的最短路径方法进行了测试,然后主要的测试都依赖于hxd的测试数据。

容器选择

容器选择是决定作业质量的关键(尤其是第三次),选对容器能让写代码的难度降低很多很多。

Hashmap

哈希图作为以键值对为基础的容器,使用起来可以说得心应手。
在JML规格中,数据结构都市以数组形式给出的,但Arraylist往往不是最加选择,比如id-person,id-value等值对使用Hashmap来处理,在查询、修改时都比数组要容易的多

PriorityQueue

这个容器在第三单元救了我一命,也是一个hxd分享给我的,在处理最短路径的迪杰斯特拉算法中这个容器非常好用。下面将会介绍一下这种容器

实现原理:

Java中PriorityQueue通过二叉小顶堆实现,可以用一棵完全二叉树表示(任意一个非叶子节点的权值,都不大于其左右子节点的权值),也就意味着可以通过数组来作为PriorityQueue的底层实现。

主要方法

add(): 按照二叉树的性质把元素插入
element(): 获取但不删除队首元素
remove()/poll():获取并且删除队首元素

在迪杰斯特拉中,通过优先队列来找到路径最短的节点进行遍历是非常方便的,会很好的降低算法时间复杂度,且不容易出错。

性能问题

我遇到的性能问题主要在第一次作业的qci、qbm,第二次作业的qgvs,第三次作业的sim、dce。

并查集

第一次作业使用了并查集来解决计算不连通块数的问题。在addperson中初始化并查集,在addrelation中合并联通的点并且把根节点设置成最小的那个,同时对全局变量block进行修改,这样可以把qbm本来要承担的时间复杂度降低了。

BUAA_OO_2021_第三单元总结

化整为零

对于时间复杂度为o(n2)的qgvs,采用了把计算分割到其他方法的策略。在addrelation和delfromgroup两个方法中对value值进行增减,调用该方法时直接返回value即可。对于agemean和agevar没有想到什么优化的方法,就顶着o(n)的复杂度交上去了,从结果看应该是被接受的。

基于priorityqueue容器实现的迪杰斯特拉

直接上代码了,其实我也没搞懂这样做的时间复杂度是多少,感觉是应该小于等于o(ElogE)的。

BUAA_OO_2021_第三单元总结

作业架构设计

UML图

BUAA_OO_2021_第三单元总结

图的构建和维护

这一部分感觉做的特别潦草,因为直接面向JML实现了,其实对message\group\person究竟连成了什么图都很模糊,只是通过测试去确定自己的方法是不是都正确,这是对于整个作业的架构没有理解透彻导致的。

总结

这一单元的难度相对于前两个单元更低,难点在于对于需要优化的部分进行正确处理。在完成作业的时候和同学讨论起到了很大的帮助,比如堆优化迪杰斯特拉和容器,这些如果不和同学交流我是肯定想不到的,也让我感受到了我对于数据结构和算法的无知,不能再摸了###

上一篇:BUAA OO第二单元总结:电梯调度


下一篇:BUAA(2021春)——排座位(简)a——挺有技巧的