BUAA OO 第三单元总结

规格实现策略

本单元的重中之重，便是对于JML规格理解与代码实现

理解并规格的时候，我一般分为下面的几个步骤：

1、先通读一遍规格，结合方法名与具体规格，理解类每个方法的大致功能并简要记录。重点理解方法之间的调用关系，方法之于类的作用等。个人认为不宜读完一个方法就实现一个方法，这样的话对于整个类没有整体观，比如适合当前方法的数据结构未必适合整个类。通读完一遍整个类，甚至所有类，然后才能作出最适合的结构选择。

2、先实现比较简单类规格，比如异常等。因为比较简单的类，往往是较为复杂的类的成员，或者会出现再较为复杂的类的实现中，先解决这些简单的类，对于复杂的类的处理也能更清晰一些。

3、实现比较复杂类的方法，仔细阅读分析规格，对于规格很长很复杂的方法，可以适当对于规格作一些分类。注意区分前置条件、后置条件、不变式等内容。括号层数太多时，注意括号的对应，不然有可能出现理解偏差。注意不要死板地照搬规格实现，规格的表述方法往往是”基础表述“，使用最简单的数据结构，所以复杂度较高。我们应该理解规格，在规格理解正确的情况下，通过更为优秀的数据结构与算法，优化性能。

测试思路

Junit测试

在第三单元的训练中，我学习了Junit测试相关的内容，对于如何进行Junit测试有了了解，在HW1和HW2中也有所使用，但感觉由于方法较多，加上编写Junit测试程序不太熟练，导致测试效率较低，迫于时间原因，并没有进行详尽的Junit测试，而是以找同学使用自动评测机对拍为主。

自动评测机对拍

我和另外两位同学，进行了自动评测机对拍，评测机是同学写的，是C语言编写的，主要功能是生成数据到.txt文件并运行.bat文件对jar包进行自动评测。

第一次作业

作业简介

实现简单社交关系的模拟和查询，学习目标为 入门级JML规格理解与代码实现。

StarUML图与类结构

由于此次作业提供了官方接口，MyPerson、MyGroup、MyNetwork类中很多成员变量与方法都相同。

为了更加简明，也便于后面的总结，对于实现较为固定的成员变量和接口中已经定义的方法，就不作展示了。

以下UML类图展示的是，笔者新定义的方法与个性化实现的数据结构。

容器选择

MyPerson类：

规格：

@ public instance model non_null Person[] acquaintance;
@ public instance model non_null int[] value;

acquaintance为与该Person有直接联系的熟人，value为二者连接的权值。考虑到Person有唯一标识id，为了方便查找，采用了HashMap的数据结构。

private Map<Integer, Person> acquaintance = new HashMap<>();
private Map<Integer, Integer> value = new HashMap<>();

MyGroup类：

规格：

@ public instance model non_null Person[] people;

考虑到Person有唯一标识id，为了方便查找，采用了HashMap的数据结构。

private Map<Integer, Person> people = new HashMap<>();

MyNetwork类：

规格：

@ public instance model non_null Person[] people;
@ public instance model non_null Group[] groups;

对于groups，还是为了方便查找，采用HashMap的数据结构。

private Map<Integer, Group> groupList = new HashMap<>();

对于people，由于方法isCircle和queryBlockSum的要求，采取了并查集的算法，建立了并查集UnionSet类，将Person[] people包含在了UnionSet类中。而UnionSet则代替people成为MyNetwork的成员变量。

性能优化

1、使用HashMap的containsKey方法来提高对于List形式数据的查找效率。

public boolean isLinked(Person person) {
    if (id == person.getId()) {
        return true;
    }
    return acquaintance.containsKey(person.getId());
}

2、使用动态维护Group sumAge与sumAge2的方法来优化年龄计算相关方法。

在向组内加入新人时，更新sumAge与sumAge2的值

public void addPerson(Person person) {
    other things to do
    sumAge += person.getAge();
    sumAge2 += person.getAge() * person.getAge();
}

组踢人时，同样也需要更新

public void delPerson(Person person) {
    other things to do
    sumAge -= person.getAge();
    sumAge2 -= person.getAge() * person.getAge();
}

3、判断两点是否可达和输出连通子图数目，采用按秩合并的并查集的算法

建立了并查集类UnionSet

MyPerson类新增成员属性fatherid和rank

具体的并查集算法参考了网络和讨论区

