你好！本文章为该博客的第十三篇文章！

本文章包含北航2025面向对象设计与构造第三单元的博客作业内容，期望同学们通过本次博客作业对该单元内容有一定了解。

本文章已经投送至本单元博客作业！

可能你已经发现了，本文章并未在完成后被及时投送至博客中，所以这其实是一个有点失去时效性的填坑投稿……

需要注意的是，本文仅完全适用于北航2025OO课程，对于之前和之后的课程，课程部分内容可能会发生变动，发生冲突时请以当前课程为准！

以及，如果本文章涉及学术诚信问题，请第一时间和我联系，我将及时做出修改，谢谢支持！

（顺便，JML在现在真有用吗.jpg）

北航2025面向对象设计与构造第三单元总结

前言

本单元第一次强测出现错误。同时也做了第一次研讨课个人分享。

总之，本单元最重要的经验是：把正确性托付给规格的严谨阅读，把性能托付给自己的复杂度识别。

大模型与规格化设计

一个显而易见的事情是，LLM的出现让写代码在某种意义上成了一种体力活。

但是仍然存在一个问题：如何让LLM写出准确的代码。这个事情取代了写代码本身，成为了困扰我们的一个问题。

当然，现在有许多通过改进LLM的方法解决这个问题。但是在这门课上，也许我们有了另一个强而有力的工具来诱导LLM生成准确的代码：规格化设计。

在大多数时候，我们写代码时经常会选择直接根据需求给出实现，或者根据需求设计一个架构，然后直接在架构里填充各种实现。

不过，不论是第六次实验课，还是这次作业的方方面面，似乎一切都在给我们一个强烈的引导：我们可以在“设计架构”和“完成实现”中间，插入一个“规格描述”。

其虽然不能直接解决问题，但其提供了一种验证实现的方法，同时也是描述功能的手段。而其最大的问题在于，由于其是使用完整严谨的规格描述语言进行了描述，故会有不可避免的额外工作量。

此时，我们可以让LLM出手。通过相对严谨的自然语言描述，我们可以使其给出更为准确的规格化描述。

相反的，也可以选择通过JML翻译出其对应的语义，从而加速我们对代码的理解。实际上，本单元后半部分作业中我就采用了这样的做法。

同时，有了JML的约束后，我们也可以通过类似OpenJML的工具反过来验证实现的正确性，降低了实现的验证难度。

人类智慧与性能优化

尽管本单元中我并未产生性能问题，但是在规格实现与不断互测的过程中，仍然识别出了一些问题，诸如（如无特殊说明，以下符号中 $n$ 代表当前图中人数， $m$ 代表当前图中关系数，$q$ 代表询问数）：

• 对于 queryTripleSum 方法：
  • 朴素的二重循环实现的复杂度显然是 $O(n^3)$ 的，此时一定会引发超时。
  • 对于“将其按度数大小转化为有向图，在有向图上找环”的复杂度是 $O(m\sqrt{m})$ 的，实际上也会引发超时。
  • 对于“在关系增删的同时维护’因为这个关系的变化而增加或删除的三元组个数‘”的做法，其做到了查询复杂度是 $O(1)$ 的，代价是增删关系时复杂度会增至 $O(n)$，根据本次作业的要求，其实际上是合理的代价分担。
• 对于 queryBestAcquaitance 方法，尽管其在第九次作业中性能要求仍然为 $O(n)$，但在第十次作业中，由于 queryCoupleSum 的出现，使得其要么进行类似dirty bit的标记，要么要求查询复杂度本身降至 $O(\log n)$ 甚至更低。
• 对于 queryTagAgeVar 方法：
  • 朴素的二重循环实现的复杂度显然是 $O(n^2)$ 的，此时一定会引发超时。
  • 对于“遍历所有 Tag 内的人所包含的所有关系” 的做法，其复杂度是 $O(n+m)$ 的，尽管复杂度看起来正确了，但是由于小型完全图的存在，使得其在常数方面实际上是不过关的，仍然有超时的风险。
  • 一个更好的做法是，在维护关系的增删改的同时，对每个 Tag 都进行相应的动态维护，尽管看起来更复杂了，但复杂度反而降到了 $O(q)$。
