「BUAA OO」Unit-3 JML月

JML - Java Modeling Language

一、背景

叙述JML和题目背景，熟悉的话可以跳过这一部分

1. JML背景

JML是Java Modeling Language的缩写，用于Java的形式化验证和契约式设计。

2. 题目背景

在这次作业中，我们需要模拟和维护一个人际关系网络。

二、题目要求

重述题目要求，熟悉题目可以跳过

第九次作业

和前六次作业不同，这次作业有以下区别：

1. 要求编写Junit4测试，对官方黑盒错误代码进行检查
2. 要求某些类必须实现或继承官方包给出的的抽象类或者接口
3. 要求严格按照官方包中的JML规格实现自己的代码

题目本身而言并不复杂，简单来说就是一带权无向图，并且要支持如下操作：

1. 添加节点
2. 添加边
3. 修改边，包括修改权值和删除
4. 查询两相邻节点连边的权值
5. 查询两节点是否连通
6. 查询图的连通分量的个数
7. 查询图中三阶完全子图的数量

当然，实际上节点就是MyPerson，边就是人与人之间的关系。此外还需要再适当的时候抛出异常。

junit只要求对查询图中三阶完全子图的数量的这一方法，按照JML规格进行测试。OO平台会使用错误的方法写一个MyPerson类，我们需要做的是通过我们写的所有junit 的 @Test 测出平台上的错误方法的bug。

第十次作业

新加入一个MyTag类，每个Tag的意义类似微信中的标签，也就是我可以对好友进行分类，相同的好友可以在不同标签中同时出现。此外，由于我认识我自己，因此我是可以被分到自己的标签下的。每一个标签可以被视作邻接节点生成子图的子图。

标签需要支持以下操作：

1. 为一个人新建一个标签
2. 为一个人删除一个指定标签
3. 添加一个人到标签中
4. 把一个人从标签中删除
5. 查询标签中所有人的年龄的均值
6. 查询标签中所有人的年龄的方差
7. 查询标签中所有边的权重和

此外题目对Person定义了新的操作：

1. 查询认识最好的人。称values中值最大的人中id最小的人为认识最好的人，即bestAcquaintance。

此外题目还为人际网络Network定义了新的操作：

1. 查询两个人的不加权最短路径（也就是说可以bfs）
2. 查询网络中CP的数量。称两个人为CP，如果两人互为对方认识最好的人。

第十一次作业

需要发送消息而已。简简单单。

需求如下：

1. 添加消息
2. 添加表情
3. 发送消息
4. 删除冷门表情

属于是只要读懂题就能写

三、解题思路

这一部分主要叙述主流的解题思路和我采用的解题方法，不想看解题方法的思考过程的可以跳过。

这次作业完全就是数据结构&算法题，所以着重关注数据结构和算法。这次还是和第一次博客一样采用问题驱动型的方式来叙述我的解题思路。

第九次作业

1. 我们有哪些需求？

需求即为第九次作业需要支持的7种操作。此外，题目已经用JML规格为我们规定了一个邻接表，也就是Network中的persons和Person中的acquaintance，分别用来存储节点和节点的邻接节点们。如果用 表示节点数量，用 表示边的数量：

1. 添加节点 直接添加到邻接表
2. 添加边 直接添加到邻接表
3. 修改权值或删除边 修改邻接表就行
4. 查询两邻接节点连边的权值 查邻接表即可
5. 查询两节点是否连通
   1. 深搜广搜
   2. 并查集
   3. 动态树 不会。
6. 查询连通分量的个数
   1. 按照官方包JML 遍历
   2. 并查集 遍历
   3. 维护连通分量个数这一数据结构
7. 查询图中三阶完全子图的数量
   1. 暴力求解 或 或
   2. 维护三阶完全子图的数量这一数据结构

分析后选用并查集来完成题目的解答，我们先看并查集。

2. 怎么使用并查集？

并查集的两个经典的优化分别是路径压缩 Path Compression和按秩合并 Union by rank。

可以发现并查集并不能直接套用在第九次作业上，因为并查集不支持删除边这一类操作。解决方法很简单，暴力重构即可。但是需要注意的是只需要重构删除的边所在的连通分量就行。重构分为两种情况：

1. 删除的边不是割边，不需要重构
2. 删除的边是割边，这时会产生两个连通分量，我们需要遍历每一个连通分量的所有节点。对于每一个连通分量，将他们的根节点分别设置为同一个节点。重构遍历直接 就行

此外，由于关系图可能会出现一条很长的链，所以深度优先搜索和路径压缩不能递归，否则有爆栈风险。

