OO第三单元总结

前言

本单元的作业相对前两个单元来说简单，具体需要做的就是根据提供的JML撰写相应的代码，重点来了安全按照规格编写代码只能确保正确性，却不能保证性能。这也充分体现了JML这种契约式编程下，设计与实现相分离的特点，当然这里的分离并非完全分离，实现需要在保证符合设计的要求下尽可能的达到高性能的目标(毕竟没人喜欢低性能的程序吧！)。

虽说简单，但是为了表示严谨而长篇大论的JML在描述某些规格时却异常繁杂，而这也使其成为了本单元与算法设计(因为低性能的算法真的会挂点QAQ)并列唯二的重中之重。

第九次作业

作业要求

维护一个社交网络,并对其中用户及之间关系进行管理.用户可通过标签管理与自己存在关系的其他用户.

• 在阅读官方包给定的相应的JML规格后,依据规格 实现相应的Person,Network,Tag类来分别implement相应的接口,需严格满足接口给出的JML规格定义.
• 阅读关于异常行为的描述,结合官方包给定的异常类的javadoc,体会异常处理的流程.
• 同时还要在主类中调用官方包的Runner类,载入实现的类来运行程序.
  实际上就是将接口的JML规格实现成相应的代码.

强测bug

1. 对于queryBestAcquaintance()这个方法，我是在每个Person类中以熟人集合来维护一个大顶堆Heap通过返回堆顶完成函数，而我却没有考虑到modifyRelation()时，value值是负的不一定会使关系破裂，有可能只是关系淡了，因此也就是默认了不会关系破裂的情况下value都是正的，对应结点只需要向上调整即可，即adjustUp()函数，但是也有**value值是负的且关系仍未破裂的情况**，此时应该对应结点向下调整adjustDown()，因此，我修改了相应的adjustDown()函数，因为因为删除和仅是value值减小的向下调整处理并不相同，并在value正时调用adjustUp()函数，相反调用adjustDown()函数。
2. 将给定样例通过IntelliJ Profiler运行，得到代码中耗CPU时间最长的地方是并查集的find()方法中压缩时在相应结点的父节点的子节点堆中删除该结点，而这个维护时在子节点很多时是十分耗时的。一开始出于并查集中按秩合并的准确性考虑，我打算去维护每个结点准确的秩，(后来被Red学长教育了其实是无用功)采用的方法就是维护一个以结点id为键，其所有子节点组成的大顶堆为值的HashMap，但是这样的维护代价是极其大的，原先仅仅是为了获得熟人集中最大value的人的id而设计了大顶堆，但是其只有在真正的关系破裂的时候才会去进行删除结点的操作，而假如在并查集中设置大顶堆来维护每个结点的所有子结点，这样一来很有可能每次find()都要进行一次从堆中删除结点的操作，这样的开销可想而知，属于是胡乱优化了。因此，我向不准确的秩妥协了，也就是不去维护每个结点的准确的秩，即路径压缩时，并不会去修改相应的秩，虽然这样并不准确，但是很好的降低了并查集操作的时间复杂度，毕竟并查集的功能主要还是判断两个结点的连通性，而不是索求某个结点当前的秩，舍本逐末反而会弄巧成拙。

第十次作业

作业要求

在第九次作业的基础上，新增“公众号”和“文章”概念。即在维护已有Person、Network和Tag类基础上新增一些查询方法，并新建一个OfficialAccount类，完成诸如增删文章、维护关注者等操作。

强测bug

出现了一个点CTLE。原因出于我的求最短路径长度的算法复杂度稍高(真就高一点点QAQ)。我是通过bfs的方法完成求解，跳出大循环的条件是从队列队首取出的结点恰好是目标结点的时候，但是这样一来，可能会多遍历同一层的其他结点以及其相应的子结点，确有爆CPU时间的可能，于是我将跳出大循环的时机改为将目标结点加入队列的时候，这也是最快的情况，即”第一次发现目标结点的存在“，这时候只要赋值为头结点到当前结点的距离+1给相应的返回变量并退出即可。

第十一次作业

作业要求

在第十次作业的基础上，完成对消息收发的模拟。维护已有Person、Network、Tag和Officialaccount类，Person增加money和socialvalue等属性，Network增加管理消息的容器，以及相关的管理操作。

