BUAA OO UNIT3 JML语法以及社交网络的构建

本单元作业的目的是根据JML规格来实现 person 类和简单社交关系的模拟和查询，同时需要构造异常类子类处理程序运行时候产生的异常。相较于前两个单元的作业，本单元的难度有所降低，但是有关JML基本语法知识的学习和大篇幅JML注释的阅读也花费了我很多的时间。

 

设计策略

因为JML中已经明确地指出了数据规格和方法规格，所以我在学习并理解这些JML语言后，我就将已经确定的规格通过Java语言加以实现。

在第一次作业中，我首先将全部JML规格通读了一遍，这样可以对于总体的框架和每个函数的功能作用有一个初步的了解，明确了大方向后可以使我少犯一些愚蠢的错误，并且有助于我选择合适且高效的数据结构来存储相应的信息。

此外，在对于JML语言的实现过程中，我们需要保证代码的严谨，例如是否将所有可能的情况覆盖全面，抑或如果自己采用了一种认为更好的算法变形来完成方法时，是否能保证我们采用的变形算法的正确性和时间复杂度方面的问题。

最后，在我们完成代码的过程中，最好能够实时的对于算法时间复杂度进行评估，如果发现异常可以及时纠正。

 

测试方法和策略

我的测试方法主要分为以下几个方面：

首先，根据JML对方法进行覆盖性测试。测试顺序为从原子方法开始，然后逐层向上进行。

其次，对于自己代码中比较核心（用到了复杂的算法或复杂度较高）的部分进行强化测试（例如增加图的复杂性，扩大验证的全面性，增加关于边界数值的测试等）。通过该方法，我成功查出了我在求取人名rank的时候将排名误作为从0开始这一低级的错误。

最后，如果想进行更进一步的测试的话，可以同学之间分工合作，构建一个评测机对于代码进行评测。并且为了避免忘记删除测试有关的代码从而对强测产生影响，我们可以将debug部分统一装载到一个debug类中。此外，测试数据并不是简单的随机产生，这样可能会产生很多无意义的测试，例如我们需要在扩大图的复杂性的时候，应当尽量使每个连通域中的人物和关系更加复杂，而不是仅仅增加连通域的数量，这样对于代码时间复杂度的测试没有太多帮助。

 

容器选择

因为本单元的所有作业都是在维护一个以带权无向图为基础的社交网络，需要我们实现的指令功能也都是对图进行增删改查等一系列基本操作。所以我最终在MyPerson类中采用了HashMap来存储acquaintance和value这两个属性，这样不仅增加了查询等操作的效率（HashMap具有查询速度快等优势），也大大简化了代码量（相对于最简单的数组存储）；同样，我在MyNetwork类中也采用了HashMap，用于存储people这一属性，因为本次作业中也涉及到了对于两个节点之间是否位于一个连通块这一判断，采用HashMap在查找中可以在一定程度上避免超时的发生。

此外，在迪杰斯特拉算法中，我采用了HashTree和HashSet这两种容器。其中HashSet用来存放不能重复的元素，而且查询的时间复杂度接近O(1)，在使用迪杰斯特拉算法求最短路径时，要记录已经访问过的Person的id，此时使用HashSet存储调用contains()方法可以实现。另外，HashTree具有可以对于存储的二元组依据key自动排序的功能，并且也可以实现快速查找，因此在求取最短路径中也可以发挥很大的作用。

在历次作业中，最常见的可谓是ArrayList了，其优势在于其随机访存效率高，如果我们的数据集合需要频繁的变动和遍历，那么ArrayList不失为一种很好的选择。

自此，在确定容器后，对于JML的实现就显得不那么复杂了。

 

性能问题

第一次作业中：决定本次作业性能的关键点就在于isCircle和queryBlockSum函数所采用的算法。如果queryBlockSum是照搬JML语法来实现的话，就可能会产生很高的时间复杂度，从而在qbs指令过多时导致CPU超时。

在最初我isCircle采用了广度优先算法，queryBlockSum照搬了JML语法，导致了互测中被疯狂hack。后来我学到了一种新的思路：连通域的思想，即在加人、加关系后，我都对于连通域的情况进行一次调整，这样就不会出现每次qbs都需要重新分类一遍这样不合理的操作了。

在采用后者的思路后，我代码的效率得到了明显的提升。

第二次作业中：决定本次作业性能的关键点在于对于每个人valueSum的计算和年龄方差的求取方法getAgeVar，这两个方法均可能会导致CPU超时。于是我采用了在MyGroup中对于这些变量进行实时维护和更新的方法，即每当MyGroup的实例中增加了成员后，我都会更新相关的数值，避免多条同类指令来到时进行不必要的重复计算，虽然使得各个类的耦合度有所增加，但是使得性能得到了很大的提升，也验证了有得必有失这句话。

第三次作业中：决定本次作业性能的关键点在于新增了基于迪杰斯特拉算法的最短路径查询方法，sendIndirectMessage，deleteColdEmoji是两个可能会产生超时的方法。本人的代码在这次作业中的性本能表现并不是很理想，后来听取同学建议采用了堆优化的迪杰斯特拉算法后感受到性能有了很大的提升。