3. 是否要维护连通分量个数？是否要维护三阶完全子图个数？

个人认为后者必须，前者无所谓。

第十次作业

4. 需求分析。

通过第九次作业的复杂度分析可以发现，如果一个指令需要的时间，那么就绝对不会超时。但是如果是需要，那么处于超时边缘。如果需要更多时间比如，那么就完蛋了。

标签需要支持以下操作：

1. 为一个人新建一个标签 创建即可
2. 为一个人删除一个指定标签 删除即可。记得更新维护的变量。
3. 添加一个人到标签中 添加即可
4. 把一个人从标签中删除 删除即可
5. 查询标签中所有人的年龄的均值 维护即可。
6. 查询标签中所有人的年龄的方差 维护即可，毕竟都是上过概统的人。
7. 查询标签中所有边的权重和 维护即可，不维护可能超时（ or ）
8. 查询每个人认识最好的人 维护即可
9. 查询CP数量 暴力不会超时，尽管我维护了
10. 查询最短路 不需要，直接就行。

第十次作业几乎没有难点。主要问题集中在超时方面，也就是上面的操作7。在查询的时候有人没有维护。没维护也就罢了，偏偏用了的算法，导致互测直接超时。最舒服的方法应该是维护 ，简单由实用，而且应该是我唯一能想到的不超时的方法。

此外，如果两个人决裂了，那么所有包含这两个人的tag都需要将这两个人的value给去掉，因为维护了。一个人只知道自己的tag都有哪些人，但是不知道自己在哪些tag中。因此我又维护了一个变量来让Network类知道每个人都在哪些tag当中。

此外方差可以用概统课上学的公式化简，注意不要化简错了就行。（这次方差的计算有很容易出错的取整问题，建议先算出公式再敲进IDEA中）

第十一次作业

第十一次作业没有需要特别维护的变量，没有需要特别考虑的数据结构。除了将 中的数组写为容器（ HashMap HashSet ArrayList）等等没有任何特别之处。

1. messages[ ] ArrayList
2. emojiIdList[ ] + emojiHeatList[ ] HashMap

此外没有什么特别的地方，个人认为没有必要进行叙述。本次作业也同样没有性能问题，也不进行叙述。

四、单元测试过程

1. 黑箱测试、白箱测试的理解

黑箱测试：

• 本身不知道也不在意内部代码的具体实现，而是只根据输入和输出去判断代码的正确性。也就是按照效果和结果去测试代码；
• 优点在于简洁方便，符合封装思想。
• 缺点很明显，外部难以得知自己的测试是否全面地覆盖到了黑盒内部的每一种情况。
  白箱测试：
• 需要测试人员了解代码的内部结构进行测试，也就是按照实现方式去测试代码
• 最经典的指标包括覆盖行数、覆盖分支数等等。
• 优点在于全面精准地测试代码，比如可以覆盖代码的各种分支路径。
• 缺点在于增加了测试的复杂性。在一些代码中，完全覆盖程序的所有分支路径情况可能会花费巨量时间。

2. 其他各类测试的理解

• 单元测试
  • 对某一个单元模块进行测试。一般这个最小单元通常为一个函数。
  • 优点在于能够对于某一单元进行有针对性地测试，保障每一个单元功能本身的正确性。
  • 缺点在于无法测试单元之间的代码，也就是彼此单元之间相互衔接的代码。
• 功能测试
  • 根据预期要实现的功能，检查代码是否达到预期要求的功能。
  • 个人认为最大的优点在于迭代开发。如果我能保障先前的功能正确，进行接续的迭代开发相比也会舒畅不少。同时他也保障了程序能够达到预期运行效果。
  • 缺点在于只测试了某一方面的具体功能，并不能保障代码本身没有问题，也不能保障功能间的协同合作没有问题。还需要用单元测试、集成测试进行进一步测试才行。
• 集成测试
  • 集成测试主要作用在于测试单元与单元之间的代码正确性，它将单元与单元之间组合起来组装成子系统进行测试。
  • 优点在于能够测试单元与单元之间的代码，弥补了单元测试的缺点。
  • 缺点在于不如单元测试和功能测试的测试目的那么精确有针对性。
• 压力测试
  • 压力测试是模拟程在实际使用中长时间或超大负荷地运行程序，考察程序的正确性、稳定性和性能等方面因素。
  • 压力测试的优点在于能够测试程序在高负载情况下的运行情况。