Find操作（查找操作）

 Find(x) 伪码
     if x.parent == x
        return x
     else
        return Find(x.parent)

Union操作（合并操作）

 Union(x, y) 伪码
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot == yRoot
         return
 	if xRoot.rank < yRoot.rank
     	xRoot.parent := yRoot
 	else if xRoot.rank > yRoot.rank
     	yRoot.parent := xRoot
 	else
     	yRoot.parent := xRoot
     	xRoot.rank := xRoot.rank + 1

程序分析

度量分析

OCavg=Average opearation complexity（平均操作复杂度）

OCmax = Maximum operation complexity（最大操作复杂度）

WMC = Weighted method complexity（加权方法复杂度）

可以看到，类的复杂度均尚可。

方法复杂度分析

CogC = Cognitive complexity（认知复杂度）

ev(G) = Essential cyclomatic complexity（基本圈复杂度）

iv(G) = Design complexity（设计复杂度）

v(G) = cyclonmatic complexity（圈复杂度）

可以看到，我自行编写的方法的复杂度均尚可。

Bug分析

公测中的bug

HW1的公测中，我的程序没有被检测出bug。

互测中的bug

HW1的互测中，我的程序没有被检测出bug。我也没发现其他同学的bug。

我的感受

本次作业，我初步学习了基于规格的层次化设计，了解了JML规格，学会了如何读懂JML，如何书写简单的JML，如何基于规格进行程序设计等内容。

初次接触规格，感觉JML的难点主要有两点：一是JML语法，比如各种操作符的含义；二是复杂JML难以理解，有些JML的表达式非常长，又嵌套了很多的\forall，\exists等逻辑较为复杂的子表达式，给理解带来了困难。我解决的主要方法就是，多层嵌套的JML表达式先进行分层，然后就是一遍遍地阅读，搞清楚每一层的含义，也没找到啥特殊的技巧。

第一次作业，所涉及的方法大都比较简单，很多都是10行以内就可以写完的基础功能（get之类的），比较复杂的就是isCircle、queryBlockSum，用到了并查集。在公测和互测中也没出现bug，还是不错的。

第二次作业

作业简介

本次作业，需要完成的目标是进一步实现社交关系模拟系统中的群组和消息功能，学习目标为进一步掌握JML规格的理解与实现。

StarUML图与类结构

由于此次作业提供了官方接口，MyPerson、MyGroup、MyMessage、MyNetwork类中很多成员变量与方法都相同。为了更加简明，也便于后面的总结，对于实现较为固定的成员变量和接口中已经定义的方法，就不作展示了。以下UML类图展示的是，笔者新定义的方法与个性化实现的数据结构。

容器选择

MyPerson类：

private Map<Integer, Person> related = new HashMap<>();

HashMap related是与这个Person连通的所有Person的集合，需要动态维护。

private ArrayList<Edge> edges = new ArrayList<>();

Array List edges是这个Person所在的最大连通子图的所有边的集合，需要动态维护。

Edge类，是新定义的类，代表边，其结构如下：

public class Edge {
    private int personid1;
    private int personid2;
    private int value;

    public Edge(int a,int b,int c) { }

    public int getpersonid1() { }

    public int getpersonid2() { }

    public int getvalue() { }
}

性能优化

1、使用HashMap的containsKey方法来提高对于List形式数据的查找效率。

public boolean isLinked(Person person) {
    if (id == person.getId()) {
        return true;
    }
    return acquaintance.containsKey(person.getId());
}

2、使用克鲁斯卡尔+并查集求最小生成树（queryLeastConnection）

MyNetwork类中新定义的数据结构：HashMap<Integer,Integer> ids = new HashMap<>(); 用于并查集计算。

MyPerson类中新定义的数据结构：ArrayList edges = new ArrayList<>(); 用于表示边的集合。

由于克鲁斯卡尔算法的要求，edges被定义为权值递增的，在更新时，需要依照权值大小插入到List指定位置。

