前言

由于涉及了图以及图上的算法，本次作业的难度较高。难点主要在于单源最短环的查找方式。

本次作业添加了几个新的 Message 种类：EmojiMessage，NoticeMessage，RedEnvelopeMesssage。均按照规格写，无需过多改动此前的代码。

需要进行改动的代码主要是 NetWork 中的 addMessage 类和 sendMessage 类，需要针对不同的消息类型做出对应的处理。

此外需要完成单源最短环的查找（queryLeastMoments）。

第十一次作业设计

重点谈谈对于单源最短环的设计吧：

起初，我的设计是删边法 + 最短路：

对于起点 i，假如点 j 与 i 直接相连，则删掉此边后查询 i 和 j 之间是否仍然存在路径。若存在路径，则一个可能的最短环值就是 $u_{i,j}+Dijkstra_{i,j}$，遍历所有与起点直接相连的点即可找到最短环。

这个做法易于理解，实现起来并不复杂，我本来打算就用这个写法来着。当我按照这个设计写完之后，经过计算、考虑和询问助教后，认为这个方法的时间复杂度比较危险。按照我的预计，有可能会 t 掉 1-2 个点。（后来我交了一下这个做法发现果然会 t 掉一个点）

本来想着就这样算了，但是后来在周末的时候又觉得有点点不甘心，于是就对原来的方法进行了优化。

优化的方法参考了讨论区内的帖子和 CSDN 上的博客，在此不进行正确性证明，只描述一下我的实现方式：

首先以源点开始跑一遍 dijkstra 算法，能够得到图上所有点到源点的最短路的值。在跑最短路的过程中记录每个点和其父节点，最终我们可以得到一颗以源点为祖节点的生成树：

树图

然后我们在树中尝试添加一条边来构造最短环。这条边的两个顶点不能处于同一颗子树下，否则生成的环路中不包含源点。

设源点为 o。于是对于树中的每一个定点 i，选择的边的另一个顶点 j 有两种情况：

  1. j 是源点且 i 的父节点不是源点（若是源点则无环）。
  2. j 是其他子树上的定点。

树图2

对于第一种情况，得到的环值为 $Dijkstra_{o,i}+u_{o,i}$。对于第二种情况，得到的环值为 $Dijkstra_{o,i}+Dijkstra_{o,j}+u_{i,j}$。

遍历所有树上的顶点即可得到最短环值。

在实现过程中，为快速判断两个顶点是否是同一颗子树下，可以使用并查集。这部分可以复用以前的并查集代码。在实现 dijkstra 的过程中可以利用 Java 的优先队列进行优化。

伪代码

这里给出我实现 qlm 的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int id;                             // 源点id
HashMap<Integer, Integer> nodes;    // 存储点到源点的距离
HashMap<Integer, Integer> preId;    // 存储每个点的父节点
DisjointSet diffTree;               // 存储不同子树的并查集
int ans = -1;                       // 存储答案
dijkstra(id, nodes, preId);
preIds.forEach((nowId, preId) -> {  // 存储子树
            if (preId != id) {
                diffTree.merge(nowId, preId);
            }});

for (Person person: people.values()) {
    if (person.hasPath() && person.id != id) {
        for (int i: person.getAcquaintance().keyset()) { // 所有与当前 person 直接相连的人的 id
            if (i == id) {
                // 判断对应条件，更新 ans
            } else {
                // 判断对应条件，更新 ans
            }
        }
    }
}
if (ans == -1) {
    // throw sth
}
return ans;

OKTest

本次作业的 OKTest 要求我们对 deleteColdEmoji 方法进行 OKTest 测试。

难点主要在于理解晦涩的 JML。

bug分析

本次作业没有遇上什么让我值得一记的 bug，强测和互测都顺利通过。

总结

本次作业难度主要体现在 qlm 还有课程组飘忽不定的 JML 上。不得不吐槽的是 OKTest 的 JML 的可读性真的巨差，我时常怀疑是否是我的理解能力出现了问题还是说 JML 的可读性就是这么差劲。后来我用自然语言翻译了一遍 OKTest 的 JML，发现自然语言真是好用多了，帮同学 debug 也不用读 JML 了，主打的叫一个舒服。

