「BUAA OO Unit 3 HW12」第三单元总结 目录

Part0 前言Part1 测试分析1.1 黑箱白箱1.2 多种测试思路分析1.2.1 单元测试1.2.2 功能测试1.2.3 集成测试1.2.4 压力测试1.2.5 回归测试 1.3 测试工具分析1.4 数据构造策略1.4.1 oktest测试数据构造1.4.2 数据生成器数据构造策略 Part2 架构分析2.1 图构建概述2.2 主要图论指令维护算法2.2.1 "qci" 指令2.2.2 "qbs" 指令2.2.3 "qts" 指令2.2.4 "qlm" 指令 Part3 性能分析3.1 性能优化策略3.2 规格与实现分离 Part4 ok测试分析4.1 oktest方法的意义4.2 改进建议 Part5 心得体会

Part0 前言

本博客严格对标作业要求完成，阐述了我个人对这些和Unit 3有关的问题的理解，下面直接进入正文。

Part1 测试分析

1.1 黑箱白箱

黑箱测试和白箱测试都是测试的思路。

黑箱测试，按照我的理解，其意思就是在测试的过程中不关心内部程序的具体实现，只关心给这个程序一个输入，这个程序能不能给我一个正确的输出。

白箱测试，黑白相对，白箱测试的意思那就是我们要关心程序的具体实现逻辑了，要完全了解程序的结构与处理过程。比如，代码走查就可以认为是一种白盒测试，通过检查代码的方法看程序是否有按照自己期望的逻辑运行。

写到这里，我其实就已经感觉到我测试的不足了，即：我每次采取的测试策略基本都是黑箱测试，白箱测试的思想虽然也有，但是并不多，而白箱测试也是有其优越性在的(比如可能一个很小的bug靠黑箱的话要找很久，甚至可能还测不出来，但是如果是白箱测试的话可能很快就找出来了)，所以我希望自己将来也能多用一些白箱测试的思想来保证程序的正确性。

1.2 多种测试思路分析

如本节标题所言，下面的一些和测试有关的名词都是指一些测试的思想，下面我便会说一下我个人对这些思想的简单理解。

1.2.1 单元测试

指对程序中的各个单元(至于什么算是一个单元，感觉这个就看自己的理解了，比如可以认为一个函数是一个单元，也可以认为整个程序是一个单元)进行测试。什么意思呢？比如我现在写了一个java程序，这个程序的主方法调用了5个其他自定义方法，那么我就可以把这5个方法看成5个单元，对每个单元，我就可以通过黑箱/白箱的思路，对其进行充分的测试，在确保了这5个小单元的正确性都没问题后，我们再将顶层的main方法看成一个单元，再对这一个顶层单元进行充分的测试(比如直接代码走查，看逻辑有无错误)，这样就能通过"逐个击破"的思路实现了确保整个程序正确性的目的。

1.2.2 功能测试

功能测试在我看来就是是指测试一个程序的功能完不完整，正不正确。构造一堆测试样例，这些样例可以覆盖到软件的所有功能，然后让这个软件跑一遍这些样例，就可以测试出软件的功能是否完备了。比如，拿我们hw11写的软件来讲，我们就可以分别构造出各个指令对应的用例，来测试我们写的软件是否满足了基本的各个功能需求。

1.2.3 集成测试

集成测试，顾名思义，就是把各个部分集合起来测试，看看各个部分能不能正常的协调工作。比如我们通过单元测试的方式测试对A B 两个单元测试好了，这时候我们就可以将A B 集成起来，对他们整体进行测试，以确保有正确实现的单元还能够做到正确地协同运行。

1.2.4 压力测试

压力测试我觉得就是针对我想测试的对象，以及想测试的功能，构造一些极端一些的用例来对程序测试，如果程序能承受住这种极端测试的压力的话，就可以在很大程度上表明程序的这一功能有着较好，较正确的实现。拿我们的作业举个例子，我想对qlm指令进行压力测试，看看程序的效率能不能扛得住，那么我就可以先加充分多的节点，然后加充分多的边，构造一个完全图，然后构造很多qlm指令，用这种极端的样例测试，如果程序在这种情况下仍然能保持一个较高的效率，那么在强测中应该也就不会出锅了。

