OO-Unit3-Summary


OO-Unit3-Summary

测试过程

各种概念的辨析

黑箱测试

黑箱测试是根据功能需求来测试程序是否按照预期工作,是要从用户的角度分析.尽量发现代码所表现的外部行为的错误.黑盒测试应该是由测试团队来完成的.根据某个给定的输入,应该能够理解并详细说明程序的预期输出.

基本流程:功能需求–>产生测试用例–>被测程序–>输出实际结果–>与预期结果比较–>分析功能是否实现.

类似于OO的中强测。

白盒测试

白盒测试是测试人员要了解程序结构和处理过程,按照程序内部逻辑测试程序,检查程序中的每条通路是否按照预定要求正确工作.它主要的针对被测程序的源代码,测试着可以完全不考虑程序的功能.

基本流程:源程序–>分析程序内部逻辑结构–>流程图–>制定测试用例–>被测程序–>执行路径–>覆盖情况分析

单元测试

是指对软件中的最小可测试单元进行检查和验证。这个单元可能是一个函数,一个类等等。

回归测试

在对软件进行修正后进行的有选择的重新测试过程.一般要重复已用的测试用例.目的是检验软件在更改后所引起的错误,验证软件在修改后未引起不希望的有害效果.放到作业里面就是修完bug再测试

功能测试

根据产品特性、操作描述和用户场景,测试产品的特征和可操作行为,以确定其满足设计需求。

集成测试

其中软件的不同模块被集成并作为一个整体进行测试。我认为是对立与单元测试,将程序作为整体测试。

压力测试

不是在常规条件下运行手动或自动测试,而是在计算机数量较少或系统资源匮乏的条件下运行测试。通常要进行软件压力测试的资源包括内部内存、CPU可用性、磁盘空间和网络带宽。压力测试涵盖,性能测试,负载测试,并发测试等等,这些测试点常常交织耦合在一起。

可以类比电梯单元的超大吞吐量数据和本单元较为极限的数据测试。

测试工具

