BUAA 面向对象课程 第三单元总结

JML单元，对 JML 规格的理解和代码实现

一、实现规格所采取的设计策略

JML(Java Modeling Language)是用于对Java程序进行规格化设计的一种表示语言。JML是一种行为接口规格语言(Behavior Interface Specification Language, BISL)，基于Larch方法构建。BISL提供了对方法和类型的规格定义手段。所谓接口即一个方法或类型外部可见的内容。

关于实现过程，因为JML狭义上只是一种对于规格的描述，它并不会约束具体的实现形式。所以我在编写代码之前要将规格整体化的浏览一遍，并注意观察并记忆类相互之间的关系，如依赖关系，调用关系，所属关系等。

具体而言，本单元作业实现了一个关系网的模拟，实质上维护了一个无向图的结构，其中的点具有一定量的属性和行为，边后期也具有了属性和行为（可以是network类驱动的）。这种结构的抽象也有助于在实现时选择合适的数据结构和容器。对于id到独一无二的个体的映射，使用map；对于group的需求，即强连通分量的维护，使用并查集；对于连通分量所拥有的属性的维护，进行实时更新；对于最短路计算需求，使用最短路算法等等。

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

课程中介绍了junit，实际在单元作业项目中没有真正应用到。逻辑验证不失为一种好的方式，说白了就是答完试卷后进行检查。针对jml的描述，对代码段进行一一的对照检查。

另外，和同学进行程序对拍，随机生成数据，检测输出是否相同。

三、容器选择和使用的经验

容器的选择就依照需求了吧。id-实例这种要用HashMap，消息列表要用链表或是队列，因为要进行队首插入。

在编写代码的时候要注意面向接口编程，也就是说不要试图去编写独立于特定容器实现的代码。如果真的有这种需求的时候，则不要定义接口引用如List而是直接使用LinkedList这种具体实现的类。

四、如何通过良好设计以避免出现性能问题

如前面所说，将模型抽象为一个图结构，有助于简化问题，淡化细节，找到影响时间复杂度的因素。同时能更容易的将已知的图论知识结合进来。具体而言，这个简化的关系网就是一个只具有无向边的具有一个或多个强连通分量的图结构。那么现在有关于判断人之间认识关系的需求，可以理解为这个图结构中的无向边。

在queryBlockSum()中也就是要对连通分量进行计数，则可以利用并查集来对连通情况进行维护，每次统计连通块个数的时候，利用set的特性进行计数。

在第二次增加的需求中，增加了一些统计量的计算。如果直接朴素计算的话时间复杂度是一定无法满足需求的。可以在具有对这些统计量有所影响的操作处，进行数值的在线更新。因为每次在线更新的代价小，这样的实现，最终查询的时间复杂度是线性的（O（1）），而更新操作所消耗的代价远远低于朴素计算。

第三次增加了最短路径的需求，就使用最短路dij算法了，并可以加以堆优化降低一下复杂度。

五、梳理架构设计，特别是图模型构建与维护策略

见第四部分的介绍。