1.2.5 回归测试

回归测试也比较好理解，就是说我们在写程序的时候肯定经常会涉及到程序的迭代开发。而每当我们迭代的时候我们都可能因为改错代码而为之前完美的程序引入新的bug，那么对于这种情况，我们就可以在每次迭代之后拿之前版本的程序的测试工具对迭代后的程序进行测试，确保不会出现因为改程序把原本正确的功能都改错了的情况发生。

1.3 测试工具分析

我使用的测试工具主要是数据生成器+对拍器。这个想必几乎每个同学都使用了。这里我想说的是，数据生成器也是有讲究的，并不是说因为它的随机性足以让他覆盖所有情况就可以放心了，因为虽然随机性可以覆盖，但是有的情况被覆盖到的概率是很小很小而几乎可以忽略不计的。

举个例子来说，一个数据生成器，创建group指令的概率比较大, 同时创建人的概率又不是那么地大，这就会导致，即便 人加群 的指令很多，但是因为群太多了，所有人都被稀疏地分散进了各个群中，基本很难(概率非常小以至于可以忽略，相当于数据生成器不能覆盖到这样的情况)出现一个群里有1k个人以上的情况，而这样的话就测不到 群人数上限的限制(我看群里有同学将 <=1111写成了 <1111 而导致出了bug)。

更具体的数据生成器的套路会在1.4说。

除了数据生成器+对拍器这一常规的套路之外，我还使用了Junit工具进行单元测试。这方法是一种白盒测试的思想，因为我们知道被测试的软件是如何完成功能以及完成怎么样的功能的。不过在作业中，我对于这种测试方法用的没有数据生成器的多，因为毕竟随机数生成器可以进行自动化的测试，省事效率高，且只要生成器逻辑写好，其生成的数据强度也是很可观的。

1.4 数据构造策略

1.4.1 oktest测试数据构造

这个的数据就手捏了，自动生成有一定强度的oktest方法数据还是有一定难度的。手捏的方式是尽可能地去枚举每种情况。hw10的oktest方法应该是这三次作业中最复杂的了，拿hw10的来举个例子，我们可以进行如下方式枚举(虽然oktest的数据难以完全交给数据生成器自动生成，但是在捏的过程中也可以用一下来生成一些局部数据)：

非异常情景(三个参数合法)

修改一个固定的id1<—>id2 value 随机生成使涵盖所有 +value 后的值的情况 其它无关的afterData有改变(值改变/多少关系)其它无关的无改变 —> 相关的不改变相关的改变正确相关的改变错误: value错, 去边… 异常情景 出现异常有副作用出现异常无副作用

当然，上面是我捏数据的思路，未必全面，但是也是希望通过枚举所有情况的方法来尽可能地提高全面性，这也是其他两次oktest方法数据的构造思路。

1.4.2 数据生成器数据构造策略

在这里我想着重说一下数据生成器数据生成逻辑问题，也算是数据构造策略了。要认识到的一点是，我们的数据策略可能不是唯一的，数据生成器在我们自己的手中，我们可以随时调参数，因此我们可以用不同版本的生成器针对不同情况进行强测。

要避免数据量看起来大，但其实一堆都是无效数据的情况。比如举个极端的例子，我仅生成了一个ap指令，也就是整个图只有一个节点，但是却有9999条加边的指令，那这个数据量，看着10000条也挺大的，但其实还不是随便手捏几条数据的强度高呢，当然这只是为了便于读者理解我的意思举的一个极端的例子，事实上肯定不会极端到如此地步。

