oo第三单元作业总结
规格实现策略
本单元我实现规格时按照以下步骤
-
阅读规格，理解含义
首先可以很明显的将规格分为两部分，异常部分和正常功能部分。
对于正常功能部分，由于JML的严谨性，很简单的意思需要比较长的叙述，所以我会用回车将其分开，并标注好这部分干了什么，如：
/*@ public normal_behavior
@ requires !(\exists int i; 0 <= i && i < people.length; people[i].equals(person));
@ assignable people;
@ ensures people.length == \old(people.length) + 1;
//容器长度+1
@ ensures (\forall int i; 0 <= i && i < \old(people.length);
@ (\exists int j; 0 <= j && j < people.length; people[j] == (\old(people[i]))));
//原有元素保留
@ ensures (\exists int i; 0 <= i && i < people.length; people[i] == person);
//含有新元素person
@ also
@ public exceptional_behavior
@ signals (EqualPersonIdException e) (\exists int i; 0 <= i && i < people.length;
@ people[i].equals(person));
@*/
//异常部分
2.实现异常部分
异常部分只需在方法开头用条件语句结构判断即可，之后便不再需要考虑
3.选择实现方式
由于JML其实只规定了输入和结果，具体实现可以*发挥，所以在阅读规格，理解方法需要实现的功能后，选择合理的实现方式，当然也可以无脑按照规格中类似多重循环的实现方式，但性能会很尴尬。
所以要在完全理解规格的基础上合理选择容器和算法。
例如本单元中有多个需要计算集合中元素某属性之和的方法，按照规格实现的话每次获取都需要遍历所有元素将指定属性相加，但我们完全可以将计算移到添加元素时完成，这样获取时只需要一个return语句。
测试策略
直接阅读代码
由于本单元需按照JML写代码，所以大家的整体结构基本一致，只有具体方法实现不同，那么直接看代码就是比较有效的方式。
对于本单元来说，这个方法可以很快的发现性能问题。
最明显的是 isCircle queryBlockSum这两个方法，可以很快的看出是否优化了实现方式，如果出现了搜索、多重循环，那么构造一个含有多条上述指令的数据点就能成功hack。
评测机随机测试
主要用来测试正确性，（也可以设置大量的添加人和关系再查询来测试性能），随机测试可以测出一些比较明显的正确性问题，但是也存在一些问题很难测试出来的情况。
针对性构造测试
对于一些涉及多个属性、对象、类的方法，可以针对性测试。
如queryGroupValueSum方法，该方法涉及到组中成员与成员之间的关系，我为了优化性能，在添加组员时计算ValueSum，但是忽略了关系的可添加性，若先加入组，再添加组员间的关系，需要更新ValueSum。
还有deleteColdEmoji方法，该方法既要删除表情，又要删除含有满足条件表情的消息，可以构造多个指令测试是否正确删除，是否有多删、漏删的情况。
容器的选择
本单元中我只使用了两种容器：
-
Arraylist
-
HashMap
只要是对顺序没有要求的情况，我优先HashMap，因为访问快速，对于contains、get类方法来说很合适（HashSet也可）
当然，如果有数据有对应关系，那更需要用HashMap,如Emoji的id与heat
需要注意的是关于HashMap遍历删除的问题，需要用到迭代器
Iterator<Map.Entry<Integer, Integer>> it = emojiHeatMap.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, Integer> entry = it.next();
if (entry.getValue() < limit) {
it.remove();
}
}
如果需要考虑顺序，则使用Arraylist，如getReceivedMessages，需要严格按照顺序给出收到的消息。
性能分析
本单元作业我没有出现性能问题，主要的可能出现性能问题的方法是查询、统计类的方法，分析如下：
-
isCircle
该方法需要查询两个点是否可达，如果使用最常见的搜索，那么显然是容易超时的，我使用了并查集算法，引入了祖先节点的属性，我按照点的添加顺序规定辈分高低，在添加点连线时（addrelation）更新相关点的祖先节点，那么判断是否可达时只需判断两个点的祖先节点是否相同，也就是O（1）的复杂度。
-
queryBlockSum
理解代码后可以知道该方法是查询联通图的个数，同上所说，只需遍历一次查询有多少个节点的祖先节点是自身即可，复杂度O（n）
-
sendIndirectMessage
该方法需要查询最短路径，那么直接使用dijkstra即可解决，还可以使用Java自带的PriorityQueue实现堆优化
-
getAgeMean/getAgeVar
计算平均值和方差都可以通过在添加和删除时更新总和以及平方和来优化
平均值：ageSum / people.size(); //ageSum为总和
方差：(age2Sum + people.size() * getAgeMean() * getAgeMean()-2 * getAgeMean() * ageSum) / people.size();
//age2Sum为平方和
此时两方法的复杂度均为O（1）
架构设计
MyPerson
private int id;
private String name;
private int age;
private int socialValue;
private HashMap<Integer, Integer> map;
private ArrayList<Message> messages;
private int family;
private ArrayList<Integer> groups;
private int money;
该类维护了三个容器，map用来存link的person以及value，messages用来存收到消息并保留原有顺序，goups存加入的Group均在构造时初始化，add时更新。
family用来存祖先节点，代表所属家族，在addrelation时判断辈分并更新相关的所有节点的family
MyGroup
private int id;
private ArrayList<Person> people;
private int valueSum = 0;
private int ageSum = 0;
private int age2Sum = 0;
该类维护了一个容器，people，用来存组中成员，忘记改成HashMap或HashSet, 性能更好。
valueSum ageSum age2Sum 在add remove时更新，便于相应值的访问
MyNetwork
private ArrayList<Person> people;
private HashMap<Integer, Integer> idMap;
private HashMap<Integer, Group> groupMap;
private HashMap<Integer, Message> mesMap;
private HashMap<Integer, Integer> emojiHeatMap;
维护五个容器，people用来存放节点，idMap记录节点id与队列位置的对应关系，通过它可以得到节点的位次，判断节点的辈分大小，用于更新祖先节点
groupMap mesMap emojiHeatMap功能基本相同，存放id与对应对象，便于存取
心得体会
本单元主要训练对JML的理解以及规范实现，难度较低，但是做到完全不出错却很难，很有可能漏掉细节，对本地测试有很高的要求。
本单元虽需要严格按照规格实现，但给了很大*发挥空间，实现优化，我的注意力基本放在了一些优化上，对于细节方面没有在意，导致出现一些小错误，而且过分依赖评测机，以为对拍了就没问题，结果还是有严重BUG。
本单元的学习还使我对各种容器的使用更加熟练，总结后也发现了本次作业中不足的容器选择。还有图相关算法的使用也得到了训练，总体来说体验很好，不是那么累但又练了很多、学了很多。