『面向对象』面向对象第三单元总结——社交网络与JML

一.前言

转眼第三单元也迎来结尾，这单元的笔者的经历可谓是起起落落落落落(省略n个)，充满了魔幻色彩。

官方要求培养的能力有二：

了解基本的JML语法和语义，以及具备根据JML给出的规格编写Java代码的能力。
了解OK方法，以及具备规格写OK测试的能力。

JML(Java Modeling Language)是用于对Java程序进行规格化设计的一种表示语言。在单元末尾再来思考JML的存在意义，笔者终于理解为什么行业上鲜有人使用，一旦方法代码复杂起来，用语法很难去描述一个完备的规格(比如实验课上较复杂的JML俺都写不出来)，连课程组给出的JML都能被找出Bug，在日后的大工程中那想都不敢想，以及目前好像缺少形式化验证的方法(如何验证JML所写与你脑海里构想的功能相符且完备)，我们也要去深入探讨是否有必要完成这种形式化编程，或者说是否需要将需求先转化成JML规格进而再转化成代码，就笔者目前接触到的程序中是不太需要的，然而无论如何本单元也为我们开辟了一片新的天地，对于形式化构建类和方法，增强程序的健壮性有了更加深入的理解，学习到了许多未接触过的知识。

然而实际上，我更愿意称本单元作业是披着JML规格化外衣的算法题，这三次作业对算法复杂度要求颇高，研究算法所花费的时间远远超过了根据JML写代码的时间，尤其是求最小环时，使用最常见的删边法并使用优先队列堆优化竟然会超时，在使用讨论区大佬自创的算法后才能通过，诚然，对于之前使用的算法需要n次迪杰斯特拉，而自创的算法只需1次，在数据量大时效率一定有很大差距，但我不禁感到疑惑，我和朋友在市面上(CSDN，博客园等)均没有发现一次迪杰斯特拉求最小环的解，难道一个OO作业已经要求我们去自创，去魔改算法了吗，这未免对我们要求过高。

二.测试方法

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

白盒测试也称为结构测试，主要用于检测软件编码过程中的错误。程序员的编程经验、对编程软件的掌握程度、工作状态等因素都会影响到编程质量，导致代码错误。

黑盒测试又称为功能测试，主要检测软件的每一个功能是否能够正常使用。在测试过程中，将程序看成不能打开的黑盒子，不考虑程序内部结构和特性的基础上通过程序接口进行测试，检查程序功能是否按照设计需求以及说明书的规定能够正常打开使用。

黑盒测试和白盒测试主要有以下三个区别：

从定义上的不同：白盒测试需要从代码句法发现内部代码在算法，溢出，路径，条件等等中的缺点或者错误，进而加以修正。而黑盒测试着重测试软件功能，它并不涉及程序的内部结构和内容特性。黑盒测试并不能取代白盒测试，它与白盒是互补的测试方法，它很可能发现白盒测试不易发现的其他类型错误。
从测试目的上的不同：黑盒测试的目的是检测是否有不正确或遗漏的功能；数据或者参数上，输入能否正确接收；是否有数据结构错误或外部信息访问错误；性能上是否能够满足要求；是否有初始化或终止性错误。而白盒测试的目的是通过在不同点检查程序的状态，确定实际的状态是否与预期的状态一致，而不顾它的功能。
检测方式上的不同：白盒测试是穷举路径测试，黑盒测试是穷举输入测试，这两种方法是基于完全不同的观点，反应了事物的两个极端，它们各有侧重和优势，但不能彼此替代。在现代的测试理念中，这两种测试方法不是截然分开的，而是交叉使用。

2.对单元测试、功能测试、集成测试、压力测试、回归测试的理解

这几种测试都包含在黑箱测试的范畴。

