2022_OO第三单元总结

一、架构分析

1.hw9 基础架构和基本功能的搭建

  hw9作为第三单元的第一次作业，基本上还是带我们熟悉jml的基础语法，搭建好整体的框架，实现一些基础功能，并在此基础上进行一些简单的优化。

基础架构

  hw9中每个类的结构大致如下：

//MyNetwork
public class MyNetwork implements Network {
private HashMap people;
private HashMap groups;
private DisjointSetUnion dsu;
public MyNetwork() {
people = new HashMap<>();
groups = new HashMap<>();
dsu = new DisjointSetUnion();
}
...
}
//MyGroup
public class MyGroup implements Group {
private int id;
private ArrayList

people;
public MyGroup(int id) {
this.id = id;
this.people = new ArrayList<>();
}
...
}
//MyPerson
public class MyPerson implements Person {
private int id;
private String name;
private int age;
private ArrayList

acquaintance;
private ArrayList value;
public MyPerson(int id, String name, int age) {
this.id = id;
this.name = name;
this.age = age;
this.acquaintance = new ArrayList<>();
this.value = new ArrayList<>();
}
...
}


性能优化

  hw9中出现了 query_circle 和 query_block_sum 两种指令。query_circle 就是询问两个点是否联通。query_block_sum 是询问图里的连通块数量。考虑到没有删改边的指令，我选择了实现并实时维护一个并查集。

  这样在接收到 query_circle 命令时，直接调用并查集，判断两个person的父节点是否相同即可；而且维护并查集时也能顺便解决 query_block_sum 命令，只要在并查集中存储一个int类型的值sum，初始为0，每加入一个节点sum就+1，每合并一个节点sum就-1，这样该命令的时间成本就均摊在维护并查集的过程中，相比jml给的基本策略，只需要O1就能获取sum值，大大提高了效率。

  当然并查集中也有相应的优化，比如路径压缩和按秩合并等等，我使用的是按两边节点个数合并，原理与按秩合并大致相同。

2.hw10 加入message并实现进阶功能

  hw10沿用了hw9搭建的架构，增加了MyMessage类，实现了与message相关的一些更高级的功能。

基础架构

  hw10中每个类的结构大致如下：

//MyNetwork
public class MyNetwork implements Network {
private HashMap people;
private HashMap groups;
private HashMap messages;
private MyDisjointSetUnion dsu;
private ArrayList values;
public MyNetwork() {
people = new HashMap<>();
groups = new HashMap<>();
messages = new HashMap<>();
dsu = new MyDisjointSetUnion();
values = new ArrayList<>();
}
...
}
//MyGroup
public class MyGroup implements Group {
private int id;
private HashMap people;
public MyGroup(int id) {
this.id = id;
this.people = new HashMap<>();
}
...
}
//MyPerson
public class MyPerson implements Person {
private int id;
private String name;
private int age;
private int money;
private int socialValue;
private ArrayList

acquaintance;
private ArrayList value;
private ArrayList messages;
public MyPerson(int id, String name, int age) {
this.id = id;
this.name = name;
this.age = age;
mOney= 0;
socialValue = 0;
this.acquaintance = new ArrayList<>();
this.value = new ArrayList<>();
this.messages = new ArrayList<>();
}
...
}
//MyMessage
public class MyMessage implements Message {
private int id;
private int socialValue;
private int type;
private Person person1;
private Person person2;
private Group group;
public MyMessage(int messageId, int messageSocialValue,
Person messagePerson1, Person messagePerson2) {
type = 0;
group = null;
id = messageId;
socialValue = messageSocialValue;
person1 = messagePerson1;
person2 = messagePerson2;
}
public MyMessage(int messageId, int messageSocialValue,
Person messagePerson1, Group messageGroup) {
type = 1;
person2 = null;
id = messageId;
socialValue = messageSocialValue;
person1 = messagePerson1;
group = messageGroup;
}
...
}


  可以看出，类的变化大部分是围绕message相关。

性能优化

  hw10中出现了 query_least_connection 指令。这个指令的含义是询问图中包含某个点的最小生成树的边权和。

  基于hw9中已经实现了并查集，并且没有负数边，所以这里可以直接使用kruskal生成最小生成树。由于指令可以随时加入新的边，如果要动态维护最小生成树的话，则需要每加一个边就重新生成一个树，时间成本比较高，所以这里我选择了现用现生成的策略，接收到 query_least_connection 指令后才生成树，进行最小边的计算。

3.hw11 message相关子类高级功能的实现

  hw11引入了几种不同的message子类，如通知消息、红包消息等，在此基础上将sendMessage等方法进一步细分，并对优化有了更高的要求。

基础架构

