OO第三单元JML
0 前言
本单元的重点或者说想要实现的基础点应该是，学会阅读、理解和简单的写一写JML这种契约式编程，做类似工业上的从设计到正确性验证(助教替我们完成了)到写代码到写测试的全流程分析。
对于JML这种语言本身我一向是不喜欢做太多评价的，不喜欢用就不用，未必是它本身的好坏。但是这种从自然语言到JML(认为是一类契约式语言)再到写测试这一个流程，却反倒让我期待以后自然语言编程了（x
另外一点是，除了需要实现的基础点外，我们为了保证性能还会考虑很多的算法设计来减少时间复杂度。
1 测试过程分析
1.1 黑箱白箱测试
黑箱测试又被称为功能测试，是一种不考虑内部结构和实现的软件测试方法，只关注软件的输入和输出，验证软件功能是否符合预期。黑箱测试的主要目是验证软件的功能需求，检查程序是否能正确运行。
黑箱测试是确保软件质量的重要方法，能发现很多设计或需求不明确导致的问题。但同时，由于黑箱测试并不关注代码的具体实现和内部结构，因此有一些问题（例如资源泄漏，难以复现的错误）可能不能通过黑箱测试发现。因此，黑箱测试通常和其他测试方法（例如白箱测试）结合使用。
在本次作业中，我们搭建的评测机，从生成数据到相互比对输出结果，实际上就是一种典型的黑箱测试。但是由于输入的局限性，导致还是有一些bug没有测出来，哭😢
白箱测试，又被称为结构测试、透明箱测试或者玻璃盒测试，是一种软件测试方法，它要求测试者理解被测软件的内部工作机制，了解程序的内部结构，包括主要的代码，逻辑判断和程序路径，然后基于这个理解来设计和实施测试用例。
白箱测试可以让你发现一些隐藏的问题，例如死代码（不会被执行到的代码），逻辑错误，漏洞等等。
在本次作用中，每个人在完成互相阅读代码实际上就是一种白箱测试。互测中，如果相互是通过检查代码然后构造特定数据的实际上也是一种白箱测试。
1.2 多种测试思路分析
在软件测试的流程中，需要不同的测试类型相互协同，共同确保软件的质量。在早期阶段，单元测试和功能测试帮助我们发现并修复问题；在代码全部整合起来后，我们需要进行集成测试和系统测试来确保各个模块可以正确协同工作；在发布前，我们可能需要进行压力测试以确保软件在高负荷下依然可靠；在软件的维护阶段，回归测试将帮助我们保证修改后的代码不会影响到已有功能。
1.2.1 单元测试
单元测试是指对软件中的最小可测试单元进行检查和验证。对于面向对象编程，这个单元就是方法，但也可以是过程或函数。单元测试主要用于开发阶段，确保每个部分都正常工作。它可以帮助检查和修复程序中的早期错误，将大大减少调试的时间。
对于每个小的单元，我们可以再去选择使用黑箱测试和白箱测试的办法来进行测试。比如Junit基本上就是使用的黑箱测试的办法进行测试，通过多次数据生成和结果比对进行测试。假设我们有一个Java程序，其中有一个类MathUtils，它有一个add方法，用来进行两个数的加法运算：
public class MathUtils {
public static int add(int a, int b) {
return a + b;
}
}为了进行单元测试，我们可以创建一个测试类，使用JUnit等测试框架来编写测试方法：
import static org.junit.Assert.assertEquals;
import org.junit.Test;
public class MathUtilsTest {
@Test
public void testAdd() {
int result = MathUtils.add(1, 2);
assertEquals(3, result);
}
}在testAdd方法中，我们测试了MathUtils.add方法，参数是1和2，预期的结果是3。assertEquals是一个断言方法，如果MathUtils.add(1, 2)的结果不等于3，那么这个单元测试就会失败。
这样的单元测试可以大大提高代码质量，因为它允许开发者在早期阶段就发现和修复错误，也可以作为文档来说明代码的预期行为，还可以促进开发者写出更加模块化、可测试的代码。
1.2.2 功能测试
功能测试又称为黑盒测试，主要是从用户的角度进行的，关注的是最终结果是否符合预期的功能。它不关心软件内部逻辑和结构，仅通过操作用户界面，验证软件功能是否正常。
在功能测试中，我们要做的往往在于构造数据。构造数据的强度则决定了这个测试的好坏，因此也是后续会提到的如何更好的构造数据来对相应工程或者每个单元(类和方法等)进行测试。
1.2.3 集成测试
集成测试是在所有模块逐个测试的基础上，进行联合测试，以便发现模块间的错误和问题。它主要目的是确保各个模块能够正确地协同工作。
在进行集成测试时，我们通常采取增量的方式，每次将一个新的模块添加到一个已经进行过测试的模块组中，并进行测试。
例如：你在开发一个电商网站，网站的主要功能包括用户注册、登录、浏览商品、添加购物车、提交订单等模块。每个模块单独开发完成后，你都会进行单元测试，确保它们的功能实现是正确的。然后，你需要进行集成测试，一步一步的将这些模块组装在一起。
首先，你可能会集成用户注册和登录模块，测试用户注册后能否成功登录；然后再集成商品浏览模块，测试登录后的用户能否正常浏览商品；然后再集成添加购物车模块，测试用户能否将商品添加到购物车中；最后，集成提交订单模块，测试用户从浏览商品到提交订单的整个购物流程是否都能正常进行。
集成测试是软件开发中非常重要的一个步骤，它能帮助你发现各个模块间交互时可能存在的问题，然后针对这些问题进行修复，确保整个系统的稳定性和可靠性。
比如在这次hw11中出现了 qtvs的bug，或许就是因为没做好集成测试，导致后续新加的方法对原先的动态维护产生了影响。
1.2.4 压力测试
压力测试是通过模拟大量、超出软件规定的负荷或者测试环境进行测试，以确定其性能的稳定性和可靠性。目的是调整优化系统的性能，以便在高负载环境下正常工作。
在U2的时候或许体会更加深刻，当某一时刻到达多个进行时如何处理。这一单元主要是对于内存和cpu运行时间的挑战，如何应对一些极端数据以及针对极端数据的优化。
1.2.5 回归测试
在修改了旧代码或者添加了新代码后，回归测试可以确保软件的原有功能仍然可以正常工作。回归测试的目的是发现在修改和介入新模块后引入的错误或方案中遗漏的错误。
回归测试可以是手动执行，也可以是自动执行。在大型和快速迭代的项目中，自动化的回归测试能大大提高效率。这通常需要一个稳定的，自动化的测试套件和持续集成（Continuous Integration）环境。
比如我们在作业迭代过程中，不能因为迭代影响到了之前的程序，这也和程序设计的方法相关。
1.3 数据构造
我们构造数据主要是围绕上面提到的方法进行构造。
针对黑箱测试，可以使用数据生成器，随机生成各种数据，来保证能够实现基本的功能。
针对单元测试，在本单元不同指令间的关系不是很紧密，我们可以构造以某一类数据为主的数据来进行测试。
针对压力测试，可以设计更加极端的数据进行构造。包括数据范围是int，构造接近Integer_MAX、Integer_MIN的数据来进行测试。构造一些很大的数据，确保能够在给定的时间空间内完成要求。
2 架构设计
本单元由于已经设计好了JML规格化的描述，我们对于架构的设计也不是重点。
除了一些大家都有的，讲一下我自己特色的两个设计，一个是使用了一个MyNetwork里面的一个内置类Edge来存储边，同时改写了hashCode和equals方法，优化了边的存储结构。
同时使用了一个Checker类，它本身也是自己的工厂，这里用到了单例模式的饿汉式加载。专门来处理某些异常的情况。
2.1 层次化设计
本次用到了Network中有很多Person，Person中很多有Tag，每个Tag中又有Person，同时Network中有很多Message，每个人有很多Message这个层次化的结构。
我们在设计时，尽量不要逆层次来进行操作，可能出现奇怪的bug。
2.2 图的存储与维护
这里的核心是MyNetwork中的
public static final HashMap<Integer, Person> persons = new HashMap<>();和MyPerson中的
private final HashMap<Integer, Person> persons = new HashMap<>();也就是这里是一个邻接表的结构。
这里也能够想办法使用邻接矩阵的办法，但是考虑到空间等因素，似乎都不是最优解。
人与人之间的关系通过在某个Person的persons里面put / remove即可。
然后这里还有需要维护的是Edge，其实本不必存储Edge，但是由于后续我用到了并查集，需要在重建并查集时使用。
private final HashSet<Edge> edges = new HashSet<>();
class Edge {
private int id1;
private int id2;
public Edge(int id1, int id2) {
this.id1 = id1;
this.id2 = id2;
}
@Override
public boolean equals(Object obj) {
Edge edge = (Edge) obj;
return (edge.id1 == id1 && edge.id2 == id2) ||
(edge.id1 == id2 && edge.id2 == id1);
}
@Override
public int hashCode() {
return (Math.min(id1, id2) * 31 + Math.max(id1, id2)) % 1000000007;
}
public int getId1() {
return id1;
}
public int getId2() {
return id2;
}
}这里和Pair这个数据结构不同，使得这里的边是实实在在的无向边。
这里相关的系数也是调试了几次后选的相对比较好的。（或许能够有更好的。。。
2.3 规格与设计分离
规格与设计分离的原则是指在软件开发过程中，我们可以分别独立地描述软件的“什么”和“如何”。即，我们将软件的功能需求或业务逻辑（即规格）与软件的实现细节或内部结构（即设计）显示地分离开。
它的主要思想是：
- 规格（或需求）描述了软件应该做什么，也就是它需要提供哪些功能，如何满足用户的需求。规格通常包括数据校验，业务规则，数据转换和处理，用户界面逻辑等。
- 设计描述了如何实现这些功能，包括软件的结构，类或函数的设计，选择何种算法等实现细节。
在面向对象的设计中，这种原则尤为重要，为了体现这种原则，我们通常把规格抽象出接口，而将设计和实现写在具体的类中。即，接口定义了规格，类提供了设计和实现。这使得我们可以在不改变接口的情况下改变内部实现，也能在不改变内部实现的情况下增加新的接口。
这种分离的好处是：
- 提高了软件的可维护性和可读性，因为更改需求或设计时，只需要关注一部分代码，减少了复杂性。
- 提高了软件的可扩展性和灵活性，因为可以在不改变已有设计的前提下添加新功能，或者在不改变已有功能的前提下改变内部实现。
- 增强了模块化，可以更好地实现高内聚低耦合的原则。
- 方便进行单元测试和集成测试，因为可以分别对规格和设计进行测试。
3 性能与算法
3.1 数据结构
-
这里大多数使用的是
HashMap这个数据结构，可以快速查找。这里有个小细节
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public HashMap(int initialCapacity, float loadFactor) {}也就是在新建
HashMap的时候可以设置开始的容量和负载因子。负载因子说的是当使用的元素超过这个比例后会重新分配一次。可以尝试调参&炼丹 -
在后续添加的
message那里，由于涉及头插法，因此建议使用LinkedList这个数据结构，会比ArrayList的效果更好。在
ArrayList中add(0, message1)是会把后面的元素重新复制一遍，复杂度较高。public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }而在
LinkedList中只需要处理一下类似指针的操作，复杂度为O(1)。
3.2 公式优化
queryTagAgeVar指令中，我们需要计算年龄的方差，但是没必要根据JML中的循环来计算，而是可以维护agePowSum和ageSum替换成下面的代码：
public int getAgeVar() {
if (persons.isEmpty()) {
return 0;
}
int ageMean = ageSum / persons.size();
// 考虑到java向下的负数取整是-1.25 -> -1 (不完全是向下取整),不能将ageMean * ageMean * persons.size()提出去
return (agePowSum - 2 * ageMean * ageSum + ageMean * ageMean * persons.size()) / persons.size();
}这样就可以降低时间复杂度。同时这里还需要注意一些细节，比如在注释中提到了不能将ageMean * ageMean * persons.size()提出去。
3.3 动态维护
本次作业中，很重要的一个优化方法就是动态维护。动态维护实际上是将一些中间变量进行保存。
这里还想进一步分析一下。
实际上这种动态维护会发现，比如说我在
addRelation的时候，本来只需要添加到对应的HashMap里面就可以了，但是这样我还得要么加到一个缓冲区buffer里面，要么进行多余的计算。单对这一个指令来说无疑是
在queryBlockSum、queryTripleSum、queryTagValueSum、queryCoupleSum等指令中，如果我们每次查询都是将图遍历一遍，那么时间复杂度大大提高，具体问题可能超过$O(n^3)$，这是我们不能接受的。
对于BlockSum是用到了并查集进行优化。
并查集，也称为不相交集合（Disjoint-Set），是计算机科学中处理一些不交集类问题的一种主要数据结构，它管理一系列不相交的集合，并支持将两个集合合并为一个集合，以及查询元素属于哪个集合的功能。并查集的主要操作包括：
大体理解就是，每个集合找一个代表，每个人都只认识那个代表，比较的时候只需要进一步比较那两个代表是不是同一个集合或者同一个人即可。
- 创建并查集：开始时，每个元素都在只包含自己的集合中，这些集合可以通过一个一维数组来表示，数组的索引表示元素，数组的值表示各个集合的代表元素。
- 查询操作（Find）：这个操作可以查找给定元素属于哪个集合，通常通过查找其“代表元素”（或“集合的根”）来完成。在一个集合内的所有元素都链接到该集合的代表元素。
- 合并操作（Merge）：这个操作可以将两个集合合并为一个集合，通常通过将一个集合的代表元素链接到另一个集合的代表元素下实现。
由于并查集支持非常高效的合并和查询操作，因此在很多含有大量查询和合并操作的问题中，首选使用并查集。
在MyNetwork中维护一个
private final HashMap<Integer, Integer> roots = new HashMap<>();在addPerson的时候把自己添加进去。
roots.put(person.getId(), person.getId());同时在添加关系的时候进行merge操作。
/**********************并查集*************************/
private int find(int id) {
if (roots.get(id) == id) {
return id;
}
roots.put(id, find(roots.get(id)));
return roots.get(id);
}
private void merge(int id1, int id2) {
int root1 = find(id1);
int root2 = find(id2);
if (root1 == root2) {
return;
}
roots.put(root2, root1);
blockSum--;
}
private void reBuild() {
blockSum = roots.size();
roots.forEach((key, value) -> roots.replace(key, key));
edges.forEach(edge -> merge(edge.getId1(), edge.getId2()));
}这里有rebuild是因为涉及到并查集的重建。
这里也正是因为需要重建的关系，可能不如dfs。
也是我在这一小节最开始提到的，不同的算法实际上实际时间分配到了不同的地方，因此都有可行的地方。
那么有了并查集之后，每次添加一个人，也就是进行addPerson，那就增加一个block。
然后再查询的时候设置了一个是否需要重建的因子，如果涉及到了删除边，那么就需要重建并查集，此时我们可以等到需要查询的时候在重建，实现懒重建。
同时在merge的时候如果两个人本来不在一个集合中，那么就需要减少一个block。
public void addPerson(Person person) throws EqualPersonIdException {
...
blockSum++;
}
public int queryBlockSum() {
if (needReBuild) {
reBuild();
needReBuild = false;
}
return blockSum;
}对于TripleSum是每次增加一个关系或者删去关系，进行遍历，检查是否需要修改。
addRelation和modifyRelation的时候分别重新修改一下tripleSum
public void addRelation(int id1, int id2, int value){
...
tripleSum += queryThree((MyPerson) persons.get(id1), (MyPerson) persons.get(id2));
}
public void modifyRelation(int id1, int id2, int value)
throws PersonIdNotFoundException, EqualPersonIdException, RelationNotFoundException {
if (persons.get(id1).queryValue(persons.get(id2)) + value <= 0) {
tripleSum -= queryThree((MyPerson) persons.get(id1), (MyPerson) persons.get(id2));
...
} else {
...
}
}
/**********************检查三角形*************************/
private int queryThree(MyPerson person1, MyPerson person2) {
if (person1.getPersonSize() < person2.getPersonSize()) {
return person1.queryThree(person2);
} else {
return person2.queryThree(person1);
}
}对于TagValueSum也是在每次添加关系、修改关系和删去关系时都需要进行调整。
这里我自己有一个优化(似乎没什么用)，就是添加了一个
buffer，每次在tag里面添加一个人，我先不计算新的tagValue，先放到buffer里面。
/**
* 用于为valueSum的求解进行缓冲。
* 等到需要用到value sum的时候在进行添加。
*/
private final HashMap<Integer, Person> personBuffer = new HashMap<>();
public int getValueSum() {
for (Person person : personBuffer.values()) {
// 前一部分与后一部分
persons.forEach((key, value) ->
valueSum += personBuffer.containsKey(key) ? 0 : value.queryValue(person) * 2);
// 后一部分之间
personBuffer.forEach((key, value) ->
valueSum += value.queryValue(person));
}
personBuffer.clear();
return valueSum;
}同时删除的时候进行一下判断。
其实也就这里会是唯一比不加
buffer有优势的地方了！！！
public void delPerson(Person person) {
if (personBuffer.containsKey(person.getId())) {
personBuffer.remove(person.getId());
} else {
persons.forEach((key, value) -> valueSum -=
personBuffer.containsKey(key) ? 0 : value.queryValue(person) * 2);
}
}对于CoupleSum这个，可以给每个人维护一个bestId。
这样的话最佳情况就是O(n)，是可以接受的。
public int queryCoupleSum() {
coupleSum = 0;
for (Person person : persons.values()) {
if (((MyPerson) person).getPersonSize() == 0) {
continue;
}
if (((MyPerson) (persons.get(((MyPerson) person).getBestAcquaintance())))
.getBestAcquaintance() == person.getId()) {
coupleSum++;
}
}
return coupleSum / 2;
}这里注意在维护的时候要注意数据范围。
如果明年我当助教肯定要在这里埋个坑。樂（x
3.4 算法优化
包括前面的并查集其实也可以认为是算法优化。
这里主要是指在维护每个人的bestId的时候可以使用优先队列或者堆的思想，可以将$O(n)$变为$O(log(n))$。但是这里的话，从我打超算的角度认为是很好的一个优化，但是从一个做算法题的角度，能过就行。那么从$O(n)$变为$O(log(n))$在这里时间能够运行的情况下是完全没有必要的。
4 Junit测试
利用JML设计Junit
JML，是一种行为界面规范语言，用于详细的说明 Java 中类和接口应该如何表现。它可以用于为 Java 方法和类编写规格。然后，这些规格可以与测试工具（如 JUnit）配合使用，来验证代码是否满足 JML 规格。
在 JML 中，我们可以针对方法的行为进行描述，例如方法的前提条件（requires）、后置条件（ensures）、不变性（invariant）等等。
使用 JML，我们可以根据这些描述生成适合于 JUnit 的测试用例，然后使用 JUnit 来运行这些测试。
关于具体编写，我的Junit测试可以分为这么几步：
-
首先设计数据规格和对象初始化
private Network network = new MyNetwork(); private HashMap<Integer, Person> persons = new HashMap<>(); private HashMap<Integer, Tag> tags = new HashMap<>(); private Random random = new Random(System.currentTimeMillis()); private int personNum = 50; private int tagNum = 50; private int relationNum = 1000; private int emojiNum = 5; private int personPerTag = 10; private int messageNum = 100; private int emojiMessageNum = 50; private int emojiMessageSendNum = 10; private static int testNum = 50;这里的
network实际上就是主要测试对象，而其他的是我们自己存储的拷贝对象。 -
搭建数据生成器，用最开始设计的数据的规模生成大量随机数据；
genAddPerson(); genAddRelation(); genAddTag(); genStoreEmoji();由于我们这里其实不需要生成所有类型的指令，只需要其中几个即可。
-
将翻译JML得到的标准答案与执行指令得到的答案进行比较；
-
检查执行指令前后是否符合JML中的ensures等要求。
-
注意需要检查
pure这种，包括还有那些not_assigned的值。
Junit与JML的一致性
JML（Java Modeling Language）和JUnit都是用于Java程序的工具，但它们解决的问题并保证代码质量的方法是不同的。
JML是一种行为界面规范语言，可以通过注释的形式为Java程序提供规格说明。JML提供了稳定、详细的规格，用于描述程序各部分预期的行为。例如，你可以使用JML为Java类或方法注解一个先决条件（pre-condition）、后置条件（post-condition）或者类不变性（class invariant）。JML规范可以通过静态检查或者运行时断言来进行验证。
再来看JUnit，JUnit是Java的一种单元测试框架，它通过编写测试用例，然后运行这些测试用例，验证程序的实际行为是否符合预期行为。JUnit完全依赖于程序员编写的测试用例，其准确性和覆盖率取决于测试用例的质量。
那么JML和JUnit之间的关系是什么呢？简单来说，一致性来自于它们都是在描述软件应该如何运行。JUnit测试实际行为，而JML描述预期行为。一致性的证明过程则相当于是在比较预期行为与实际行为。例如，当你有一个JML规格的后置条件为@ensures \result >=0，并且你有一个JUnit测试用例没有符合该后置条件（得到的结果为负数），这时一致性就被破坏了。
更深入一步，我们可以利用JML规格自动生成JUnit测试用例，然后通过运行这些用例来验证程序符合JML规格的要求。这使得JML和JUnit可以无缝配合，有效地提高了代码质量的保证和验证效率。
5 学习体会
这一单元，对于一个在计院待了差不多一年，经历了大一的磨练的来说应该是不难的。
我在最前面也提到了，本单元的重点应该是学会阅读、理解和简单的写一写JML这种契约式编程。但是不知道是基于什么考量，本单元我们需要关注更多的是怎么去优化，怎么去考虑更好的算法。
这让我联想到了大一上的程序设计的课程，那时我啥都不会，那个课程也是目的是为了让我们学习C语言的基础语法，但是涉及到很多算法层面的内容。
这两者都有一个共同点，就是似乎总是想要通过某种手段分出一个孰优孰劣出来，但是忽略了我们只是需要完成基本的需求即可。
我这里并不是对OO这个课程有任何看法，我始终觉得这个是一个绝世好课。
我只是觉得大学真的有必要通过这个超出基本需求的要求来对学生进行评判吗。
害，不说了，终究是我太菜了，菜就多练吧
对于JML本身，我觉得它是一个非常有效的工具，可以大大提高Java程序的质量和可维护性。首先，通过在代码中添加JML注释，我们可以明确规定方法的预期行为，包括前置条件、后置条件、不变性等。这为我们提供了一种非常明确的方式来表达我们的意图，并定义代码应当如何执行。其次，JML可以帮助我们发现代码中的错误，而且能够在非常早的阶段就发现这些错误。当我们编写了JML注释后，可以使用JML的工具来静态检查我们的代码，看看代码是否满足我们的预期。这可以在实际运行代码之前就找出很多潜在的问题。再者，JML也支持运行时检查。通过JML，我们可以生成可以在运行时检查的断言。这对于找出一些难以复现的bug，或者是一些只有在特定情况下才会出现的问题非常有帮助。同时，JML还可以帮助我们自动生成测试用例。只要我们为代码编写了详细的JML注释，就可以通过工具自动产生JUnit的测试用例。这对于保证代码质量，提高测试效率都非常有帮助。综上所述，我认为JML是一个非常强大且有用的工具。它可以帮助我们更好地理解我们的代码，提高代码质量，以及提高我们的开发效率。