单元测试：是对软件中最小可测试单元(通常是一个方法)进行检查和验证。单元测试是在软件开发过程中要进行的最低级别的测试活动，软件的独立单元将在与程序的其他部分相隔离的情况下进行测试。
功能测试：功能测试就是对产品的各功能进行验证，根据功能测试用例，逐项测试，检查产品是否达到用户要求的功能。
集成测试：也叫组装测试或联合测试。在单元测试的基础上将所有模块按照要求设计组装成为子系统或系统，进行集成测试。
压力测试：通常是使用极大的数据量或临界数据对系统进行测试，检验系统是否具备处理高压数据的能力，或者系统处理数据的时间是否过长复杂性过高。
回归测试: 修改了了旧代码之后重新进行测试以确认修改没有引入新的错误或导致其他代码产生错误。

我们课程组极力推荐的JUnit便是进行单元测试，通过对每个方法人为设置输入，前置条件并判断得到的输出是否与预期输出相符。据简要的研究，JUnit对一个方法每次只能测一组数据，效率过低，因此笔者整单元并没有使用过JUnit，即并没有进行过单元测试。

笔者采取了下述几种测试，均是以自制的半随机生成指令评测机与朋友对拍为基础：集成测试，对全部的指令半随机生成，测试整个系统的正确性；功能测试，对部分功能涉及的指令半随机生成，算是对某些功能的强测，诸如测试发红包分钱，关系图，计算组内年龄方差等等；压力测试，一次性输入大量(指令数上限左右)复杂度较高的指令，如第三次的qlm和第一次的qts，测试系统会不会超时或崩溃，这点笔者做的并不好，并没有针对qlm和qts进行万条指令的测试，因此强测便被狠狠的上了一波压力；回归测试，自然，每改一个Bug都一定会重新对整体进行测试。

3. 数据构造有何策略

具体来说，评测机的数据构造采用的半随机生成方式，针对集成测试，即先添加给定的组数，消息数，表情数，接着添加人数，并随机将人分进组内，并随机生成数量固定的二人关系，做好前置部署；最后随机的从所有指令中生成(这是为了避免一开始出现大量的无用异常)，为了使指令出现频率某些高某些低，可以再适当手动调整，诸如加人，加组等操作已经执行过，便可降低频率，但为测试异常还是要保留，另诸如发送信息操作，我们自然是想让添加的信息尽可能发出，那便提高发送信息的概率。归根到底即保证所有情况都要被全面的测试到，无论是正常还是异常。

当执行集成测试时，经常会出现上千条数据中出现Bug的情况，Debug根本无从下手，于是笔者找到错误的指令，并针对与之相关的功能设置了强测，即排除掉其余不会对该功能产生影响的指令，只针对性生成指令，这样在百条左右的测试中便会暴露问题，大大提高了Debug效率，诸如图算法出现问题时，只保留加人，添加关系，删除关系等指令，查询金钱出现问题时，只保留与组相关的以及添加发送红包信息的指令。现在想想应当是先进行功能测试再进行集成测试，然而为了图方便，也是抱着侥幸心理，二者的顺序被我颠倒了，在以后面临大型的项目时，应该分清先后才对。

三.梳理本单元的架构设计，分析自己的图模型构建和维护策略

本单元UML图如下所示：

大致框架JML已经给出，并不涉及过多复杂的内容，为加强功能的分离以及Network不能超过500行，将图算法相关内容和Ok测试相关内容单独封装成类。

第九次笔者采用BFS图算法并没有动态维护属性，后因超时修改为并查集且进行动态维护，效率大增。

第十次笔者发现并查集适用于只涉及加点加边的问题，而即使有着重建并查集的方法，仍觉得并查集不适合进行删边操作，后终于发觉真正影响时间的是动态维护与否，而非图算法性能高低，后又改为BFS并进行动态维护。

第十一次笔者采用最常见的迪杰斯特拉+删边法处理qlm问题，需要进行指定结点度次数的dij算法，效率低然而并无更好的想法。后由于强测超时将方法更改为讨论区提到的一次迪杰斯特拉寻找结点最短路径与次短路径的方法，笔者对其大为震撼，然而由于正在二阳，还未来得及研究其证明过程。在更改算法时遇到一个问题：优先队列不能擅自更改内部元素，不然将无法准确排序。

本单元使用的动态维护策略如下：