• 对于 deleteArticle 方法：
  • 其所带来的影响是会对 Person.receivedArticles 带来随机访问和删除的操作，从而在其实现为单纯的线性表时，单个人的 removeArticle 方法复杂度是 $O(q)$ 的。这似乎没有问题，但是当我们需要对一个 OfficialAccount 中的所有人删除某个文章时，整个方法的复杂度就来到了 $O(q^2)$，这就不可接受了。
  • 最正确的方法是弃用单纯的线性表，使用索引数据结构辅助链表，在删除文章时可以快速定位到待删除节点，再结合链表删除元素的高效性解决问题，复杂度可以降至 $O(q\times f(\text{find}))$，其中 $f(\text{find})$ 为使用的索引数据结构查询单次的时间复杂度。
  • 当然，由于Cache的存在，实际上单纯使用 ArrayList 也可以通过强测。

然而以上对性能问题的描述其实只是本单元对实现要求的表象，其真正内涵其实无外乎以下二句：

1. 不能完全复刻规格描述；
2. 任意一个单次操作复杂度应该在 $O(q\log q)$ 以内，且常数不能太大。

对于前者，其需要对JML的本质有深刻理解（即，规格与实现分离）。具体来说，JML实际上只是对方法运行前后的对象状态进行了约束，至于这个状态变化是如何实现的，实际上不重要，JML也并不关心，这也就意味着“怕写错从而不对JML给出的实现进行修改”是一种非常错误的行为。当然，为了保证正确性，可以采用迭代开发的方式，先给出一个正确的实现，再进行逐步优化即可。

对于后者，其需要我们（实现需求的人）对实现本身的复杂度有准确的了解。实际上，根据研讨课经验分享的问答反馈来看，许多同学并不清楚应该用复杂度来分析程序，当然不知道哪里会超时，这也许才是造成无数个性能问题的元凶。解决这个问题的方法……可能必须要课程引导和学生个人同时注意到了。

迭代开发与架构设计

由于本单元的作业形式为“根据课程组给出的JML和框架约束实现完整程序”，故可能会有同学认为架构设计的作用在本单元实际上没有被考察，故无需关注架构设计带来的影响。

然而，实际上课程组给出的规格约束可能存在一定的属性管理混乱的问题（如，Network 中的 articleContributor 本意是管理文章对应的发布者，但个人认为此信息丢给 OfficialAccount 管理更加妥当），且一部分查询方法实际上只依赖于 Network 的一部分性质（如 queryTripleSum,queryShortestPath 等方法只依赖图结构性质），故如何在适应这些问题的同时，尽量进行解耦，实际上仍然是一个值得关注的设计问题。

具体而言，我在课程组给出的约束下做了如下调整，使之信息管理更加清晰：

1. 将关联较强的数据进行打包处理。如对于 Person.acquaintances 和 Person.values 而言，显然其管理的是所有好友及“伴随这个好友关系的值”，即好友本身和关系值的联系更深，因此我实现了 AcquaintanceInfo 类将此二类信息进行打包，保证查人和查关系值一定是一一绑定的。
2. 将与图结构性质关联较强的询问抽象为单独的类和方法。具体而言，我设计了 Graph 类型，将人和关系和关系值抽象为点和边和边权，放入 Graph 类中同步维护，同时给出 GraphSolver 类作为询问的处理方法类。当出现仅涉及图结构性质的询问时，我在 GraphSolver 中通过访问参数中 Graph 的各项属性对该问题进行求解，而仅将 Network 到 Graph 的部分交由 Network 进行处理。（事后证明，对于本单元作业而言，实际上 GraphSolver 类是多余的，合理的做法是将其合并至 Graph 中）
3. 尽可能把信息移至组合或聚合至 Network 的类中。如，对于 articleContributor 的维护，实际上我是在 OfficialAccount 内进行维护的。

测试与潜在问题查找

测试类型的适用场景

从过去到现在学过的有关“测试”的名词其实有很多，诸如单元测试、功能测试、集成测试、压力测试、回归测试等。但是在实际作业中，使用这些名词对应的测试方法进行测试是一个比较困难的事情。码量大和数据难以设计当然是一个问题，但是更主要的问题在于，我们什么时候该考虑怎样的测试呢？