• 回归测试
  • 回归测试指程序在迭代开发过程中对往次迭代的代码进行测试。
  • 尽管一个理想的迭代开发不应当对往次迭代内容进行大规模改动，但是现实中往往多少会改一改。
  • 当迭代开发对往次迭代有一定改动，或者有涉及时，进行回归测试是很有必要的。他确保了先前的迭代开发功能不会受到影响或破坏。

3. 数据构造策略

数据整体采用了随机构造的策略，尽管不够好，但是个人认为还不错。个人认为数据构造需要考虑以下几个方面：

1. 不要一股脑地ln 100，这除了构造出一个大数据用来 别人以外没有任何用处：难以 ，生成的图不见得覆盖了各种情况（实际上，能覆盖的情况少得可怜），并且写过 的同学都知道 不是增加数据量就能过的。多数同学的代码和世界上普遍代码一样：如果它在小数据范围正确，那么它在大数据范围也大概率是正确的。所有除非想要压力测试，否则完全没有必要ln 100，这只会徒徒增加 复杂性。建议在测试正确性的时候用ln 10或者ln 15，因为足够了。
2. 要有针对性地压力测试，比如针对qtvs定点爆破可能会取得不错的效果（900条qtvs都能到就离谱）
3. 审慎思考、不要偷懒。比如有不少人使用messageId来生成emojiId去构造一个emojiMessage，导致自己搓的评测机完全测不出来的 被别人轻松 。
4. 在随机生成时考虑一下生成概率。比如在测试时，我希望能够将100条消息中的每一条都发送0-20次之间的随机值：
   • 一种方法是先确定一个0到20的随机数然后循环这个随机数次。
   • 另一种是确定生成概率（比如确定为0.5），然后循环20次，每一次都有一定概率（50%的概率）发送。
     两种方法看似都实现了数据生成的随机性，但是在我个人实现中，前者要更好。因为后者是一个二项式分布，也就意味着在范围两个的数据量极小，生成可能十分低，而前者则是一个均匀分布，每一个发送次数都能覆盖到。
5. 实际测评中可以尽可能减少错误指令的密度。可以说，只要一个人的异常处理不出问题，就没必要生成异常指令。尽管很难，但是如果能够控制异常指令的密度，评测的实际效果就真的会好很多。

五、性能问题及其修复情况

很庆幸，在第三单元本人没有出现性能问题，仅在正确性判断中出现了一些小bug而已。（显然第三单元的强测还是太弱了，第十次作业和第十一次作业强测都没有测出一个大bug，结果被第十一次的互测刀了）

上文已经分散地叙述过性能问题的产生、分析和避免，这里总结一下：

分析复杂度：

• 强测一共 条指令，记

• 总共可以生成317阶完全图 ，或者生成 长的链。

• 总共可以发送10000条消息。生成5000左右条tag，往一个tag里面加5000个人左右。
  计算达到10^8量级会很危险，10^9量级基本爆10s，也就是超时。计算一波可以发现每一条指令的复杂度上限大概为： or or 小常数的

• 爆复杂度的最简单的解决方案是维护一些特征值。第三单元的很多特征值都非常好维护。

• 其次的解决方案是更换更高效的数据结构或算法。比如用并查集，或者一些奇怪的动态图双连通图问题的解决方案。

• 不推荐设置脏位，因为这没有从根源上降低运算复杂度，也就是它在最坏情况下不会有任何性能提升，或者说在最坏情况下最好也不过将用时砍半。

六、规格与实现分离的理解

个人理解有以下几个方面：

1. 规格更着眼于描述一个函数或者一个属性的效果、结果。比如在描述最短路径时的JML规格时，只需要描述一条路径和比其他路径都短两个方面，而不需要关心路径是如何得出的等具体实现。
2. 实现则着眼于具体算法。比如在描述最短路径时，穷举每一种路径显然是不现实的，因此需要找到能够达到规格所描述的效果的实现算法来完成规格的实现。
3. 规格和实现都是必要的。规格对应黑盒实验，它不关心一个函数或类的内部具体实现是什么，而只是简单刻画了这个封装起来的“单位”在外界看来应该呈现出什么效果，而这显然对于契约式设计有大作用。实现则对应白盒实验，不知道实现就无法深入程序细节。

七、Junit测试

在第三单元中，本人没有过多思考如何构建更好的Junit测试，而是无脑按照 完成 Junit 测试。利用 进行 Junit 测试显然是不够好的，因为存在无法按照 测试的情况，比如最短路径：我们显然不可能找出所有的路径然后取最短的值作为返回值。类似的情况还有很多。因此本人没有非常好的方法去进行具体的Junit测试。