北航面向对象第三单元总结

2025-05-17

Java实现人际关系网络，可接收和发送消息，设有公众号和文章系统

一、测试过程

1. 名词解释

(1) 单元测试

单元测试是针对程序中的最小可测试单元进行正确性检验的过程。一个单元是应用程序中最小的可测试部件，例如一个函数、一个方法或一个对象。单元测试的目的是确保每个单元都能正确地执行其设计的功能。单元测试通常由开发者编写，可以自动化运行，以便在开发过程中快速检测和修复错误。在本单元中，单元测试主要依据JML规格对某几个方法进行测试。我们需要验证方法的实现是否满足其JML描述的。

(2) 功能测试

功能测试关注软件是否按照需求规格正确执行其应有的功能。它通常从用户角度或外部接口层面进行测试，不关心内部实现细节，它侧重于应用程序的主要功能，确保它们正常工作。功能测试通常由质量保证（QA）团队执行，可以在用户界面（UI）级别进行，也可以在没有用户界面的情况下进行，即通过 API 进行。

(3) 集成测试

集成测试是在单元测试的基础上，将已测试的模块（类）按照设计要求组合起来进行测试，检验它们之间接口的正确性和协同工作的能力。集成测试可以是单级集成，也可以是多级集成，逐步将不同的模块或服务组合起来进行测试。在本单元中，类之间存在复杂的交互。集成测试需要验证这些交互是否符合JML中对整体行为的描述，确保数据在不同对象间传递和修改时的一致性。

(4) 压力测试

压力测试是指在极端或异常条件下（如处理大量数据、高并发请求、长时间运行）测试系统的稳定性和性能。压力测试的目的是确定系统的稳定性和最大工作能力，包括响应时间、稳定性和资源消耗。通过这种测试，可以发现系统的薄弱环节，并确保在正常工作条件下系统不会因为过载而崩溃。对于本单元，压力测试主要包括：构建包含大量用户和关系的社交网络，执行大量查询或修改操作，测试CPU时间和内存占用是否在可接受范围内，避免超时 (TLE) 或内存溢出 (MLE)。JML本身不直接规定性能，但性能优化是实现高复杂度指令的关键。

(5) 回归测试

回归测试是指在软件发生修改（如修复bug、添加新功能、重构代码）后，重新运行之前的测试用例，以确保修改没有引入新的错误或导致原有功能退化。本单元中，每次完成新作业，在提交新版本前，都应运行针对旧有功能的测试用例，确保新代码没有破坏JML已规定好的行为。

2. 数据构造策略

通过搭建数据生成脚本，与他人进行对拍，是对本次作业的代码进行全面测试的好方法

(1) 核心思想

  • 状态维护： 在数据生成器中维护一个简化的系统状态，包括已存在的用户ID、标签、关系、公众号ID等，以及它们之间的关联。
  • 依赖性处理：许多指令的参数会根据当前维护的状态来生成。在添加关系时，倾向于选择已存在的用户ID；在向标签添加成员时，会考虑该标签是否已存在以及用户之间是否存在关系。
  • 概率控制： 数据生成器使用概率来决定是使用已存在的ID还是生成新的ID，这有助于测试边界条件和异常情况；同时通过为不同指令类型设置权重，控制各类指令在生成的测试序列中的大致比例，从而可以侧重测试某些功能或保证各种指令都有机会出现。

(2) 生成流程

  • 预填充：首先生成一定数量的初始用户，基于已创建的用户生成一定数量的初始关系，接着生成一定数量的初始标签，创建一定数量的初始公众号，为公众号贡献一定数量的初始文章，建立一定数量的用户关注公众号的关系；最后，存储一定数量的初始表情ID，这些预填充操作为后续更复杂的指令提供了必要的基础。
  • 循环生成：根据预先设置好的概率值，生成不同类型的指令，指令参数的生成也带有一定的随机性，与此同时，会更新数据生成器中维护的相应状态，保证数据生成器与被测代码的状态一致。

二、大模型辅助开发

1. JML->自然语言

  • 引导：请解释这段JML的含义，特别是 requires 部分的每个条件代表什么约束？”或者“这个 ensures 子句保证了方法执行后的哪些状态？
  • 效果：大模型通常能给出较为清晰的解释，帮助我快速理解规格的意图，尤其是在理解一些微妙的逻辑关系时，但对于非常抽象或复杂度很高JML，大模型的理解可能会有偏差，需要人工甄别，例如我在使用大模型辅助时，addMessage 方法中，如果文章不存在或者该人没有接收到这篇文章，都应当抛出异常，而大模型只给出了一个异常情况，导致我找了一段时间的bug。

