23年春面向对象第三单元分析和总结
目录
概述
JML
JML基本
JML表达式
局部容器
操作符
架构
连通块数目查询
三元环数目查询
最小环查询
测试
测试的分类
测试工具
构造测试用例
OKtest
bug分析
总结
概述
OO第三单元主要围绕着 JML(Java Modeling Language) 展开，这是一种用于对 java 进行规格化描述的语言。主要形式是由课程组提供 JML 规格，同学们实现业务代码。在本章当中，我主要学习到了如何阅读，理解，并实现 JML 规格，初步掌握了使用 JML 规格描述期望实现的逻辑的能力，了解到了规格化验证的思想。作业的背景是一个社交网络，本质上来说是一个具象化的图。实验课在此基础上设计了三次实验，形式均相同，在这里略微介绍一下背景：
1. HW9：实现社交网络的基本架构，可以查询连通块数目和三元环数目
2. HW10：新增了消息类和组类，可以发送消息，可以实现删边操作和查询最熟熟人
3. HW11：新增了表情类，丰富了消息类，可以查询最小环
总的来说第三单元虽然需要同学们动脑去构思，去架构的地方减少了，总的代码量却大大增加了。第三单元结束后，总的代码量已经达到了1500行，这其中有很多细节，容易错误的地方反而增多了。笔者在第三单元的得分要远低于一二单元，结束之后，需要好好反思总结。
由于是自己的博客而非班级博客，我在这里对于第三单元发一些牢骚，如果各位读者不愿意看，请不要点击展开。
- 笔者能够理解程序设计需要形式化的规格。这种规格相比于自然语言可以更好的消除歧义，更加严格地限定条件。但是形式化是需要有一定限度的，所谓“过犹不及”。如果一个方法的规格行数已经远远超过了实现这个方法所需要的代码行数本身，我们是不是应该思考一下，对于规格的应用是否有些过火了？如果能够使用自然语言简洁准确地描述一个方法的作用，为什么不教给同学们 javadoc 的写法然后使用自然语言描述方法？
- 对于第三次作业中的最小环算法，课程组似乎有些过于为难笔者这种能力不足的同学了。在搜索引擎上搜索最小环算法，大多数的做法是通过删边 + 最短路径或者直接在 floyd 中实现，但是这些实现方法，不论再怎么优化，都不能通过全部的测试用例。有且仅有通过一次最短路径搜索找到最小环的算法可以通过所有的全部的测试用例。课程组在指导书中没有明确指出最小环算法应该满足的复杂度，也没有向同学们介绍可能的实现方案。如果课程组默认修OO课程的所有学生都至少应该有这方面的知识的话，我只能说这充分体现了课程组的清高。我也并非有资格坐在这里上这门OO课程，只是机缘巧合，造化弄人罢了。
- 鉴于第三单元的实用程度以及其与第一、二单元的差距，我个人建议将第三单元的算法单独抽出来，然后将第三单元和OO课程神圣分离。
JML
JML基本
- JML 以注释的形式来表示规格，其注释一般写在方法之前，也有写在方法之中的关键字。表示 JML 的注释，每行开头均需以一个
@作为标志。每个字句的结尾均需以一个;结束。 - 使用
requires定义该方法的前置条件，即执行这个方法前应该满足的条件，一般不满足前置条件的时候，该方法不能有副作用并可以抛出异常。 - 使用
assignable定义该方法的副作用范围，即这个方法可以修改的数据范围。如果不定义该项，或者之后的后置条件与之不搭配，那么就不能确定该方法是否具有其他的副作用。使用关键字\nothing表示该方法无任何副作用，在方法中标注/*@ pure*/也可以起到相同的效果。 - 使用
ensures定义该方法的后置条件，即执行完这个方法后满足的条件。 - 使用
model定义规格变量。规格变量具有两种类型：静态规格变量和实例规格变量，分别对应了 java 的类变量和类成员变量。 - 使用
normal_behavior规定方法正常工作时满足的子句，使用signals规定方法在何种情况下会抛出何种异常。
上述的这些构成了 JML 的基本框架，但是为了描述规格，JML还需要很多其他的逻辑关键字进行限定。
JML表达式
\result表示方法执行的返回结果\old(X)表示X在方法执行前的值。此表达式通常套在需要取原来值得表达式外边，因为如果只是对于某一个引用(或其他内容有变化的变量)取该表达式的值，只能够保证该引用没有变化，不能够确认引用中的值有没有变化。JML 中不加\old()表达式的取值则是方法执行之后的。\not_assigned(X)表示表达式X的值没有变化，用于在后置条件中限制不变部分。(\forall X)全称量词(\exists X)存在量词(\sum X)返回表达式X所有可能值的求和(\num_of X)返回表达式X可能取值的个数(\max X)返回表达式X可能取值的最大值，(\min X)返回最小值
局部容器
在比较复杂的规格当中，输入和输出之间的关联可能并不那么直接，有的时候需要我们通过构造中间变量的方法约束得到的结果。
使用new ST {T x | R(x) && P(x)}来声明一个局部容器，其中的R(x)对应集合中x的范围，通常是来自于某个既有集合中的元素，如s.has(x)，P(x)对
应x取值的约束。
操作符
架构
第三单元的架构主要的由课程组提供的，在实现的过程中，笔者无非采用了一些其他的容器，或者针对图论问题采用了某些维护方法。故本次不再提供 UML 类图。
连通块数目查询
采用了并查集。
并查集是一种数据结构，主要用于处理一些互不相交的集合合并与查询的问题。在本次作业中，我们使用并查集来维护连通块的数目。并查集的基本结构很简单，由一个数组和两个函数组成：数组用于记录每个节点的父亲节点。两个函数分别是 union(合并) 和 find(寻找祖先)。两个节点在同一个连同块中的充要条件是它们有相同的祖先。
如上图所示，并查集构成了一个这样的结构。find 会持续递归回溯节点的父亲节点，直到某个节点的父亲节点为空，就找到了这棵子树的祖先节点。
在合并时也很简单，只需要在两颗待合并的子树中任选某一个子树的祖先节点，将其父亲节点设为另一个子树的祖先节点即可。
有时候为了优化并查集的查询性能，会采用压缩路径的优化。只需要在 find 时添加一个赋值语句即可。
在第十次作业中，新增了一个删边的操作，这对于并查集的维护是一个打击。基于“删边的情况总是比较少，最多也不会超过总指令数的一半”这个信念下，我仍然保留了并查集算法，在删边的时候重置所有节点的父亲节点并重新构建连通块。
三元环数目查询
采用了动态维护。也是评论区 nr 大佬的思路。
由于三元环只会在添加路径时形成，只会在删除路径时删除，所以对于三元环数目进行了动态维护。
最小环查询
首先是对于最小环的定义：在一张图中，由n个节点构成的边权和最小的环。在无向图中，最小环至少包含三个节点，有向图中没有节点限制。
对于最小环的查询，New Bing 给予了我三种解决方式：floyd 算法，时间复杂度 O(n3)；堆优化的 dijkstra 算法，时间复杂度 O(nmlog(n))；tarjan 算法，时间复杂度 O(mn)。floyd 和 dijkstra 都是通过删边的办法实现的，对于其算法的基本描述，已经在我的另一篇博客 最短路径算法 记录了。值得注意的是，只有类似于 tarjan 算法之类的时间复杂度小于 O(nlog(n)) 的算法才能够通过全部测试用例。关于 tarjan 算法，笔者能力有限，留个坑在此处，后面有时间再填上。
测试
很惭愧的说，笔者的测试一直以来都做得很差劲，可能是早已习惯了程设，DS再到CO那种提交上去就可以知道正确与否的课设模式，笔者对于OO这种课设模式总是感到不适应。在前两个单元，因为存在评论区大佬无私共享的测评机和测评数据(再次特别感谢各位充满着共享精神的大佬)，笔者也迟迟没有动手写过自己的自动化测试工具。最多的情况下也不过就是手动构造一些数据，“瞪眼法”修修bug罢了。但是进入到第三单元，没有各位佬的拐杖，就像缺了一条腿走路，再加上完全没有强度的中测数据，使得我这种测试困难户的毛病暴露出来。此处还需要痛定思痛。
测试的分类
从测试者是否关心被测代码的内部结构的角度上，测试可以被分为黑箱测试和白箱测试。
黑箱测试指的是根据功能需求来测试软件的输入输出，并不关心软件内部的实现。OKTest，测评机，对拍器等都属于黑箱测试的范畴。黑箱测试有以下注意事项：
- 想要进行黑箱测试，首先对于软件的规格需要有明确的限定
- 黑箱测试需要覆盖所有可能的情况，包括正常和异常情况
- 黑箱测试需要记录测试的结果和发现的缺陷，以便进行改进
白箱测试指的是测试者需要了解软件的具体实现，检查每条代码是否被正确执行。打断点调试，瞪眼法，使用print输出调试等都属于白箱的范畴。白箱测试也有一些注意事项：
- 对于程序的每一个分支都要进行测试
- 对于程序的每一个判断都需要进行真、假两次测试
根据测试的目的和范围，又可以将测试分为单元测试、功能测试、集成测试、压力测试、回归测试。
单元测试指的是测试是针对软件中的最小可测单元进行的，在函数式编程中可能是一个函数，在 java 中可能是一个类。主要用于检查代码的正确性和质量。
功能测试指的是对软件的某一个特定功能进行测试。这通常适用于一个大的软件系统，对于其中各个相对独立的功能进行测试。主要用于检查软件是否满足用户的期望。
集成测试指的是对软件中的多个单元或模块进行组合和协调的测试，比如接口、数据流、消息传递等，主要用于检查软件的整体性能和稳定性。
压力测试指的是对软件在高负载或极限条件下的表现进行测试，比如并发用户数、网络延迟、内存消耗等，主要用于检查软件的可靠性和容错性。
对软件在修改或更新后的功能和性能进行重新测试，比如修复bug后、增加新功能后等，主要用于检查软件是否有新的问题或影响。
测试工具
构造测试用例
手动构造测试样例不可能涵盖大量的情况，其主要作用是对边界情况和异常情况进行测试。手动构造测试用例只能够作为自动化测试的补充，不能够起到充分测试的目的。
OKtest
OKtest 实际上是一种黑箱测试，其实就是课程组为了防止大家不使用 Junit 而专门设置的考察点。OKtest 确实可以做到对方法的全覆盖，但是其臃肿程度又非一般测试所能接受的。故 OKtest 或者与之相似的单元测试天然就是为了与规格搭配而生的，通过严格检查输入输出来考察方法的正确性，可以很快的定位到方法中实现错误的部分。对于加深对规格的理解有一定帮助。
bug分析
第三单元可以说是惨不忍睹。笔者第九次作业喜提鸭蛋，第十次和第十一作业均存在相当数量的bug。一部分原因是因为第三单元的作业码量庞大，要求繁杂，既要读规格，还要写代码导致的，但最主要的原因还是在于没有进行充分测试。
第九次作业中的bug出在了迭代器上。在实现过程中，笔者使用了 HashMap 和 HashSet 一类的散列容器对数据进行存贮，遍历时使用了 iterator。说来惭愧，这还是笔者第一次使用类似散列结构的容器。问题出在了对迭代器的使用上，在一次循环中，调用了两次 iterator.next()。原意可能是没有存上一次调用时的值，或者是改语句的时候漏改了，总之这个bug在强测中全部暴雷，喜提鸭蛋。这让我意识到，如果不是需要对容器进行删除，foreach 循环可以安全的平替迭代器，可以避免这样的情况发生，但是如果需要借助迭代器做其他的操作，如：iterator.remove() 那就只能使用迭代器了。
第十次作业的bug出在删边后的连通块数目上。我的做法是在删边之后全部重跑一遍并查集，但是在重构并查集的时候，union 操作出现错误：笔者并没有将其抽象出来单独做一个方法，而是嵌入其中的，结果第九次作业中写了正确的 union 操作，在第十次作业中写了错误地。前后代码都不一样，悲（
第十一次作业中则是因为最小环的查询问题。笔者只采用了一个删边 + 朴素 dijkstra 的实现方法。可以想象，在强测数据极其稀疏的情况下，所有测试求最小环的测试点全部挂掉。笔者尝试了使用 SPFA 和按边遍历 + 堆优化的 dijkstra 进行优化，但是都不能修复所有的测试点。
总结
第三单元的任务结束了，留下了很绝望的回忆。第一次挂掉强测，修复bug的时候看到满屏的re，我有一种一拳打在棉花上，棉花却反弹过来创死我的既视感。抽象，荒诞，并且鬼畜。平心而论，第三单元除去最后的最小环其实并没有什么能力上的要求，bug的出现当然也是因为自身的能力不足。但是相比之下，在第一二单元，即使写出了像是唐吉坷德冲向风车般的滑稽错误，我也尚且觉得悲壮和有价值。以《等待戈多》的末尾做结罢：
“嗯?咱们走不走?”
“好的,咱们走吧。”
[他们站着不动]