//MyNetwork
public class MyNetwork implements Network {
private HashMap people;
private HashMap groups;
private HashMap messages;
private HashMap emojiList;
private MyDisjointSetUnion dsu;
private ArrayList values;
public MyNetwork() {
people = new HashMap<>();
groups = new HashMap<>();
messages = new HashMap<>();
dsu = new MyDisjointSetUnion();
values = new ArrayList<>();
emojiList = new HashMap<>();
dsu.addValues(values);
}
...
}
//MyGroup 同hw10
//MyPerson 同hw10
//MyMessage 同hw10
//MyNoticeMessage
public class MyNoticeMessage extends MyMessage implements NoticeMessage {
private String string;
public MyNoticeMessage(int messageId, String noticeString,
Person messagePerson1, Person messagePerson2) {
super(messageId, noticeString.length(), messagePerson1, messagePerson2);
string = noticeString;
}
public MyNoticeMessage(int messageId, String noticeString,
Person messagePerson1, Group messageGroup) {
super(messageId, noticeString.length(), messagePerson1, messageGroup);
string = noticeString;
}
...
}
//MyEmojiMessage
public class MyEmojiMessage extends MyMessage implements EmojiMessage {
private int emojiId;
public MyEmojiMessage(int messageId, int emojiNumber,
Person messagePerson1, Person messagePerson2) {
super(messageId, emojiNumber, messagePerson1, messagePerson2);
emojiId = emojiNumber;
}
public MyEmojiMessage(int messageId, int emojiNumber,
Person messagePerson1, Group messageGroup) {
super(messageId, emojiNumber, messagePerson1, messageGroup);
emojiId = emojiNumber;
}
...
}
//MyRedEnvelopeMessage
public class MyRedEnvelopeMessage extends MyMessage implements RedEnvelopeMessage {
private int money;
public MyRedEnvelopeMessage(int messageId, int luckyMoney,
Person messagePerson1, Person messagePerson2) {
super(messageId, luckyMoney * 5, messagePerson1, messagePerson2);
mOney= luckyMoney;
}
public MyRedEnvelopeMessage(int messageId, int luckyMoney,
Person messagePerson1, Group messageGroup) {
super(messageId, luckyMoney * 5, messagePerson1, messageGroup);
mOney= luckyMoney;
}
...
}


  可以看出，本次作业的架构和优化，大多都是基于新的message子类要求的。

性能优化

  hw11中出现了 send_indirect_message 指令，需要求消息的双方的最短路。由于数据要求符合，可以直接使用Dijkstra算法。

  除此之外，Dijkstra算法还能进行堆优化，直接使用java自带的容器PriorityQueue即可，很简单，但是可惜当时没有想到优化，也没注意仔细看讨论区，早早过了中测就没再打开，强测丢了一个点，很可惜。

二、测试数据

手动测试

  仔细看代码，寻找jml中的一些坑点，同时不能放过异常处理，全面编写数据进行测试；

  另外还要对性能进行测试，如最小生成树算法等等，有的指令不进行细致的优化就有可能TLE。

自动测试

  随机生成强测代码，可以一次生成很多针对一个点的数据，进行集中测试，也可以生成全面数据，全面测试，个人感觉还是集中测试更容易发现bug。

三、Bug分析

  hw9中强测没有发现bug，但互测中发现了一个bug，具体原因是判断是否存在id前就进行了get操作，导致取到了空指针报错。

  hw10中强测互测均未发现bug。

  hw11中强测互测都发现了一个bug，就是Dijkstra算法忘记优化导致了TLE，不再赘述。

四、NetWork扩展

题目描述

假设出现了几种不同的Person

• Advertiser：持续向外发送产品广告


• Producer：产品生产商，通过Advertiser来销售产品


• Customer：消费者，会关注广告并选择和自己偏好匹配的产品来购买 -- 所谓购买，就是直接通过Advertiser给相应Producer发一个购买消息


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

拓展

  Advertiser、Producer 和 Customer 可以设计为 Person 的子类，继承 Person 的属性；Advertisement 和 BuyMessage 可以设计为 Message 的子类，继承 Message 的属性。

发送广告：

生产商生产产品：

购买商品：

五、心得体会

  本单元三次作业相对前两单元难度降低了不少，主要是让我们了解规格化设计，熟悉基于jml的规格模式。jml确实给了很明确的目标和架构，不用自己搭建架构和设计方法，少走了很多弯路，也让我对jml有了更深的理解。

  这几次作业也带我们回顾了大一程设和数据结构里学到的一些知识，涉及了时间复杂度的计算，甚至到后来有的方法在优化时直接换了架构，比如有的方法原先需要调用子类中的方法，但优化后直接在父类中解决即可，也就是说抛弃了子类中的某些方法。这让我更加体会到，在给定的规格下，内部的实现可以是多种多样的。

  经过一单元的学习，在我看来，jml优缺点都很明显。jml的优点就体现在本单元的难度上，由于jml清晰地传递了需求甚至具体方法，没有自然语言的二义性，比其他oo作业（还有os）的要求明确的多，不用猜测含义，即使第一次没看明白也可以通过反复阅读解决；另外，jml缺点也很明显，没有二义性带来的副作用就是表达啰嗦，有时候一句话的要求，读jml中能要看几十行才能看明白是要干嘛（比如sendMessage），所以后来有的描述过长的方法是通过看方法名猜目的，然后再阅读jml检查自己的判断准不准确，这对jml编写者和使用者都是一个很大的挑战。

  由此看来，如果要想把所有的函数的效果全部用JML描写，则会带来巨大的复杂性，所以在实际应用中到底是选择效率高但是可能有歧义的自然语言，还是使用极其准确但可能相对复杂得多的jml，还是有待考虑。