基本采用了数据生成器+对拍脚本的思路。将生成好的数据投喂到jar包中,由于本单元的结果校验十分简单,直接使用powershelldiff指令进行文本对比即可(其实用shell语法写powershell

数据构造策略

首先需要保证的是数据的量必须保证足够由于输入限制1w条,我基本也保持了这个标准。但是在部分情况下为了挑战极限情况,我也有部分10w+条的数据测试。

我的数据生成器指令生成权重由一个给定的字符串决定,虽然很笨,但是很好用,通过给定字符串来生成对应的指令。也可以采用ticket[i]=log2(random(0,1))/weight[i],选出其中最大者作为生成的指令编号。(时间原因,没有加上

既然可以决定不同的指令的权重。构造策略基本就是对于不同部分的强测和综合强测。

部分强测主要是生成以Group,Message,Person,Network这几个类为主体的指令进行测试,例如对于针对Message的测试就只生成AddPerson,AddGroup,AddMessage,SendMessage,AddMessage等指令。

综合强测就很简单了,对所有指令按照设定好的权重进行生成。

为了加强测试,我有意增多了ar的数量。

其中为了避免过多的无效指令,我对RandPerson,RandMessage,RandGroup等进行了限制,存下来当前社交网络的部分状态,例如组中的人员id等等,以保证指令的有效性,而不是一大堆异常抛出。

对于图的数据构造,我只采用了ap:ar:qlm = 2 : 10 : 1的比例进行了随机生成,在这种情况下,1w条数据勉强称得上有强度,但是想要真正考验qlm等性能,还是太年轻了。。。这也是本单元最后的折戟处。

对拍加生成地址:
https://github.com/UyJZ/OO_BUAA_Unit3_Generator

架构设计

框架

基本上按照了课程组的要求,本单元在框架上的自创空间并不大。

hw_9

hw_9中,我新增了Block连通块类,类似于并查集的结构,但是并没有类似于父亲节点的结构,单纯采用了HashSet<Person> set来存储personnetwork增加了ArrayList<Block> blocksHashMap<Person, Block> map作为PersonBlock之间的映射。

hw_10

hw_10新增了Update类用来提供动态维护的具体操作。

hw_11

hw_11Block中新增了Dijkstra等方法用来计算最小环。

性能问题

hw_9

性能问题主要在于qci,qts,qbs三条指令上,在想到将连通块直接视为一类之后采用动态维护的方法虽然增大了addPersonaddRelation的成本,但是直接将qciqts等指令$o(n{2}),o(n3)$的复杂度直接降为$o(1)$。

本次作业没有出现问题。

hw_10

由于modifyRelation的新增指令,破坏了Block的连通性,因此必须在mr出现的时候重新构建连通块。

我主要采用了dfs去搜索以person1为起点是否存在新的到达和person2的路径,在搜索的过程中,如果不存在该路径,则其一定会走遍每个与person1可达的person,将其存入一个HashSet<Person> Set中,若最终未能发现路径,则该Set为新的BlockPerson集合。

新增的QueryCoupleSum指令,主要采取了动态维护的方式,同时注意删边时的动态维护。

public int updateCouple(MyNetwork myNetwork, int id1, int id2) {
        int best1 = ((MyPerson) myNetwork.getPerson(id1)).getBestAcquaintance();
        int best2 = ((MyPerson) myNetwork.getPerson(id2)).getBestAcquaintance();
        int couples = myNetwork.queryCoupleSum();
        HashMap<Integer, Integer> bestAcquaintances = myNetwork.getBestAcquaintances();
        if (bestAcquaintances.get(id1) != best1 || bestAcquaintances.get(id2) != best2) {
            if (bestAcquaintances.get(id1) == id2 && bestAcquaintances.get(id2) == id1) {
                couples--;
            }
            if (best2 == id1 && best1 == id2) {
                couples++;
            }
            if (bestAcquaintances.get(id1) != best1) {
                if (bestAcquaintances.get(bestAcquaintances.get(id1)) == id1
                        && bestAcquaintances.get(id1) != id2 &&
                        bestAcquaintances.get(id1) != id1) {
                    couples--;
                }
                if (bestAcquaintances.get(best1) == id1 && best1 != id1 && best1 != id2) {
                    couples++;
                }
            }
            if (bestAcquaintances.get(id2) != best2) {
                if (bestAcquaintances.get(bestAcquaintances.get(id2)) == id2
                        && bestAcquaintances.get(id2) != id1 &&
                        bestAcquaintances.get(id2) != id2) {
                    couples--;
                }
                if (bestAcquaintances.get(best2) == id2 && best2 != id2 && best2 != id1) {
                    couples++;
                }
            }
            bestAcquaintances.put(id1, best1);
            bestAcquaintances.put(id2, best2);
        }
        return couples;
    }

本次作业没有出现问题。

互测中发现有房友在AddMessage并未按照JML规格将其插入到第0处,而采用了HashMap<Integer, Message>的结构存储。

hw_11

本次作业的主要性能问题是qlm指令,意外在此处马失前蹄。

周四晚上想到了跑出最短路树,将不同树上的节点相连或直接选择一最短路树的节点与起始点相连即为最终所希望的形式。(自己写了非常繁琐的证明,就不献丑了,后来才发现网上一大堆。。)

使用Dijkstra跑一遍再遍历一下节点选出最小值即可。然后剩下的就直接交给了评测机不停跑去做音乐展示了。。。。。偷了懒,果然还是出现了性能问题。

在测试的时候我的图是完全随机生成的,qlm指令分布过于均匀,导致强度不足,在自己线下测试的时候基本能保证自己的数据在3s内跑完,误以为性能已经足够,随偷懒了堆优化的dijkstra,直接采用了朴素的dijkstra,导致强测一个点出现了ctle的情况。在修改为堆优化之后解决。

本次互测中发现房友有jar包和本地代码运行结果不一致的现象,将其错误数据交上去刀中也是薛定谔的猫一样不确定,猜测使用了某种未定义行为。

规格与实现分离

规格和实现确实完全没有关系,对于规格设计师而言,其最需要做的是通过简洁易懂的规格语言来描述需求,其具体的实现操作只与实现的工程师有关,充分体现了分工的思想,就好像计组和os中的交给软/硬件处理。很符合rwg老师的雇个程序员帮你做的至理名言(

OKtest

oktest是一种对函数的结果和副作用等等的校验手段。其基于规格设计,如果实现者并未完全理解规格,可能会导致Oktest的校验完全无效。

故我认为Oktest可能属于规格设计者的工作范畴,实现者应该在调用测试方法的时候将各个数据封装成合适的容器传入测试方式。

Oktest的实现依赖于规格设计,而且其校验方式应当独立于设计成果的方法,比如在校验qts的时候不能把beforeData转化为Network的属性再调用qts方法进而校验成果。这相当于默认该方法为正确的,并不符合我们对于测试的需求。

而且校验应该是不需要对性能有太多要求的,其是通过绝对正确的朴素方法校验通过某些算法实现的方法。因此校验一般就是跑很多次循环即可。

体会

关于测试

本单元我第一次自己动手做数据生成器,并且有着不错的覆盖度,因此保证了每次作业的正确性,但是图论的数据生成依旧是我的短处,没有刻意去构造稠密图,稀疏图等数据导致我在第三次作业中没有发现潜在的性能问题。

Oktest可能是一种潜在的规格设计者提供的测试接口,从中我感受到了单元测试以及常见的一些测试手段。

关于JML

坦率的讲,JML的可读性不算强,但是确实十分严谨,非常全面,标注了副作用和边界条件,感觉像是在读离散一的数理逻辑式子。JML就像是一大堆拼图,可能在将拼图拼出来之后也可以很清晰的读出来整幅画的模样,而且对细节的理解可能更到位,但是将拼图拼出来的过程是较为耗费时间的,因此JML这样的规格设计语言的使用见仁见智。

其他

回顾了一些图论的经典算法,不至于都忘干净(


文章作者: UyJZ
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 UyJZ !
  目录