2. JML->代码

  • 引导：请根据以下JML规格，为方法 methodName 生成Java代码的骨架，包括必要的检查和循环结构，同时在代码中加入注释，说明哪部分代码对应JML的哪个子句。
  • 效果：大模型可以生成包含前置条件检查、主要逻辑循环、以及基于后置条件返回值的基本代码结构。这可以节省一些基础编码时间，但往往需要人工大幅修改和优化，尤其是在数据结构选择和算法效率方面。大模型可能无法理解JML中隐藏的性能需求或最佳实现策略。它也可能忽略一些边界情况或JML中隐含的约束，本次作业中，如果采用这种方法直接编程，大模型往往无法给出一个复杂度较低的算法。

3. JML->JUnit

  • 引导：针对这个JML规格，列出一些需要测试的边界条件和可能触发异常的场景，而后，请根据这些场景为 methodName 方法设计一些JUnit测试用例的输入和预期输出，覆盖其requires和ensures子句。
  • 效果：大模型能提供一些有用的测试数据和思路，帮助我思考得更全面。有时它能想到一些我初步忽略的组合情况，但生成的测试用例可能不够深入，或者无法覆盖所有复杂的逻辑路径。就本次作业需要写JUnit的方法而言，大模型常常会忽视纯方法的检验。

4. 大模型引导方法

通过本周多次与大模型的交互，我总结了以下几点大模型辅助开发的几个实用方法或思想：

  • 提示词工程：模糊的指令只会得到模糊的回答。需要清晰地定义任务、上下文、期望的输出格式，如果可能，提供相关的JML定义、已有的代码片段或期望的输出样例，能帮助模型更好地理解任务。
  • 分解复杂任务：不要期望大模型一次性解决一个复杂问题。可以将大任务分解为小步骤，让模型逐步完成。例如，先让模型解释JML，再让其生成代码框架，然后针对特定部分进行优化提问。
  • 迭代式交互：对于一个复杂问题，通常需要多次交互。对模型的初步输出进行评估，然后给出反馈，要求其修正或改进。
  • 人工审查：大模型是辅助工具，不是最终决策者。对其输出必须进行严格的审查和验证，尤其是在正确性、效率和安全性方面。不能盲目信任其结果。

三、架构设计

1. 基础数据结构模块

(1) 并查集

  • 管理节点的连通性，支持节点的插入，关系的插入和删除操作。
  • 使用哈希表存储节点的父节点、秩，实现路径压缩和按秩合并优化，支持节点断开连接后的连通性重建。
  • 维护图的邻接表，维护并实时更新计算三元环数量，同时提供 BFS 方法计算最短路径。

(2) 自定义双向链表

  • 实现带哈希表的双向链表，支持高效的元素头插、删除和子列表查询。
  • 用于Person类管理接收的文章列表（receivedArticles），确保按时间顺序存储和快速访问。

2. 核心网络管理模块

  • 整个社交网络可以自然地抽象为一个无向带权图，节点代表 Person 对象，边代表两个人之间的关系，边的权重代表关系值。
  • 管理整个关系网络的实体（用户、官方账号、文章、表情、消息），同时集成Disjoint实例处理连通性、三元环等计算问题。

3. 消息模块

  • 消息基类：定义消息的基础属性。
  • 表情消息：携带表情ID，更新表情热度。
  • 转发消息：携带文章ID，处理文章转发逻辑。
  • 红包消息：携带金额，处理金钱分配。

4. 数据管理模块

  • 账号类：管理官方账号的关注者、发布的文章和贡献者统计，文章发布时自动推送给所有关注者。
  • 用户类：表示用户实体，维护熟人关系、标签、接收的文章、消息、金钱和社交值。
  • 标签类：管理标签下的用户集合，计算年龄均值、方差和标签值总和。

四、性能相关问题