黑箱测试与白箱测试

黑箱测试是从软件外部对软件进行测试，只关注输入和输出，不考虑软件是如何实现的。黑箱测试也称为功能测试或数据驱动测试，它主要根据功能需求设计测试用例，检验软件是否能按照规格说明书的要求正常工作。黑箱测试的优点是与软件具体实现无关，如果软件实现发生了变化，测试用例仍可用；缺点是可能遗漏一些内部错误或逻辑缺陷。黑箱测试常用的方法有等价类划分、边界值分析、因果图、决策表分析等。

黑箱测试的优点：

  • 独立性：黑盒测试相对于开发团队是相对独立的，测试人员可以独立进行测试，减少了开发者对测试过程的干扰。
  • 用户导向：黑盒测试从用户的角度出发，关注系统是否满足用户需求和规格要求，能够更好地验证系统的功能和用户体验。
  • 代码无关：黑盒测试不需要了解系统的内部实现细节和代码逻辑，测试人员只需关注输入和输出之间的关系。

黑箱测试的缺点:

  • 遗漏内部错误：由于黑盒测试不考虑系统的内部结构和代码逻辑，可能无法发现由于内部错误或代码缺陷引起的问题。
  • 覆盖范围有限：黑盒测试通常基于需求和规格说明，因此测试用例的设计可能受到这些文档的限制，导致无法覆盖所有可能的情况。
  • 效率低下：由于黑盒测试无法直接访问系统的内部，测试人员需要通过用户界面或其他接口来进行测试，这可能导致测试过程效率较低。

白箱测试的优点：

  • 内部错误发现：白盒测试可以深入系统的内部，检查代码的执行路径、逻辑错误、边界条件等，有助于发现由于代码缺陷引起的问题。
  • 覆盖全面：通过访问系统的内部结构和代码，白盒测试可以设计更全面的测试用例，覆盖不同的代码路径和分支情况。
  • 性能优化：白盒测试可以评估系统的性能瓶颈和资源利用情况，帮助开发团队进行性能优化和调优。

白箱测试的缺点：

  • 依赖开发者技能：白盒测试需要测试人员具备一定的编程和调试技能，以理解代码逻辑并编写相应的测试用例。
  • 开发团队的参与：由于白盒测试通常由开发团队的一部分执行，可能存在开发者对自己代码的偏见，导致测试过程缺乏独立性。
  • 时间和资源消耗：白盒测试需要深入理解系统的内部结构和代码，因此可能需要更多的时间和资源来进行测试和分析。

数据构造策略

本单元在做测试时我主要是针对自己的代码做的白箱测试。通过构造特定的图以及相应的指令来满足覆盖率的要求。这样做测试的针对性较高，基本不到十个数据点即可满足覆盖率的要求。相应的是编写测试点需要耗费较多的精力。

规格与实现相分离

规格与实现分离是一种软件设计的原则，它要求在编写软件需求规格说明时，只描述软件的功能和性能，而不描述软件的内部结构和实现方法。这样可以使软件需求更清晰、更稳定、更容易验证，也可以使软件设计和开发更灵活、更自由、更有创新。

规格是对系统功能、行为和性能的描述，通常以需求规格说明、设计规范或用户文档的形式存在。它们是开发团队与客户、用户之间的合同和共享理解的基础。规格的目的是定义系统应该做什么，而不是如何实现它。

实现是指将规格转化为实际的软件代码和系统组件的过程。它涉及开发者根据规格进行编码、调试、测试和部署的工作。实现的目的是将规格转化为具体的可执行代码，以实现系统的功能和要求。

这个原则实际上我们经常接触；打比方，在做题时题目只给出了要求完成的功能，没有限制实现的方法。我认为这也是一种规格与实现相分离（出题者和做题者之间）。

OKTest 的理解

本单元的 OKTest 要我们对于某些方法的正确性以及副作用按照规格进行检测。实际上是写了一个小型的评测机。