那么如何避免这种情况呢？首先给ap指令设置一个不低的概率，因为没有节点的话别的所有指令都将没有意义。在此基础上，每次ar mr 时以一个很大的概率从已经ap过的人(而不是在int范围内随机生成俩id去进行操作，int范围太大了，这样生成的id基本就是无效id)中挑两个来进行边操作，mr还可以挑两个之间有边的人进行修边操作，之所以是"一个很大的概率"而不是百分百的概率，是因为还要测异常情况，留一小部分概率给异常，可以让测试的覆盖面更广。这样一来，大多数指令就是有意义的指令了。要避免稀疏图的情况。其实这一点的解决策略和上一条有点重复了。有的测试点，虽然看起来指令不少，但是实际上这个数据点所构建出来的图是非常稀疏的，这就会导致很多情况测不到，比如qci判断两个点是否连通，那要是这个图很稀，几乎随便俩点都不连通，那其实qci 的正确性就不能充分得到测试(当然，稀疏可能也有好处, 一些情况的测试可能需要构建稀疏图, 还是说我们的数据生成器的参数可以随时调整, 我们调整出不同版本的生成器进行多方位强测即可)。 那么如何让生成器生成稠密图呢？就是把ap指令的概率调大，然后ar指令的概率调大，且ar的概率要比ap大一个档次，且ar的时候要大概率在已经存在(或者甚至是已经存在且没边)的两个人中间加边, 这样就可以得到稠密图，稠密图测试点可以覆盖相当多的bug情况。避免群人数不够多的情况。群人数够多才能测到群人数的限制。要解决这一问题，数据生成器生成 建群指令 的概率要调小，同时 加人指令和把人加进群的指令 的数量要调的足够多，这样才能构建出"大群"的情况。避免图稠密但是图的规模小的情况。通过上面的第2条，我们知道了构建稠密图的方法，但是如果想要在稠密的同时保证图的规模足够大(规模大，肯定能覆盖很多情况)，那应该怎么做呢？就可以调大指令的总条数，类似于“相似三角形 等比例扩大”，各个指令都变多了，1k个节点的图，我们可以用10w、20w、50w…的数据量来保证以这么多节点仍然能构造出稠密图，虽说强测限制1w条，但是我们本地测可没限制呀，我之前竟是忽略了这一点的，自己在强测前就应该用十万、百万级的数据狠狠地测！

暂时想到了这些比较经典的，就先写这么多~

Part2 架构分析

2.1 图构建概述

我用邻接表的方式来存整个图。主体容器为HashMap<Integer, HashMap<Integer, MyPerson>>类型，这个容器的keySet是图中的所有节点，容器的values是对应key这个人的“邻居”，也就是key的边的信息。在加边加人删边的过程中不断维护这个大容器, 就是图的构建过程。

同时，通过在MyPerson类中增加parent属性实现了基于所得到的基本图之上的并查集的构建(下文会详细讲)。MyNetWork类中也加上了cntTriangle, cntSelfParent等需要动态维护的属性，来满足各个指令的查询需求。

图的架构貌似比较统一，再加上本单元架构几乎被官方码完全限制的因素，这方面我好像想不到太多要说的…

2.2 主要图论指令维护算法

2.2.1 “qci” 指令

该指令的作用是, 查询图中的两个节点之间是否存在一条路径。我的方案是用并查集算法来实现。对于并查集，我觉得可以理解为我们使用这个算法是在对一个无向图（的节点）进行分类整理（图太乱了，给sort一下），最后想达到这样一个效果（目标）：以这个图为素材，整理出来一个森林，这个森林由若干个树组成，每个树都对应一个图中的极大连通子图（也就是极大连通块），我们整理时只需要保证连通的点都在同一个树上就可以了，我们不管这些树上的点之间相对排布。例如下图：

我们用这个算法的时候脑海里应该能想象出来这样的一个森林（上图中展示的是A->BDC，还是说，我们不关系这个树的结构，只需要让属于同一个极大连通块的节点都在同一个树上就可以了）。

简单来讲，就是把图中的所有的极大连通子图都抓出来，各个子图各自用自己的所有节点建立一颗树，这颗树的结构随意，只要保证此连通子图的节点都在其对应的树上即可。

那我们是如何构建出这一个个树呢？？是通过不断地”指定父节点“来实现的，B的父节点是A，那么此时AB就相当于在一条树上了。即，我们认为图中的每个节点都有一个唯一的父节点（每个节点都有一个属性，记录他的父节点id，类似于链表中的指向下一个元素的*next指针），通过这个”父节点（next指针）“把各个节点都串起来成为一个个树。