qbs: 静态计算n方复杂度，也许不会爆，然而动态维护很方便，只需在加人时加一，增关系前，减关系后判断两节点连通性即可。
qts：静态计算n三次方复杂度，罪魁祸首。动态维护只需在增删关系时遍历找到二人共同的朋友即可。
qcs：静态计算n复杂度，而动态维护较方便，对于每人维护一个Pair<bestFriendId,bestValue>即可。
qba：同上。
qgav：静态计算n复杂度，可动态维护组内的年龄和和年龄平方和，查询时直接带入方差公式计算即可，注意应严格按照JML标准(不严格会出现由于向下取整问题导致的差一现象)。

对于有些复杂度并非很高且动态维护较为麻烦的指令(qgvs)选择放弃，复杂度在$O(n^2)$之内的应当都可以接受。

四.Bug分析

本单元三次作业Bug如下:

第一次：强测40分，没有使用动态维护，qts，qbs完全按照JML写的，导致被强测干烂，后改成上文所述方法，因此对规格与实现分离略有理解。
第二次：强测寄一个点，没有看到JML中组内人数上限，不细致，活该出错。
第三次：强测寄一个点，qlm的压力测试未能通过，采用的传统方法复杂度较高(nmlogn)，后使用院友改进版方法(n+mlogn)通过并大受震撼。笔者对于qlm的性能已经尽力辣，还是要多看看讨论区，信息渠道不要太闭塞为好。

规格与实现的分离有几个很好的例子，在规格中Person拥有int[] acquaintance 和 int[] value 两个属性，一开始还傻傻的开数组，并尝试将数组和ArrayList来回转化，后来有点小悟，觉得无论用什么方式只要能存储起来就行，便改成了Arr，再最后改成了HashMap。再比如qlm的JML表述，读懂后能很快明白意思，找到一个Path数组，长度大于等于4，头和尾相同，中间依次相连……就是找到一个最小环，然而正所谓条条大路通罗马，在求最小环时你使用迪杰斯特拉，弗洛伊德抑或其他算法皆可，复杂度高还是低皆可，这属于具体实现方法，并不是规格所关心的，规格关心的只是到底干没干好这件工作，即前置条件，后置条件，副作用，结果等是否正确。qbs，qts也同理，若是按照JML严丝合缝地写，复杂度过大，然而实则无论你采用何种方法得出正确结果即可，JML只是给出了一个正确结果如何得到的表述，(要是能早点意识到该多好。

规格与实现的分离也是契约式编程中规格撰写方与代码实现方互相信任的表现。

五.本单元中同学们实现了OK测试方法，请同学们思考OK测试对于检验代码实现与规格的一致性的作用，有何改进何建议

本单元每次作业都令我们实现了一个OKTest，即给定一组输入输出，已知输入状态合法，让我们判断输入经过方法后得到的预期输出与执行后状态与给定的输出与执行后状态是否一致。我身边的同学对Ok测试颇有争议，对实现方式也颇有争议，有根据输入状态真实生成一个网络并调用被测试方法的，也有仅依据JML直接对输入输出容器进行判断的，前者过于复杂，笔者采用的是后者的方式，也更倾向课程组是以后者的思路设计的，所以起初认为这好像只是一个锻炼我们对容器基本操作能力的东西，仅仅用到了官方给出的规格。小组讨论后，我现在更倾向于一种说法，Ok测试是对JML的一种代码化实现，完成Ok测试时我们的角色应该是规格撰写者，站在规格撰写者角度应百分之百信任JML和Ok测试，即认定JML与Ok测试具有一致正确性，然后我们对将一位笨笨的程序员的代码执行该方法前后的信息提出，并接入我们的Ok测试，判断其代码实现的正确与否，即检验了代码实现与规格的一致性，只不过在本单元，我们既充当了规格撰写者又充当了代码实现者，需要在两种角色间自由转换。

至于改进建议，不知上述笔者理解的是否存在偏差，建议课程组可以写的详细具体一些，令大家直观的明白写Ok测试的意义，不至于令人抓瞎。