此外，由于Dijkstra算法每次得到的是源点到所有顶点的最短距离，而每次调用我们只需要源点到目标点的最短距离，所以我们等于额外做了很多工作，如果不对那些当前用到的数据进行记录，那么就等于做了很多无用功。因此，我们可以额外设置一个路径缓存，用于记录每次查询后得到的结果，当缓存中存在最短路径时就可以直接返回最短路径，大大节省了时间，提高了代码的效率。

 

UML类图和作业架构

因为最具有代表性和普适性，所以我以第三次作业为例来对作业架构进行说明。我们也能将类分为用户需求类和异常类：用户需求类包含MyPerson，MyNetwork，MyMessage，MyGroup，MyEmojiMessage，MyNoticeMessage，MyRedEnvelopeMessage；异常类包含MyEqualPersonIdException，MyEqualRelationException，MyRelationNotFoundException，MyEqualGroupIdException，MyEqualMessageIdException，MyGroupIdNotFoundException，MyPersonIdNotFoundException，MyEmojiIdNotFoundException，MyEqualEmojiIdException，MyMessageIdNotFoundException。

另外，当我们重点观察用户需求类时，从图中我们可以看出，本次作业主要可以分为Network、Group、Message、Person四个模块，而Person和Value可以认为代表着这张社交网络无向图中的节点和边。为了保证每个模块之间耦合性的最小化，我们要做的就是将输入的指令具体分配到相应的模块，尽量让它们独自完成数据的操作和存储；但必要时由于在低耦合度和高性能之间的权衡，也有可能会出现增加耦合度的数据的缓存这一现象的出现。而Group类则可以认为是因为客户需求造成的新类，它将一部分人从全体中分割出来并对其相关性质和参数进行研究。最后，Message类则是用于记录节点之间的信息传递，需要依赖Person和Network两个类协助完成相关操作。

对于图的存储，我们采用的是经典的邻接表的数据结构：

public class MyPerson {private HashMap<Integer, MyPerson> acquaintance;　 //我的熟人
    private HashMap<Integer, Integer> value;　　　　　  //与熟人之间的边权
}

public class MyNetwork {
    private HashMap<Integer, MyPerson> people;         //人的总体
}

所以在这其中，Person是为了实现社交网络图中具体每个节点和边的增删改查，而Network则是用来描述整个社交网络的情况，是我们可以从整体来观察查询整个社交网络的基本情况。

以下几个问题是本单元中的重点问题：

连通块数目查询：对于该问题，我的策略是每加入一个新结点则连通块数目加一；当两个结点之间建立关系时，若它们不属于同一连通块，则连通块数目减一。这种策略有两个方法实现，一种就是通过并查集来实现；另一种是采用二维HashMap，其中每个二阶HashMap中存储的就是以恶搞连通域中的所有节点。

最短路径查询：可以选择采用堆优化的Dijkstra算法，并且由于Dijkstra算法每次得到的是源点到所有顶点的最短距离，而每次调用我们只需要源点到目标点的最短距离，所以我们等于额外做了很多工作，如果不对那些当前用到的数据进行记录，那么就等于做了很多无用功。因此，我们可以额外设置一个路径缓存，用于记录每次查询后得到的结果，当缓存中存在最短路径时就可以直接返回最短路径，大大节省了时间，提高了代码的效率。

而对于底层结构，具体使用何种容器来维护相关数据并可以优化代码性能，上面的“容器选择”已经做过说明。

 

bug与体会

其实第三单元作业看似难度较低，其实隐藏着很多的陷阱，在完成它的过程中需要万分小心，在这三次作业的历程中，我主要在queryBlockSum、valueSum、Dijkstra算法三个地方出现了超时的bug。究其原因，主要还是我当时只是注重于正确性的验证而忽视了对于性能问题的探究。其中第三次作业的教训格外惨痛，我也明白了不要想当然，不要偷懒，要关注课程组的更新，要反复阅读jml，要对自己的每一个方法进行时间复杂度的分析的道理，在下一单元的作业中我一定会投入时间，更加认真地完成作业。

此外，我也认识了JML这个强大的工具：只需要对前置条件、后置条件、副作用以及不变式进行约束，在顶层将实现的功能用数理逻辑进行精确的描述。相较于我们从前的注释语言，它更规范，没有歧义，能够被机器识别，并且在实现时我们可以只关注于局部的要求，大大简化了程序员之间的分工合作，减小了程序开发的难度。但是有时候JML的可读性并不是很好，不能让人很快地理解方法的目的。希望在以后更深一步的学习中我可以了解更多有关JML的知识，可以熟练地使用JML这个当前已经发展成熟的世界通用的工具链。

 此外，TDD思想和Junit在debug中的应用也进一步开阔了我的眼界和思路，激起了我对于JML的兴趣，我也会利用空闲时间进行进一步的学习。