对于回归测试，其应用场景比较显而易见：

1. 每当我在bug修复时，需要验证此bug的修复会不会引入其他bug时；
2. 每当我进行了性能优化后，需要验证这种优化方法会不会出现bug时。

对于压力测试其实同样好分析：在本单元作业的功能全部完成后，需要分析性能较差的部分时，往往需要压力测试才能发现需要优化的地方。

但是对于单元测试、功能测试和集成测试，其功能其实有一定的相似之处：测试正确性。于是大家总是会有一种期望：只要对于某种测试过关了，其它测试就没有必要了。

但是，这三种测试其实对于测试的粒度而言是不同的。从单元到功能到集成：

• 对局部的正确性关注递减；
• 对系统整体正确性的关注度递增；
• 对测试数据要求的侧重点差异显著。

我的经验是，需要进行单元测试获得对方法各个分支正确性的确认，再通过功能测试获得对连续一类方法执行的正确性的确认，最后再用集成测试确认对整个系统的正确性。

如何构造数据

上文中提到了“对单元测试、功能测试和集成测试，其对测试数据要求的侧重点差异显著”，那么如何根据这种显著的差异来构造数据呢？以及，如何构造压力测试的数据呢？

就我的经验而言，对本单元作业来说，单元测试实际上只需要把分支的覆盖率拉满其实就够了，基本上只要不是看漏了一个分支都不会出大问题的。

而对于功能测试，其更需要把一段方法连续起来看，关注一下整套操作前后的效果即可。

至于集成测试，其实在构造时都去寻找”阅读单个功能的JML时无法联想到问题“的部分构造就行。比如说对于 sendMessage 和 deleteArticle 两个功能的组合而言，其关键点是要想到”只要我转发了两次文章，receivedArticles 中就会出现两个相同的id，那么删除文章时两个id都要删“，而这一点在只测试 sendMessage 时或只测试 deleteArticle 时往往会被忽略。

同时，压力测试和功能测试也有一定的相似之处，大部分成功的压力测试都来源于对某个功能的反复使用，比如说反复对所有人关注的 OfficialAccount 进行 contributeArticle 和 deleteArticle 操作就可以卡中维护 receivedArcitles 时性能较差的实现。

规格与单元测试

实际上，相信大家会注意到本单元作业的这样一个特性：只要我对各个规格的实现是正确的，那么整个作业应该就是正确的，那么似乎只需要单元测试就可以完成本单元作业的所有测试工作了。

这话其实确实没错。本质上，规格确实是对每个方法的运行要求约束，只要实现正确，状态变化结果就一定正确，那么错误就只可能出现在规格里，而规格的正确性由课程组来保证，当然是正确的。

（所以我们甚至可以认为，规格就是一种压缩后的单元测试）

除了一个问题：我怎么知道我的单元测试一定能检查到规格的所有约束？或者说，Junit测试检验代码实现与规格的一致性的效果如何保证？

这是一个很吃”实现技巧“的问题，我可以举出很多例子来保证不写漏：按规格给出的关键词拆分，为每个字段写一个检测运行前后不变的方法，尽量保证检测方法和JML实现一致……

这也是一个很吃”数据构造能力“的问题，需要你把每个分支触发一遍不说，还要考虑一些”尽管JML只有一句话，但是实现很可能有分支控制/产生意料之外的异常“的情况（比如空图的构造和完全图的构造）。

但是，归结下来其实也就一句话：手要稳，要死扣JML，还要自行思考出JML说了，但实现者很可能设计出的分支。

心得体会

第九次作业的强测不通过还是给了我一个很大的教训的。正是在从本次作业的错误，诱导我去发掘如何不读错JML的方法，从而想到了LLM；也是本次错误让我找到了更加合适的测试数据，顺带着发现了一堆的性能优化的地方。（甚至因为反复阅读JML和指导书，指导书中的一个缺陷也因此被找到了）

总之，一次错误带来的经验比八次成功还重要，这已经超越分数带来的意义了。

结语

把正确性托付给规格的严谨阅读，把性能托付给自己的复杂度识别。

现代工具的作用是严谨快速的阅读规格，而现代人类的作用则是在机器翻译出的规格上展现人类智慧的效能。