1. 数据结构选择

  • 在本次作业中，大多数类的成员变量都需要按值查找，而规格中给出的定义往往是由静态数组维护的，这会使对象的查找和删除有较高的时间复杂度，可以采用 HashMap 对这些成员变量进行维护，实现 O(1) 复杂度的增删改查。
  • 对于 BestAcquaintance属性的计算，如果按照规格中的定义，每次查询时重新计算，会造成很大的时间开销，可以考虑将每个 Person 的 Acquaintance 使用 TreeSet 维护（这里需要注意防止 id 相减超出 int 范围），实现 O(1) 查询 BestAcquaintance，O(logn) 复杂度增删改关系。那么同理，虽然 BestContributor 这一变量的访问次数远不及前者，但也可以采用同样的方法进行维护，这里不再赘述。
  • 在关系网络中，可能需要频繁查询两人之间的连通性，在这里我们组中有两种考虑，一部分同学认为 BFS 的复杂度是 O(n)，在大多数情况下已经能满足需求，而另一部分同学认为需要采用并查集来压缩路径，实现更快的连通性访问。事实上，以上两种方法均能通过评测，并查集虽然查询速度快，但在删除关系时不得不重建其结构，在大规模数据测试下，性能其实差距不大。
  • 对于 receivedArticle 这一成员变量，作业的需求有三点，有序维护、头部插入、按值删除首个匹配元素，不难发现，使用任何一种 Java 内置数据结构均不能满足其需求，所以必须自己建立一个数据结构，在维护一个 LinkedList 的同时，维护一个从值到链表节点的哈希表，而在作业中，同一个值可能在链表中出现多次，所以哈希表的结构可以记作 HashMap<E, LinkedList<Node<E>>>，其中E为数据类型，Node为链表节点，实现 O(1) 复杂度的头插和按值删除。
  • 值得注意的一点，有部分同学在 receivedArticle 时，采用 LinkedList 维护不能通过评测，而 ArrayList 可以通过评测，对于头插操作 ArrayList 复杂度为 O(n)，LinkedList 复杂度为 O(1)，两者按值删除的复杂度均为 O(n)，ArrayList的复杂度反而更高，这是为什么呢？我们认为这与程序的局部性原理有关，ArrayList 在内存中是连续存储的，而 LinkedList 是分散的，同为 O(n) 复杂度情况下，ArrayList 的 cache 命中率更高，访存次数更少，其对性能的提升，超过了 LinkedList 降低复杂度的效果，但总体来说，自己实现一个数据结构才是一个更好的办法。

2. 动态维护变量

  • TagValueSum：动态维护该变量需要注意两点，第一，该变量有对称性，增删关系或关系的值时，需要将该变量改变两倍；第二，对该变量进行操作的可能性较多，增删关系或关系的值时，需要遍历每个人的所有 Tag，检查二人是否位于同一个 Tag 中，不能有遗漏，否则将会出错。
  • TripleSum：在增删关系时，需要对该变量进行修改，增减值为两个人的共同朋友，因为每对共同朋友加一条边，就能构成三角形，每个三角形去掉一条边，就会减少一个三角形。
  • AgeMean 和 AgeVar：这两个变量中，只有 AgeMean 能够维护，通过维护当前所有人的年龄和来维护均值，为什么说方差不能维护？虽然方差可以表示为平方和的均值减去均值的平方，但在JML中，均值和方差的的计算被转化为整数，丢失了一部分精度，此时如果使用动态维护的方法计算，便会产生一定的误差，造成评测错误。
  • BestAcquaintance 和 BestContributor：虽然在数据结构建立方面，这两个变量用 TreeSet 维护有较好的性能，但有部分同学采用了另一种实现方法——动态维护当前的 BestAcquaintance 或 BestContributor，实现 O(1) 复杂度的查询。当增添关系时，只需通过比较动态更新变量，复杂度为 O(1)，当修改或删除关系时，则需要重新遍历计算，复杂度为 O(n)，在各种操作较为均衡的情况下，时间开销与 TreeSet 差别不大，这也是一种可行的设计方案。

    3. 规格与实现分离

    JML规格描述的是“做什么 (What)”，而代码实现关注的是“怎么做 (How)”。这种分离带来了诸多好处：

  • 清晰的契约：JML为方法的调用者和实现者提供了一个清晰、无歧义的契约。调用者只需关心方法的JML规格（前置条件、后置条件、异常等），而无需了解其内部实现细节。实现者则必须确保其代码满足JML的各项规定。
  • 并行开发：一旦JML规格确定，不同的模块可以由不同的人并行开发，只要大家都遵守规格，最终模块就能正确集成。
  • 可维护性：只要方法的JML规格不变，其内部实现可以自由修改或替换（例如性能优化），而不会影响到调用该方法的其他代码。这大大降低了维护成本和风险。
  • 形式化验证：JML的精确性使其能够作为形式化验证的输入，或者作为生成测试用例的精确依据。
  • 设计先行：JML强制我们在编码前先进行详细的设计思考，明确每个组件的职责和交互方式，有助于在早期发现设计缺陷。

然而，规格与实现的分离也意味着，JML本身不保证性能。JML可能描述了一个功能上正确但实现起来非常低效的操作。如果实现者不经思考地直接翻译JML逻辑，就会导致性能问题。因此，实现者在满足JML规格的前提下，还需要运用数据结构和算法知识进行性能优化。性能优化是在“怎么做”的层面，需要超越JML的字面描述，但又不能违反其规定。