那么这样以后，我们就有办法处理qci指令了.我们现在已经整理出了上面图片中的森林了，那么现在给我们v1，v2两个节点，我们怎么判断他们是否连通呢？？我们可以求出v1的父亲的父亲的父亲的父亲的父亲（有点像一条链，沿着这条链一直向上递归查找）……，也就是v1所在的那个树最上面的那个节点（祖先），然后求出v2的祖先。那么很显然：

v1的祖先 == v2的祖先是v1和v2之间连通的充分必要条件。所以我们只需要求两个待判断的节点的祖先即可。我采取的找祖先的算法是递归算法, 也就是在find函数里return find函数本身, 直到递归到参数的父节点是自己本身的时候, 再结束递归。

以上就是我们的核心思路, 但是当我们用mr指令进行删边的时候, 我们已经建立的并查集会被"干碎", 那么这个时候, 我们就要重建并查集, 按照原本建立的思路继续建立就可以了。

2.2.2 “qbs” 指令

该指令的含义是查询图中极大连通块的个数。那么我采取的策略是利用如下关系来查询:

极大连通块个数==并查集中以自己为父节点的节点个数(并查集构建的思想在1.2.1已经较为详细地说过了), 那么在加点, 加边 的时候, 我们这个以自己为父节点的节点数量是可以动态维护的, 这样一来, 当qbs指令来了之后, 我们直接返回我们已经维护好的变量值即可。

同样的, 由于本策略是基于并查集的, 当删边导致并查集被破坏后需要重新构建并查集。

2.2.3 “qts” 指令

该指令的含义是查询图中的三角形的数量。 这个的话我采取的策略就和并查集没什么关系了。 不过我依然采取的是动态维护的方法。我用一个变量表示图中三角形的数量, 比如我设这个变量叫做cntTriangle。 在加边删边的时候顺带维护这个变量的值。维护策略如下。

在A,B点之间加边时：找到AB点中度数更小的点，不妨假设为A点，然后遍历A点已有的边，这个边的另一个端点记为C, 每遍历一个C，就判断一下C和B之间是否有边，如果有的话，那么ABC三者就可以因为AB之间的边的加入而构成一个三角形，这时候让cntTriangle++;

在A,B点之间删边时：在删边时，直接让cntTriangle减去这条边所承载的三角形数量，这个“边所承载的三角形数量”可以动态维护，动态维护的过程为: 在加边的时候，若成了三角形，则让这个三角形的三个边的“所承载的三角形数量”都加1; 在删边的时候，若破坏了三角形，则让这个三角形另外两条还存在的边的“所承载的三角形数量”都减1。

之所以要引入“边所承载的三角形数量”, 是为了尽可能地提高程序的性能。

2.2.4 “qlm” 指令

这个指定的含义是查询图中过某一个点的最小环。我采取的是最短路径树的算法。这个没有进行动态维护，完全地就是来一次qlm指令，就跑一遍最短树算法，性能也还算可观。

具体实现为(假设qlm要查询的节点为A)：首先以A为源点, 彻底跑一遍dijkstra算法，得到源点到包含全图的点的最短路径容器，该容器叫做distances。并且在跑dijkstra算法的过程中构建并查集，最后抽象出以A点为祖先的最短路径树。然后对树上的节点进行两两遍历，这个“两两”的选取原则为：这条边不能在最短路径树上且边的两个端点必须要符合以下两种情况中的一种：

(1). 两个点一个是源点，另一个点不是。

(2). 两个点都不是源点, 但是两个点位于最短路径树上面的两颗不同的子树上。

遍历的过程中，每按照以上原则拿到一条边(假设这条边的两个端点分别为B C点)，其实就对应着在图中挑出了一个经过A点的环，这时候我们要记录下这个环的总权值，计算方法为：distances容器中记录的 B点到A的距离+C点到A点的距离+BC这条边的长度。 从所有经过这样的计算所得到的环的权值中找出一个最小的环就可以了。

Part3 性能分析

3.1 性能优化策略

本单元对我们的算法性能有着不小的要求，因此便在此处概括一下我的算法策略中所存在的“优化性能”的要素点。

