BUAA-OO Unit3 JML规格

第三单元的作业主要是根据给出的接口和JML规格实现一个可以进行分组、发送不同种类信息、统计可达性、最短路径和相关数据的小型社交系统，应用到了一些图的相关知识。总体而言，实现JML规格完成大部分功能难度并不大，但在细节上容易发生疏漏；而性能的优化也是一个考察点。

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

实现规格主要分为以下几步：

• 阅读指导书和接口中各个方法的功能，理解整个系统的结构和每个方法的用途。

• 分析规格中类的属性（即JML规格中public instance model部分），选择合适的数据结构存储数据。

• 根据设计的数据结构依次按照JML规格实现方法。

由于JML规格只规定需要的数据类型、前置条件和后置条件，因此在实际实现过程中有许多需要自己设计的地方，特别是容器的选择，应当在整体考虑后提前选择合适的容器再实现方法，否则再改动比较麻烦，也容易出错。

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

Junit测试

Junit是通过编写测试代码来测试程序的JAVA单元测试框架，可以判断程序执行的结果是否和预期一致。在本次作业中，我主要利用AssertEquals对社交系统中一些计算的方法进行了比较简单的测试，熟悉了IDEA中Junit的基本语法和操作。

黑箱测试

黑箱测试不考虑程序内部结构和特性，只检查程序的输出信息。

在本次作业中，我主要采用的是黑箱测试，利用C语言书写了一个简单的评测机，首先随机生成一定量（10^3数量级）的addPerson、addMessage和addRelation指令构建社交网络，然后随机生成各种其他指令共数万条，利用批处理运行jar包与其他同学的代码对拍检验正确性。同时，在评测机中输出一次测试所需的时间，大概估计是否会造成TLE。对于产生TLE的情况，通过手动构造大量某一指令的数据观察执行时间，以此判断哪个方法产生了严重的性能问题，再有针对性地进行优化。

这样的测试应用简单，但由于数据是随机生成的，具有偶然性，并不能保证程序的完全正确。

3 容器选择和使用的经验

容器选择

JML规格中并不会指定容器的选用，而程序的最终性能与容器的选择很大程度上相关，因此容器的选择对于本单元作业来说非常重要。

对于需要大量查找操作的数据而言，如果使用List遍历查询会严重影响性能，此时应该选用Hashmap，通过哈希表降低查找操作消耗的时间。

对于要求插入顺序的数据而言，应当使用数据相对位置不会改变的List或者LinkedHashMap。

此外，根据元素是否可以为空、是否需要按升降序排序等要求还需要选择不同的容器，但本单元作业没有涉及。

下面给出本单元第三次作业中采用的容器：

Person

acquitance：HashMap<id, queryValue> 储存与一个人有关系的人的id和queryValue。方便判断一个人与另一个人有无关系并获取value。

messages: ArrayList<Message> 储存一个人收到的信息。由于需要进行头插，保留插入顺序，选用了ArrayList。

Group

people: HashMap<id, Person> 储存这个组中人的id和person类。由于需要进行大量查询某人是否在这个组内的操作，因此选用HashMap加快查询速度。

Network

people: HashMap<id, Person> 储存所有人的id和person类。

groups: HashMap<id, Group> 储存所有组的id和group类。

messages: HashMap<id, Message> 储存所有信息的id和message类。

emojiHeatList: HashMap<id, heat> 存储表情id以及表情id对应的表情使用次数。

此外，在dijkstra算法中使用了优先队列PriorityQueue。

使用经验

HashMap

• HashMap.containsKey的底层实现是遍历，其实可以用HashMap.get(Key) == NULL取代来改善性能。

• 当一个Key值不存在于HashMap中，HashMap.get()返回的是空指针，此时对空指针进行操作就有可能产生NullPointerException异常。因此在使用返回对象之前，应当先判断是否为空。不过在本单元中，产生空指针异常的原因多半是其他方法实现有误。

• 对HashMap.values 遍历时如果需要用到remove()，使用iterator是最简单的方式。

4 性能分析

本单元对性能的考察主要在第二次作业isCircle方法和第三次作业sendIndirectMessage方法算法的使用。

isCircle