本单元中，我认为 OKTest 的输入输出接口设计得不算太好。虽然课程组使用的 HashMap 能在一定程度上方便代码的编写，但是我认为按照 JML 规格要求的 people-person-(acquaintanceId, value) 来传入数据或许是一个更好的选择。即在第九、十次作业中传入 Person[] people 而非 Hashmap，在第十一次作业中传入 Message[] messages, int[] emojiIdList, int[] emojiHeatList。这样是更容易让人理解，至于建图这种事情，我认为应当交给我们自己做。

单元总结

本单元接触了 JML 语言，让我深深体会到了这种语言的不足与局限性。我来细数一下我在本单元中对 JML 语言体会到的不便：

  1. 同一个意思使用 JML 语言可能会有不同的表达方式，在较大的工程中不同的表达方式会给阅读者带来理解上的困难。比方说，“对于所有 i，都满足条件 cond” 这句话，我们既可以使用 ensures (\forall i; 0 <= i && i <= max; cond)，也可以使用 ensures !(\exist i; 0 <= i && i <= max; !cond)。不同的规格编写者有可能会写出不同的 JML 代码。阅读者在阅读 JML 时，一旦习惯了某一种表述方式，突然更换表述方式则会带来理解上的不便。
  2. JML 代码的正确性依赖于编写者。一旦 JML 代码出现了正确性问题，会带给阅读者深深的烦恼，而且越大的工程在迭代时维护 JML 会带来更大的困难。本单元的 JML 代码可以说是经常出现问题，每次作业都会出现规格上的错误，包括本单元的实验。这给同学们带来了不小的麻烦。
  3. JML 不易描述过于复杂的算法。或者说使用 JML 语言描述过于复杂的算法会让 JML 的体积过于庞大，让阅读者很难提起阅读的兴趣。使用自然语言几句话便可以解释清楚，使用 JML 语言则动辄数十行。这一问题在第十一次作业中的 queryLeastMoments 方法和 sendMessage 中体现的尤为明显。前者由于描述了一个相对比较复杂的算法，在 ensures 中不停地嵌套语句导致可读性降低；后者是由于方法要处理的情况稍稍有些复杂导致 JML 代码的行数足足有六十行。我的做法是读一句翻译一句，将 JML 语言翻译成我能看懂的自然语言，但是这样一来就体会不到 JML 语言的优越性了。
  4. 如果使用自然语言描述方法，那么时隔多日再次回看依然能够快速理解方法要干什么；但是如果使用 JML 语言描述方法，别说时隔多日了，我一边写代码一边都要搞不懂 JML 在说些什么。这个问题在同第三点的两个方法中体现得淋漓尽致。
  5. 阅读和编写 JML 都需要花费额外的学习精力。单单阅读的话还好，编写出好的 JML 则非常需要透彻理解方法并且将方法前后方方面面考虑得仔细透彻才能够写出一个相对合格的 JML 代码。代价未免有些太大了。
  6. JML 增加了迭代难度。在原有函数添加新功能时，其 JML 往往会产生较大的变化，导致阅读者不得不重新开始阅读整个 JML，特别是随着功能的增加，JML 代码长度的增加将导致可读性的降低。

此外写第十一次作业的时候给我一种强烈的写算法题的感觉。这个感觉主要来源于最短环算法的复杂性。如果完全按照课程组的数据范围，则一般的算法难以满足课程组的要求。我们不敢赌课程组的数据强度，也不敢赌到底怎样的时间复杂度能够满足课程组的要求。在这种情况下，我们只好尽可能卷算法。感觉本单元对算法的考察远大于前两个单元（第二单元最复杂的是最短路，远比最短环简单），不知道课程组在单元初说的 “本单元对算法的考察有所减弱，希望大家不要卷错方向~” 体现在哪里。

学习体会

在本单元中大量使用了 HashMap，在第十一次作业中还使用了 PriorityQueue，让我对 Java 对这两种数据结构的支持有了更深入的理解。同时也学会了使用迭代器遍历数组等，以及使用 removeIf() 等简化循环的小技巧。通过一些课外的扩展对 Java 的一些语言特性有了更深入了认知，可以说这段日子我对 Java 的理解更加深入了。