第三单元作业总结

一、总结分析实现规格要求所采取的设计策略

本单元作业为实现JML规格所描述的代码实现，由于本单元作业的程序主干逻辑已经实现，只需要根据JML规格的描述，实现功能就能完成，所以本单元的作业的代码逻辑设计难度比较低，主要难度在于部分实现的代码的时间复杂度。

在具体实现方面，我是先实现的person和message再实现的group和network功能，因为在逻辑上是group和network调用的people和message。

二、架构设计和规格实现

因为已经给出了代码所需的逻辑功能，所以我们不再需要思考整体的架构设计和逻辑关系，只需要按照规格实现相应函数的功能即可。由于本单元作业只对功能提出了要求，没有对实现方式提出要求，这就使得程序的灵活度提高了不少。

第一次作业

第一次作业的难度较低，主要是实现person，network这两个类的基本功能，大部分代码实现只需要能够正确理解JML规格所描述的功能就可以简单的实现，所以本次作业的主要任务是学习理解JML规格代码的语法。

第二次作业

本次作业新增了group类和message类，这两个类也是类似person的基本类，只需要按照JML规格实现即可，难度与第一次作业相似。

第三次作业

这次作业的难度比之前两次作业有所提高，不仅需要实现继承message类的几个子类，在network里还需要实现一个查找最短路径的算法，这使得时间复杂度再度提升了。

在规格上，虽然每次都有增加新的规格，也会用到一些新的JML语法，但都比较简单。

 

三、容器选择

本单元需要使用多个容器来存放person，message和人与人之间的关系，如果选择的容器查找数据耗时过长很容易导致时间复杂度较高，我采用的是Arraylist数组和hashmap来存储数据。

 

四、性能分析与bug分析

在顺利通过了第一次作业的中测时，我还远没有意识到问题的严重性，以为强测时间再高也不会高到哪去，结果强测一结束直接傻眼，第一次遇见上万条的测试数据，运行时间直接爆炸，代码逻辑出现问题导致的bug反而没有。第一次作业的时间复杂度主要是在判断是否存在路径上，所以还比较容易debug。本次作业在代码实现方面比较有难度的算是判断两个人之间是否存在可达路径，我一开始采用的是遍历查找，这使得时间复杂度非常高，虽然通过了中测但是在强测被hack的非常惨。第二次作业的主要工作是增加实现两个基本类的功能，在时间复杂度上与第一次作业差不多。第三次作业除了新增的几个message子类外，时间复杂度最高的就是查找最短路径的算法，我采用的是dijkstra算法，算法复杂度在n的2次方，但是之前判断最短路径的算法时间复杂度比较高，导致程序整体的耗时还是比较大，强测还是很惨。

五、图模型构建与维护策略

一开始以为本单元作业只是照着JML规格实现功能即可，做完才发现JML只是单纯的用来描述方法所具有的功能，如果完全按照JML规格的描述方法去写代码，就会导致时间复杂度非常高，我也是在做完这单元作业后才想到对图结构的构建和维护，我们本单元设计实现的毕竟是一个社交网络图，可以设计一个缓存查询类，用来储存一些已经常用的查询信息，在查询的时候先从缓存里查找，如果没有再使用相应的方法去查找。