对于查询两点连通性的问题，我本来采用了深度优先搜索的方法, 但是在和同学的程序进行了对比后发现这样的方法效率并不高，因此我又在网上学习了并查集的思想，并将算法换成了并查集，性能有明显改善。对于查三角形和查极大连通块的问题，我采取了动态维护的方法去做。也就是在加边删边的时候, "顺带地"做出一些为这些指令服务的操作(上文有说具体怎么操作, 此处不再赘述), 想以此来提升算法效率。但是我发现这样做的话又会出问题，在hw11的强测中，会有对qlm的压力测试，这种测试没有任何查询三角形和极大连通块的操作，这样，在加边删边时的动态维护过程便会毫无作用而占用cpu时间, 这也导致了我的一个强测点超时了。我的解决方案是将动态维护延迟到需要的时候再进行，也就是在需要查相关的信息时, 再对与这些信息有关的变量进行动态维护， 这样的话，就可以避免不查相关信息但是对他们的动态维护白白浪费时间的情况。对于删边维护三角形数量的问题，我引入了"边所承载的三角形数量"这一属性来进行优化。本来我想到的方法是，和加边一样，删边的时候通过遍历相关的边来更新cntTriangle的值，但是感觉这样又要有不少的循环，有点不放心。因此，我就新建了一个MyRelation类，这个类有一个属性是cntTriangle, 表示这条边所承载的三角形数量。在加边删边的时候对相关的边的这一属性进行动态维护(具体维护方法在上文已经说了), 然后当删边的时候我们直接减去对应边的这一属性的值就ok了，不需要再遍历了。对于查询bestId的问题, 我采取了必要时维护的策略来提高性能。核心在于"必要时"。具体地来说就是, 当查bestId的时候我跑一遍这个算法, 这时候我将跑出来的结果存进一个MyPerson类的bestId属性中。下次再查这个人的bestId的时候, 我就不跑算法了, 直接返回这个属性的值。但是这个bestId有可能因为这个人认识了别的新人，或者是本来认识的人的关系变好变坏被删除 而让bestId有了新值，而不能直接return 上次存起来的bestId。 对于这种情况我采取的优化方式是: 当原本的bestId被破坏时, 我不会立即跑循环来更新bestId，我会将一个变量isNewBestId标记为false，表示说这个bestId可能并不是一个正确的值. 这样一来, 每次查qba的时候，我检查一下isNewBestId的值，如果是true，那么对于删边需要重建并查集的问题，我优化的策略是按需动态维护。我并不会在一条边被删后立即去重建并查集，而是会在删掉后下一次需要用到并查集的时候再进行并查集的重建，避免出现每次删边都重建并查集但是却并不需要用到新建的并查集而白白浪费了重建时所花的cpu时间的情况。对于qlm, 我的优化在于换了算法。我第一次采取的算法是这样的(来自讨论区的一个方法): 遍历源点的每个"邻居", 对于遍历到的每个邻居, 我将源点和他之间的边删掉， 然后以这个邻居为源点跑一遍dijkstra算法, 找到从邻居点到qlm 查询对象之间的最短距离, 这个最短距离加上所删的边的长度就是一个环的总长度, 在所有得到的总长度中取到最小值就可以了。同时为了优化性能，我还在dijkstra中设置了提前终止条件，也就是，找到目标就不再跑dijkstra了，而不是每次都无脑地全图跑一遍。

但是在测试的过程中，我发现这样的算法根本跑不了qlm的压力测试, 太慢了。解决方案是：换算法。所换的算法就是我在2.2.4中所说的"最短路径树"的算法，这个的好处就在于，每次查询，我只需要跑一遍dijkstra算法就可以了, 这使程序的效率有了明显的提升。

3.2 规格与实现分离

对于"规格与实现分离"这个东西，我的理解是，**让 写规格 和 实现规格描述功能代码 这两件事，分别由不同的人去做，以达到分离的效果。**比如对于一个程序，老板写一个这个程序的规格要求，然后把这个规格要求交给开发团队，让开发团队去完成这个需求，类似于此。这样的话，规格编写者可以更专注于需求的理解和规格的准确定义，而实现者呢又不需要关注规格背后的逻辑，只需要按照规格翻译就可以了，可以提高开发的效率。

