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本来要承担的时间复杂度降低了。

化整为零

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

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

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

作业架构设计

UML图

图的构建和维护

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

总结

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