并查集优化的克鲁斯卡尔算法（C）：
int S[NUM];                                   //并查集
struct Edge {int u, v, w;} edge[NUM*NUM];     //定义边
bool cmp(Edge a, Edge b)  { return a.w < b.w; }
int find(int u) { return S[u] == u ? u : find(S[u]); }	//查询并查集，返回u的根结点
int n, m;     //点，边
int kruskal() {
        int ans = 0;
        for(int i=1; i<=n; i++)
			S[i]=i;                     //初始化，开始时每个点都是单独的集
        sort(edge+1, edge+1+m, cmp);
        for(int i = 1; i <= m; i++) {
            int b = find(edge[i].u);    //边的前端点u属于哪个集？
            int c = find(edge[i].v);    //边的后端点v属于哪个集？
            if(b == c) continue;        //产生了圈，丢弃这个边
            S[c] = b;                   //合并
            ans += edge[i].w;           //计算MST
        }
        return ans;
}

程序分析

度量分析

OCavg = Average opearation complexity（平均操作复杂度）

OCmax = Maximum operation complexity（最大操作复杂度）

WMC = Weighted method complexity（加权方法复杂度）

可以看到，MyNetwork类的复杂度较高，其余类均尚可。MyNetwork类新增了许多方法，可能导致其加权方法复杂度较高。

方法复杂度分析

CogC = Cognitive complexity（认知复杂度）

ev(G) = Essential cyclomatic complexity（基本圈复杂度）

iv(G) = Design complexity（设计复杂度）

v(G) = cyclonmatic complexity（圈复杂度）

可以看到，MyNetwork.addRelation(int, int, int)和MyNetwork.sendMessage(int)复杂度较高，其余方法的复杂度均尚可。

Bug分析

公测中的bug

HW2的公测中，我的程序没有被检测出bug。

互测中的bug

HW2的互测中：发起 hack: 9/35 受到 hack: 6/11

其中我hack到别人的bug是：1、qgvs方法超时；2、qgav方法超时

我被hack到的bug是：qgvs方法超时（同质bug×6）

超时的原因是：使用了两层循环硬算。

bug修复策略：改为动态维护valueSum变量。

我的感受

本次作业，我进一步学习了类规格及其测试考虑，了解了前置条件、后置条件、不变式等内容，并了解了基于它们的规格测试方法，初步接触了Juint基于规格的测试。

此次作业新增了Message类，Message的收发等内容，由于消息分类别并各有要求等原因，其细节要求较多。新增的qlc方法，为了避免超时，用到了并查集优化的克鲁斯卡尔算法。

然后qlc费半天劲写了优化，结果在HW1就完成了的qgvs方法上翻车了。我根本就忘记了测试HW1写好但未评测的那些方法，只测试了新方法，造成了被hack，要吸取教训。

第三次作业

作业简介

本次作业，需要完成的目标是进一步实现社交关系系统中不同消息类型以及相关操作，学习目标是理解JML规格在面向对象设计与构造中的重要意义，并掌握利用JML规格提高代码质量的能力

StarUML图与类结构

由于此次作业提供了官方接口，MyPerson、MyGroup、MyMessage、MyNetwork类中很多成员变量与方法都相同。为了更加简明，也便于后面的总结，对于实现较为固定的成员变量和接口中已经定义的方法，就不作展示了。以下UML类图展示的是，笔者觉得有必要展示的新定义的方法与个性化实现的数据结构。

容器选择

MyNetwork类：

规格：

@ public instance model non_null int[] emojiIdList;
@ public instance model non_null int[] emojiHeatList;

规格中EmojiMessage分为了idList和HeatList，在实际实现中，可以用一个HashMap代替：

private HashMap<Integer,Integer> emojiIdHeat = new HashMap<>();

其中key为emojiid，value为对应的heat。

在deleteColdEmoji中，找到了冷门表情后，需要将该冷门表情对应的消息移除，所以需要让每一种表情与其对应的消息集合有对应：

private HashMap<Integer, HashSet<Integer>> emojiId2Messageid = new HashMap<>();

性能优化

1、使用HashMap的containsKey方法来提高对于List形式数据的查找效率。

public boolean isLinked(Person person) {
    if (id == person.getId()) {
        return true;
    }
    return acquaintance.containsKey(person.getId());
}

2、使用动态维护emojiId2Messageid的方式，使得查找某种表情对应的消息集合变得方便。

private HashMap<Integer, HashSet<Integer>> emojiId2Messageid = new HashMap<>();

3、使用邻接表+优先队列的dijkstra求最短路径。

邻接表+优先队列的dijkstra算法（C）：