五、Junit测试

1. 具体实现

  • 基于JML规格构造：
    • 前置条件 (requires)：针对 requires 子句的布尔表达式，构造使其为真和为假的数据。
    • 后置条件 (ensures)：构造能够触发 ensures 子句中不同逻辑分支的数据。

    • 不変式 (invariant)：在方法执行序列中，尝试构造可能破坏不変式的数据，以检验实现的鲁棒性。

    • 边界构造：
      • 空值/零值：空网络，用户没有任何朋友，Tag中没有任何用户，消息列表为空。
      • 最大值/临界值：关系网络为n阶完全图，Tag中用户达到数量上限，第一次迭代任务中，我因为临界值的$\le$写成了$\lt$，导致边界处理错误，互测被hack到1次。
      • 特殊值：limit 为负数时删除冷表情，用户id为负数。
  • 随机数据生成：在JUnit中，通过随机生成数据，生成大量随机合法的测试数据，随机生成时，不能完全随机，也应考虑构造数据时的逻辑依赖关系，例如先添加足够的用户和关系，再进行查询和修改操作，防止生成完全无效的测试数据。
  • 构造影子方法：对于复杂的查询，可以实现一个逻辑简单但可能效率较低的“标准答案”方法，该方法严格按照JML的逻辑描述实现，不考虑性能优化。而后用随机数据或构造数据同时运行待测方法和影子方法，对比结果以判断正确性。这对于如 queryTripleSum、queryTagValueSum 等涉及全局计算的方法非常有效。
  • 指令序列构造：不仅要测试单个指令，还要测试特定序列的指令，因为某些bug只在特定操作顺序后才会显现。例如，先添加关系，再删除关系，再查询相关的 TagValueSum 很容易出错。

2. 测试优势

  • 自动化测试：JUnit测试可以自动化执行，快速反馈代码修改是否引入了错误，是回归测试的利器。
  • 早期发现问题：在开发过程中同步编写和运行JUnit测试，可以在早期阶段就发现实现上的逻辑错误，降低修复成本。

3. 局限性

  • 完备性：即使有JML，也很难保证测试用例达到100%的完备性，特别是对于复杂的组合逻辑和并发场景。
  • 性能问题：JUnit主要关注功能正确性，对于性能问题（如TLE）的检测能力有限，需要配合压力测试和性能分析工具。
  • 编写成本：对于复杂的JML，编写全面细致的JUnit测试本身也是一项耗时的工作。

六、学习体会

经过第三单元围绕JML的学习和实践，我对面向对象设计与构造有了更深层次的理解，主要体会有以下几点：

  1. 规格的重要性：JML让我深刻体会到形式化规格在软件开发中的价值。它提供了一种无歧义的语言来描述组件的行为和契约，大大减少了因自然语言描述不清而导致的误解和返工。在团队协作中，一份清晰的JML规格是高效沟通和协同开发的基础。
  2. 规格与实现分离：本单元完美诠释了“规格定义做什么，实现决定怎么做”。JML迫使我在编码前仔细构思。这种分离使得我可以更专注于“实现”层面如何高效、正确地达到JML的要求，而不必在实现过程中反复纠结这个方法到底应该干什么。
  3. 面向规格编程：JML是规格式设计的一种体现。通过requires、ensures、invariant等子句，明确了调用者和实现者各自的责任和权利。这有助于构建更健壮、更可靠的系统。当所有组件都遵守规格时，系统的整体行为就更容易控制，减少出bug的可能性。
  4. 测试驱动：JML的存在引导我们从测试的角度思考问题。在阅读或编写JML时，会自然地思考：哪些输入会满足前置条件？哪些会导致异常？方法执行后应该检查哪些状态？同时这也为后续编写JUnit测试打下了坚实的基础。
  5. 数据结构和算法：JML本身不规定实现效率，但很多JML描述的操作如果直接暴力翻译，性能会非常差。这就要求我们在满足JML功能规格的前提下，仔细选择合适的数据结构和算法，以应对可能的性能挑战，规格只是起点，高效的实现同样重要。

总的来说，相比前两个单元，第三单元的学习是相对轻松的。在这一过程中，我不仅理解了JML规格的使用及其重要性，而且对大模型辅助开发有了更深入的理解。虽然JML的严谨性一度让我感到束手束脚，但最终它帮助我构建了逻辑更清晰、正确性更有保障的代码。这种基于形式化规格进行设计、实现和测试的经验，对于未来参与大型、复杂的软件项目是非常宝贵的财富。它让我认识到，高质量的软件不仅仅是“能用”，更是“可验证的正确”和“可维护的清晰”，同时，我对面向对象设计有了更深的理解。