因此，需要增加Message类管理消息，其有三种子类``EmojiMessage、RedEnvelopeMessage、ForwardMessage`，注意这里指明其有三个子类，但并未指明一个消息一定是这三个子类，还可以只是父类。

强测bug

强测和互测均未发现bug。

本单元的测试过程

单元测试和功能测试(Junit测试)

由于本单元的每次作业都要求了Junit测试的需求，因此单元测试和功能测试方面算是略有心得了。

首先通过咨询大模型，得到单元测试的目的主要是验证软件中最小的可测试单元的行为是否符号预期，而功能测试的目的主要是验证软件的各个功能是否按照需求规格说明书的要求正常工作。

由于本单元每次作业都要求对一个方法写Junit测试并且还需要通过一些测试点才能拿到中测分(总是因为覆盖面不全而爆红的我暗暗难受)，其中对单个方法进行测试体现了单元测试的要求，而为了测试能够有较好的方法覆盖率，面向JML规格进行的功能测试就显得至关重要，主要是去考虑方法调用前是否满足了requires，调用后是否满足了ensures，以及是否只对assignable或modifiable修饰的变量进行了修改，这个是极其容易忽略的，在我第一次作业时就没有去考虑，虽然过了测试，但是在第二次作业的测试编写时有一个点——万恶的mid3，始终过不了，在浏览了交流群内信息后，我才幡然醒悟，因为当时的方法是pure的，也就是所有变量什么都不能修改，因此在方法调用后其实是要去判断是否有变量的属性因此被修改的，而这也正是我疏忽了要面向JML的严格测试导致的，因此全面的规格测试不只是requires和ensures，尤其要注意副作用的影响。

不过,u1s1,在完全利用规格信息来设计相应的Junit测试样例确实能够很好的测试潜在的问题(也能够更快通过相关的测试了),效果很不错!!!

集成测试

通过咨询大模型，我了解到了集成测试的目的为验证软件中不同模块或组件间交互的正确性，尤其注意模块间的接口、数据传递和协作关系。

由于我编写了与同伴安全对拍的评测机，因此我认为这一部分的测试，在编写的代码规格自带异常错误处理的情况下可以很好的在同伴间对拍输出结果中体现出来，因为不同类的协作或数据传递出问题，都可能会导致不同的错误输出，导致对拍产生不一致。进而根据对拍不同的位置定位到相应的输出，检查相应的代码。当然对拍只能解决于同伴之间的输出一致性问题，并不是一定保证正确，因为很有可能两个人都在同一点是犯同样的错误()(虽然可能性很小，但是我还是在CO课上和舍友达到了这一成就)。我的解决方法是：多找几个人()，因为我不相信所有人想的都一模一样。

压力测试

通过咨询大模型，我了解到了压力测试的目的是用来评估软件在超出正常负载情况下的稳定性和性能表现情况，具体体现在一些极限条件下，如高并发、大数据量等。

虽然强测的1w条数据并不是很大，但是本地测试未尝不可大数据量的测试，百万条起步未尝不可，其实在撰写单元总结前我都没想到可以这样，不过这确实是用来弥补随机数据低覆盖率的一个好手段，同时，大量的数据也可以很好的测试软件的鲁棒性。

回归测试

通过咨询大模型，我了解到回归测试的目的是验证软件在修改后，原有的功能是否仍能正常的工作，尤其是测试由于bug而修改的部分。

这对两次作业都有bug的我可再熟悉不过了，简单的来说，我的手段就是在修改代码后，再狠狠对拍，尤其将未出现bug的地方狠狠增多数据指令条数。

我认为这种测试确实是极为必要的，不只是在修bug的过程中，还有在完成新要求或者迭代任务中，毕竟谁都不想完成新的功能但是引入了新的bug或者触发旧bug了吧.

数据构造策略

Junit测试数据构造策略

此处主要是独立测试每一个类中的不同方法，可以采用@RunWith(Parameterized.class)的方式统一构造随机数据然后集中将该test类中的所有方法都测试一遍，也可以在每一个test方法中手动或者随机构造样例调用该方法然后利用Assert()断言判断结果是否符合要求。我是采用的两种结合的方式.

先利用@RunWith(Parameterized.class)方式,随机生成一个较为随机的人物关系网,由于方法还要去关注副作用的影响,因此这里会同时生成一个副本(注意一定要深拷贝,保不准测试的方法会去修改相应对象的变量属性,因此需要深拷贝完整的保存调用该方法前的相应对象.),此处具体如何随机是使用Random类的random.nextDouble()方法获得一个概率值,根据概率值大小决定是否给某两个人添加关系,或者添加消息等.随后就是根据requires和ensures,以及副作用等利用Assert的断言方法对结果进行真假相等判断.这里量大随机的方式很可能覆盖率极低,但是又不能超量测试(课程评测机会跑超时).因此第二种方式就孕育而生,通过手动捏造部分数据点来加强覆盖率,例如:我在第九次作业中,为了使人物关系网更加多样,手动搓了无边图,环图,完全图等,并通过在增减边的过程中检查前后置条件的方法来覆盖检查方式的多样性.

总之,随机提供大量的数据,而手搓提供高覆盖率,双剑合璧,天下无敌,虽然好像只要手搓的就能测出来,但是编写构造随机数据的过程还是收获满满的.

评测机数据构造策略

主要策略还是随机生成,其中涉及到具有唯一性的id指令,例如人,文章,公众号,消息等的id,我会将已经生成的id加入相应的池子中,当生成时赋予较大概率操作的已有id的,(具体方法还是使用random.nextDouble()来控制).但是为了使随机的结果具有一定的交互性,在完全随机生成之前会手动构建一个初具规模的人物关系,使之后生成的数据有一定规模的id池进行操作,同样也使操作更有意义.此外,由于每次作业都有新增的指令,而每次作业的重心自然应该在这些新增的指令,因此在随机生成指令的时候,我会根据给所有指令权重值大小决定生成哪些指令,(总数100),比如:像第三次作业的sendMessage指令肯定是重中之重,因此就有较高的权重值.由于本单元作业还有一个常见的错误就是超时TLE,因此能否在本地测试出超时也是至关重要,但是我发现可能是波动导致的原因,在本地超出10sCPU时间的样例,使用IntelliJ Profiler测试后都未发现很明显的超时.因此,我也是没有很好的手段来在本地判断是否超时,这也导致我有两次作业都爆了CTLE!QAQ.

对拍结果下来发现,这样的数据仅能检查到那些浅层的基础错误,例如:哪个异常抛出不同导致的error计数不同之类的,但是关于较为深层次的复杂数据并不能很好的生成出来,因为这样的样例往往都具有一定的排列顺序,脱离了随机的范畴了,比如:第三次作业的一个很严重的点,就是群发消息的时候,发送的文章如果接收者恰好也有,也是要照单全收的,而删除文章的时候,假如该人在删除文章的公众号下,则所有该文章都需要被删除掉(群发的+关注公众号后推送的),就是这个点让我在A房成功刀到了4个人,看来强侧数据也是我这样随机生成的嘛?

总而言之,随机生成肯定存在疏忽的地方,覆盖率是无法保证的,因此,在阅读相关规格进行代码编写的时候,一定需要关注好那些没有进行约束的地方,这些地方往往比约束严格的地方更容易暴雷.

关于大模型

本单元的作业中,我仅在部分算法实现时使用到了大模型,JML规格的理解都是依据提供的手册,指导书和官方包来产生的.

总的体验就是大模型确实在检索相关算法等方面更胜一筹,第二次作业的最短路径算法等一些重要算法都是询问大模型后才有一定的思路的.

当然我使用大模型并不是让其直接生成代码,毕竟我认为大模型再厉害,没有把所有的作业信息交给它,肯定也无法给出十分完美的答案.相反,我选择让其生成伪代码或者给出建议.例如:在实现存储人的接受文章的容器的时候,我提供给大模型的提示语是:”请针对实现一个可以从头部插入,任意位置删除O(1)复杂度的容器给出建议”,大模型就给出了”链表 + 哈希表: 使用链表维护元素的顺序，使用哈希表来建立元素和链表节点之间的映射关系。 这样可以快速定位到要删除的节点。”根据提示就可以自行实现相应的容器.

此外,在实验课上,我也学会了让大模型理解以及生成JML规格的方式.这样看来大模型确实势不可挡,那码农何以为立?不,在我看来大模型的强大完全是要借由使用者的介入而发挥出来的,一步步的引导大模型生成我们想要的结果或许是今后我们与大模型达到和解的关键所在.

架构设计

我的主要架构设计基本上都是跟着官方包中提供的JML规格走,不过,为了满足性能的需求,针对频繁进行增删改查等操作的容器进行了优化,例如:普遍使用HashMap来代替规格中的List使查询操作接近O(1)的复杂度.此外,我还使用并查集的方式构建图模型,解决连通性问题,使用大顶堆来实现查询最佳好友qba操作O(1),为遍历完成qcs提供了前提,使用双向链表+哈希表的自构建容器完成对于人的接受文章的存储.

其实上述很多考虑都是基于增量式设计思想的影响,也就是对于某一个查询指令,我们需要充分利用动态运行时的变化将一次建好再查询的复杂度分摊甚至细化下去,这样一来只要去动态维护相应的变量再在查询的时候直接返回维护的值即可,这样一来基本上就可以解决很多有关性能的问题了.

那么何为增量式设计呢？简单的来说，就是保留先前的计算结果用于当前的计算。因此为了保留，不可避免的需要采用合适的数据结构来进行存储先前的结果，所以数据结构的选择将制衡其计算便捷性。

那么为什么可以使用增量式设计呢?因为此次作业的网络的构建本质上是动态的，也就是说，其中的查找、增减操作都是一步一步进行的，而不是一蹴而就的，当然也不是多线程进行的，这就为我们进行保留相应的计算结果提供了依据，因为增减操作用于维护计算结果，而查找直接获取计算结果即可。

很简单的像获取一个容器的大小，我们可能会这样编写：

public int getSize() {
        return map.size();    
}

但是该方法(对于ArrayList、HashMap等容器)本质上就是用到了增量式设计，这些容器在内部维护一个变量size，当元素加入或删除时同时修改size的值，这样当你调用该方法时，会直接返回size而不会重新遍历，这样就可以使相关的查找操作的时间复杂度达到O(1)。

例子如下:

例子一:

在实现TagInterface接口的Tag类中，要求我们实现两个计算方法：getAgeMean()和getAgeVar()，根据相应的公式，我们可以定义两个变量ageSum和agePowSum分别来存储当前persons数组中所有人的年龄之和和平方和，这样一来调用getAgeMean()和getAgeVar()这两个方法时，可以如下编写：

public int getAgeMean() {
     if (persons.isEmpty()) {
         return 0;
     }
     return ageSum / persons.size();
 }

 public int getAgeVar() {
     int mean = getAgeMean();
     if (persons.isEmpty()) {
         return 0;
     }
     return (agePowSum - 2 * ageSum * mean + persons.size() * mean * mean)
             / persons.size();
 }

什么？你问我为什么第二个方法不化简，别问，问就是/的魅力。

例子二:

相信广览博客的大家一定知道了可以采用并查集来解决无向图中的连通性问题，那么我们是否可以根据面向对象的思想，将并查集封装成一个类，每次加入人、增减关系时去维护并查集？当然可以，根据并查集的思想，加入人的时候相当于添加了一个新的单元素集合；增加关系时相当于把对应的两个结点所在的集合进行合并；删除关系的时候(以下为笨人做法，如有更好的方法请大家在评论去不吝提出)，因为这两个结点原来有关系(没有的话该好好看看异常处理了())，因此这两个结点在并查集里一定在同一个集合中，在删除关系后，将这个集合里的所有结点恢复成刚加入的状态，然后再遍历这个集合每个结点的所有关系去合并，这样可以保证其余不相关的集合没有重建的开销，只对发生可能的该变的集合进行重建。

    public void addPerson(...) ... {
          ...
          disjointSet.add(p);
          ...
   }

    public void addRelation(int id1, int id2, int value) throws
    PersonIdNotFoundException, EqualRelationException {
        ...
        disjointSet.union(id1, id2);
        ...
    }

    public void modifyRelation(int id1, int id2, int value) throws PersonIdNotFoundException,
    EqualPersonIdException, RelationNotFoundException {
        ...
        HashSet<Integer> deleted = disjointSet.delete(id1);
        for (Integer key : deleted) {
            Person person = persons.get(key);
            HashMap<Integer, Person> friends = person.getAcquaintance();
            for (Integer friendId : friends.keySet()) {
                disjointSet.union(key, friendId);
            }
       ...
}

或许你会想到如果某个样例不进行查找操作，只增减了，那么阁下该如何应对呢？认栽。这时候当然就需要我们去平衡选择在维护和查找之间性能较优的数据结构了，因为只有维护成本以及保留的空间成本在我们可接受的情况下，使用该数据结构才能有去有效的提高时间性能的前提，不然维护着维护着就爆了,并查集杂合大顶堆的惨痛教训QAQ。

此外,像三元环个数,TagValueSum等量都可以采用此种方式实现高效的查询.

规格与实现分离

依我看来,规格不过是规定了最基础的需求,是相应软件需要达成的目标,有点像标定的起点和终点以及完成赛跑比赛前后运动员的变化.而实现脱离于此,只要能够贴合相应的规格就是符合要求的实现,而能够在符合规格要求的前提下还能做到较好的性能更是锦上添花,因此这就像远动员选择的到达终点的路线,好的实现能够找到较短的路线更快的到达目的地,至于如何找到这些路线就不是规格限定的.

这也是为什么甲方的要求总是天花乱坠,但是不同人的实现方案总是不尽相同,而在甲方的标准中,那些符合要求的方案总有一个比较好的原因.

总而言之,规格与实现的分离,使契约式编程成为可能,因为正是有了独立的规格才能尽最大可能的使实现达到的效果一致,规避掉二义性带来的问题.

心得体会

本单元最大的收获便是接触了规格化设计,它不仅仅是一种用于帮助验证程序正确性的辅助工具,更是那些复杂且重要系统(例如:大型工业和航空航天领域系统)的重要契约.在很多的场景下,规格化的设计是代替无法通过测试数据实现测试全覆盖的最好的检测方式,毕竟对于那些重要的系统,任何小bug都可能酿成大祸.