struct edge{
    int from, to, w;	//边：起点，终点，权值。起点from并没有用到，e[i]的i就是from
    edge(int a, int b,int c){from=a; to=b; w=c;}
};
vector<edge>e[NUM];  		 //用于存储图
struct s_node{
    int id, n_dis;           //id：结点；n_dis：这个结点到起点的距离
    s_node(int b,int c){id=b; n_dis=c;}
    bool operator < (const s_node & a) const
    { return n_dis > a.n_dis;}
};
int n,m;
int pre[NUM]; 			   //记录前驱结点
void dijkstra(){
	int s = 1;             //起点s是1
    int  dis[NUM];         //记录所有结点到起点的距离
    bool done[NUM];        //done[i]=true表示到结点i的最短路径已经找到
    for (int i=1;i<=n;i++) {dis[i]=INF; done[i]=false; }    //初始化
    dis[s]=0;                        //起点到自己的距离是0
    priority_queue <s_node> Q;       //优先队列，存结点信息
    Q.push(s_node(s, dis[s]));       //起点进队列
    while (!Q.empty())   {
        s_node u = Q.top();          //pop出距起点s距离最小的结点u
        Q.pop();
        if(done[u.id])				 //丢弃已经找到最短路径的结点。即集合A中的结点
            continue;
        done[u.id]= true;
        for (int i=0; i<e[u.id].size(); i++) {    //检查结点u的所有邻居
            edge y = e[u.id][i];             	  //u.id的第i个邻居是y.to
            if(done[y.to])                		  //丢弃已经找到最短路径的邻居结点
                continue;
            if (dis[y.to] > y.w + u.n_dis) {
                dis[y.to] = y.w + u.n_dis;
                Q.push(s_node(y.to, dis[y.to]));  //扩展新的邻居，放到优先队列中
                pre[y.to]=u.id;          		  //如果有需要，记录路径
            }
        }
    }
}

我新定义了类Ele，其作用类似于上述代码的s_node结构，记录了结点id和该节点到起点的距离distance。

程序分析

度量分析

OCavg = Average opearation complexity（平均操作复杂度）

OCmax = Maximum operation complexity（最大操作复杂度）

WMC = Weighted method complexity（加权方法复杂度）

可以看到，MyNetwork类的复杂度较高，其余类均尚可。MyNetwork类新增了许多方法，可能导致其加权方法复杂度较高。

方法复杂度分析

CogC = Cognitive complexity（认知复杂度）

ev(G) = Essential cyclomatic complexity（基本圈复杂度）

iv(G) = Design complexity（设计复杂度）

v(G) = cyclonmatic complexity（圈复杂度）

可以看到，MyNetwork.sendMessage(int)、MyNetwork.addRelation(int, int, int)、MyNetwork.sendIndirectMessage(int)方法复杂度较高，其余方法的复杂度均尚可。

Bug分析

公测中的bug

HW3的公测中，我的程序没有被检测出bug。

互测中的bug

HW3的互测中：发起 hack: 2/21 受到 hack: 0/2

我找到的bug是：有一位同学qlc方法，在处理对象时出现了NullPointerException异常。

我的感受

本次作业，我进一步学习了类型层次规格与验证等内容。

本次作业消息的种类变多了，增加了表情消息、红包消息、通知消息三个消息类型，各有各的特殊要求，因此在发送消息等操作中，需要进行的条件判断也不少，规格的理解也更加困难了。因为消息类别细分了，原有的一些处理消息方法在本次作业也发生了变化，需要仔细甄别变化之处。

此次作业是OO课程的最后一次互测机会，也比较幸运，成功hack到了bug。OO课程的互测任务到此也告一段落了，之前的每一次互测，都可以说是暗流汹涌。无论是通过读代码的方式，还是通过构造数据的方式，对别人的代码进行查错，都是一项紧张刺激的工作，一天之中，也充满了hack到别人的兴奋，和发现自己被hack了的遗憾。总体来说，还是有所收获的，在hack别人与自己被hack后修复bug的过程中，也学到了很多。

Network 扩展

题目要求

假设出现了几种不同的Person

• Advertiser：持续向外发送产品广告
• Producer：产品生产商，通过Advertiser来销售产品
• Customer：消费者，会关注广告并选择和自己偏好匹配的产品来购买 -- 所谓购买，就是直接通过Advertiser给相应Producer发一个购买消息
• Person：吃瓜群众，不发广告，不买东西，不卖东西