本方法需要判断无向图中的两个点是否联通。第一次书写时我使用了DFS方法，结果严重超时；此后改用了并查集算法。并查集适用于需要反复查找一个元素在哪个集合中的问题，在本次作业中，我们将无向图中相连的点划分为一个集合，选择其中一个节点作为树的根节点，并进行路径压缩，即每个节点的父节点都为根节点。

在作业中，我将集合内id最小的点作为父节点。使用HashMap<sonId, parentId> parent 来储存每个人的id和他们所对应的父节点id。在执行addRelation添加关系时，将父节点设置为两人父节点中id较小的那个，并遍历HashMap更新父节点id。

public void addRelation(int id1, int id2, int value) throws PersonIdNotFoundException, EqualRelationException {
    ...
    if (parent.get(id1) < parent.get(id2)) {
        changeParent(parent.get(id2), parent.get(id1));
        queryBlockSum--;
    } else if (parent.get(id2) < parent.get(id1)) {
        changeParent(parent.get(id1), parent.get(id2));
        queryBlockSum--;
    }
}
void changeParent(int id1, int id2) {
    for (Integer i : parent.keySet()) {
        if (parent.get(i) == id1) {
            parent.put(i, id2);
        }
    }
}           

queryBlockSum()方法的实现也是利用并查集。

sendIndirectMessage

本方法主要考察求无向图两点之间最短路径问题。利用基于优先队列的dijkstra算法可以使复杂度达到O(nlogn)。优先队列PriorityQueue实际上是利用完全二叉树实现的小顶堆，每次使用peek()函数都可以取出队列中权值最小的元素，且复杂度为O(1)。基于优先队列的dijkstra算法相对于基于邻接矩阵的dijksra算法（复杂度为O(n^2)）有很大的性能提升。

int dijkstra(MyPerson person1, MyPerson person2) {
        PriorityQueue<MyPerson> waitList = new PriorityQueue(new Discomparator());
        HashMap<Integer, Integer> linkedpeople = person1.getAcquaintance();
        person1.setDistance(0);
        for (Integer each : linkedpeople.keySet()) {
            MyPerson toPerson = (MyPerson) getPerson(each);
            toPerson.setDistance(person1.queryValue(toPerson));
            waitList.add(toPerson);
        }
        while (true) {
            if (((Person) waitList.peek()).equals(person2)) {
                break;
            }
            MyPerson per1 = waitList.poll();
            int distance1 = per1.getDistance();
            HashMap<Integer, Integer> linkedpeople1 = per1.getAcquaintance();
            for (Integer each : linkedpeople1.keySet()) {
                MyPerson per2 = people.get(each);
                int distance2 = linkedpeople1.get(each);
                if (per2.getDistance() == -1) {
                    per2.setDistance(distance1 + distance2);
                    waitList.add(per2);
                }
                else if (distance2 + distance1 < per2.getDistance()) {
                    waitList.remove(per2);
                    per2.setDistance(distance2 + distance1);
                    waitList.add(per2);
                }
            }
        }
        int finalvalue = person2.getDistance();
        for (Integer each : people.keySet()) {
            people.get(each).setDistance(-1);
        }
        return finalvalue;
    }

其他

除此之外，getValueSum()如果直接使用遍历也可能超时，可以在Group类中维护一个valueSum属性，当添加/删除人或添加关系时更改这个属性，以优化性能。

5 作业架构设计

作业的整体架构基本由接口和JML规格给出，其中MyRedEnvelopeMessage、MyEmojiMessagge、MyNoticeMessage继承自MyMessage，减少代码复用。除了接口要求的类外，还额外设计了Discomparator类，使用了Comparator接口，用于优先队列。

 

 

 

6 心得体会

 

本单元作业学习了JML规格的基本语法。按照JML规格大致实现方法并不困难，但是许多细节容易出现疏漏，比如JML中冗长的条件理解和异常抛出的顺序等。此外，如果不事先阅读整个系统架构、理解需要维护的属性和每个方法的含义，很有可能用不恰当的方法实现规格。等到完成所有方法之后再回来修改需要耗费很多不必要的时间。

本单元对性能的优化也让我对容器的理解进一步加深了。java容器中的方法虽然便于使用，但是如果不了解这些方法的底层实现，容易造成一些不必要的性能问题。