此外，规格化的引入相当于是在"需求->实现"这之间加了一个规格化的过程, 变为:“需求->规格化->实现”，这样的话在出现了bug 的时候，我们就会分析，是"需求->规格化"出了问题？ 还是"规格化->实现"出了问题，从更细的角度去解决问题。在我的理解看来，“需求->规格化” 和 “规格化->实现” 的完成难度和出bug的概率都是比需求直接到实现要低的，相当于把这个直接的过程细化了嘛，比如高考的一道立体几何题，把解题的过程从中间断开，着眼于各个难度更小的小阶段去做，每做完一个阶段都检查一下这个阶段的正确性，这样的话是更可能得到有一个没bug的题解的。

Part4 ok测试分析

4.1 oktest方法的意义

在我看来, oktest方法的根本意义在于,检测一个目标方法是否得到了正确的执行。一个方法是否得到了正确的执行就在于，这个方法是否有正确的返回值,是否对方法之外的程序产生了正确的影响(应该正确地修改需要修改的某些对象的内容，不应该修改不能修改的对象的内容)。那么oktest方法就是从这两方面出发对照着规格逐条检查方法执行前后的数据是否符合规格要求, 以此来判断这个方法是否得到了正确执行，这是一种确保程序正确性的思路(确保程序正确性有很多方法，其他的比如还有代码走查等)。如果我们通过编写oktest方法确保了我们所有的方法都得到了正确执行，那当然我们的代码就不会再出现错误。 以上仅代表我个人通过亲身学习对oktest方法产生的真实理解，不一定够全面。

4.2 改进建议

非要说对oktest方法的改进建议的话，那么我觉得可以让oktest方法在诊断到程序执行出现了问题后给出尽可能详细的报错信息，因为实际工程中可能oktest需要检测的内容是比较多的，如果只返回一个错误编码的话，可能对于我们程序员来说很不直观，返回具体的报错信息能让我们有更好的测试体验。

此外，既然写了Oktest方法，那就应该让所传的参数高度符合jml规范，比如我们的oktest方法，由于方法参数以hashMap的容器给出，这个容器key和value的一一对应关系就已经保证了不可能出现某些jml描述的错误情况(比如，记这种错误的编码为3)，而一个方法执行过后又确实可能会出现3号错误，所以感觉这其实可能是稍微有些不合理的，可以在传入的参数的形式上做一些改进，让其彻底能对标每个jml规范进行检测。

Part5 心得体会

这个单元给我的最大的教训是, 程序一定要按照可以应对最坏数据情况的标准去写，这样的话，强测不管怎么测，算法效率都不会出锅。我就是在此方面有了疏忽, 才使得有一个点因此而ctle。不过也让我感到欣慰的是，本单元的难度确实有所降低，主要在于官方代码已经规定好了代码架构，我们仅需要"完形填空"即可，相较于递归处理表达式以及电梯，本单元对我来讲相对更轻松。不过自省一下感觉自己并没有熟练地掌握JML语言，尤其是自己去写JML语言，还非常不熟练，个人建议，可以适当地在课下作业中加上一些手写JML的元素，这也能让我更适应上机实验…

除此之外，通过本单元的学习，我第一次了解了使用规格语言辅助的思想，通过这种方式，我们可以通过规范注释描述方法的前置条件、后置条件和类的不变式等，达到在代码中明确规定预期行为的目的，以帮助我们尽可能地避免编写错误的程序。同时，这一单元涉及了很多关于图论的算法知识，比如dijkstra的实际使用，并查集的使用，最小环的查找等，这些都让我感到收获丰富。

最后，在这个单元的学习中，我们水群的同学们为我提供了很多解决问题的参考思路，作为没什么算法基础的我来讲，见多识广的同学们在群里提供的算法思路对我来说是一个非常大的帮助，在此表示非常感谢！

anyway, oo 接近尾声, 希望自己能继续保持着一个良好的心态迎接oo的最后一个单元！