如此Network可以支持市场营销，并能查询某种商品的销售额和销售路径等 请讨论如何对Network扩展，给出相关接口方法，并选择3个核心业务功能的接口方法撰写JML规格（借鉴所总结的JML规格模式）

扩展思路

Advertiser、Producer 和 Customer 可以继承 Person 的接口

题目提到了广告的概念，可以对Message进行扩展，新增广告信息类Advertisement、购买信息类BuyMessage。

AdvertiseMessage 和 BuyMessage 可以继承 Message 的接口。

Advertiser类

由于Customer需要通过Advertiser给相应Producer发一个购买消息，故Advertiser应该需要记录自己代理的商品，以及相对应的Producer。

新增类的成员属性：HashMap<Integer,Integer> myAdvertiseMap，key为商品id，value为Producer的id。

Producer类

需要记录自己都销售哪些产品。

新增类的成员属性：List myProducts

Customer类

消费者有自己的偏好

新增类的成员属性：偏好-List myFavors

新增类的成员属性：购物车-List myGoods

AdvertiseMessage类

广告信息，需要提供产品的偏好，以供人选择。

新增类的成员属性：int favor

新增类的成员属性：int productId

BuyMessage类

需要告知广告商，自己要买的产品编号是什么。

新增类的成员属性：int productId 存的是对应商品id

JML规格

设置偏好

/*@ public normal_behavior     
  @ requires contains(personId);
  @ requires getPerson(personId) instance of Customer;  
  @ requires !getPerson(personId).containsFavor(favor);      
  @ ensures (\forall int i; 0 <= i && i < \old(myFavors.length);
  @          (\exists int j; 0 <= j && j < myFavors.length;myFavors[j] == 			          
  @           (\old(myFavors[i]))));
  @ ensures (\exists int i; 0 <= i && i < myFavors.length; myFavors[i] == favor);
  @ also
  @ public exceptional_behavior
  @ signals (PersonIdNotFoundException e) !contains(id);
  @ signals (PersonTypeWrongException e) !(getPerson(personId) 
  @                                       instance of Customer);
  @ signals (EqualFavorException e) getPerson(personId).containsFavor(favor);
  @*/    
public /*@ pure @*/void addFavor(int personId, int favor);

投放广告

/*@ public normal_behavior      
  @ requires containsAdvertise(id);      
  @ assignable advertiseMessageList;      
  @ ensures !containsAdvertise(id) && advertiseMessageList.length == 				       
  @          \old(advertiseMessageList.length) - 1 &&      
  @           (\forall int i; 0 <= i && i < \old(advertiseMessageList.length) &&             
  @             \old(advertiseMessageList[i].getId()) != id;      
  @         	 (\exists int j; 0 <= j && j < advertiseMessageList.length;                   
  @               advertiseMessageList[j].equals(\old(advertiseMessageList[i]))));      
  @ ensures (\forall int i;0 <= i && i < people.length;(people[i].isCustomer() && 	
  @	     people[i].containsFavor(\old(getMessage(id).getFavor())) ==>   
  @           (\exists int j; 0 <= j && j < people[i].myGoods.length; 
  @            people[i].myGoods[j] == \old(getMessage(id))) && 
  @           (\forall int j; 0 <= j && j < \old(people[i].myGoods.length);
  @            (\exists int k; 0 <= k && k < people[i].myGoods.length; 
  @             people[i].myGoods[k] == (\old(people[i].myGoods[j])))));
  @              ensures (\forall int i; 0 <= i && i < people.length; 
  @               people[i].isCustomer() ==> !people[i].containsFavor(id);    
  @ also
  @ public exceptional_behavior
  @ signals (AdvertiseIdNotFoundException e) !containsAdvertise(id);
  @*/    
 public void sendAdvertisement(int id);

清空购物车

/*@ public normal_behavior
  @ requires contains(personId);
  @ requires getPerson(personId) instance of Customer;      
  @ assignable getPerson(personId).myGoods;          
  @ ensures (\forall int i; 0 <= i && i < 
  @          \old(getPerson(personId).myGoods.length); 
  @           sendBuy(getPerson(personId).myGoods.get(i))); 	
  @            ensures getPerson(personId).myGoods.length == 0;   
  @ also
  @ public exceptional_behavior
  @ signals (PersonIdNotFoundException e) !contains(id);
  @ signals (PersonTypeWrongException e) !(getPerson(personId) 
  @                                       instance of Customer);
  @*/    
 public void payforAlltheItems(int personId);