[BUAA-OO] 2025 第三单元总结博客

一、单元测试过程

1.1 单元测试

  • 单元测试是对软件中最小可测试单元（比如一个方法）进行验证的过程，通常应该在编写代码时进行，目的是确保每个单元都能按预期工作。
  • 单元测试通常是自动化的，可以使用JUnit这类测试框架来编写和运行测试用例。本单元中，我们测试每个方法是否符合JML约束的过程就是单元测试。
  • 优点：
    • 提高代码质量：通过单元测试，在编写代码时就能发现和修复bug，减少后期维护成本。
    • 提高开发效率：单元测试具有针对性，可以帮助我们更快地定位问题，提高开发效率。
  • 缺点：
    • 需要额外的时间和精力来编写测试用例，无法测试各单元之间的交互。

1.2 功能测试

  • 功能测试就是对于项目的功能进行验证，确保功能符合需求规格说明和用户要求。本单元中，我们对社交网络的各种指令和功能进行测试，确保它们符合预期，这就是功能测试。
  • 功能测试对于迭代开发而言是非常重要的，通过对上次迭代的功能进行充分测试，可以避免在下次迭代时爆出上次的bug。
  • 优点：
    • 在迭代开发中，通过保证先前功能的正确性，有利于在一个稳定的架构上进行后续迭代。
  • 缺点：
    • 功能测试难以保证测试的全面性，一些指令功能的协同合作可能会被忽略。

1.3 集成测试

  • 集成测试是将多个单元组装成子系统进行测试，验证它们之间的交互是否符合预期。本单元中我们对于社交网络的各个类内部和类之间方法的调用进行集成测试，确保它们之间的交互符合预期。
  • 集成测试的优点在于可以发现单元测试中无法发现的问题，比如多个单元之间的交互问题。
  • 集成测试的缺点在于无法精准定位问题，可能需要进一步的单元测试来定位错误。

1.4 压力测试

  • 压力测试是对系统进行高负载测试，验证系统在高负载下的性能、可靠性和稳定性。本单元中我们对社交网络复杂度过高的方法多次调用，进行压力测试，确保它们在高负载下仍然能够正常工作。
  • 压力测试的优点在于可以发现系统在高负载下的性能瓶颈，帮助我们优化系统性能。
  • 压力测试的缺点在于针对极端样例的测试和后续优化可能会导致系统的复杂度增加，增加了后续维护的难度。

1.5 回归测试

  • 回归测试是对系统进行修改后，验证系统已经实现的功能是否仍然符合预期。本单元中我们对社交网络进行迭代开发后，需要重新运行之前的测试用例，确保它们仍然符合预期。
  • 回归测试的优点在于可以发现系统在修改后可能出现的新问题，帮助我们保证系统的稳定性。

1.6 数据构造策略

  • 本单元我们实现了一个模拟社交网络，在测试时需要构造强度较高的测试数据。我主要使用了随机数生成器来生成测试数据，确保测试数据的多样性和复杂性。
  • 单纯random的数据生成覆盖率极低，会导致绝大部分输出都是异常，无法起到任何测试作用。（除非你想测试异常处理bug）
  • 我使用以下数据构造策略来提高数据生成强度。
    1. 对于随机测试来说，需要尽可能减少异常指令的出现概率，因此我采取了在数据生成器中维护数据池的方式，在随机时从数据池中随机选择。
    2. 为了保证生成的关系图的连通性，可以首先建立一个较为稠密的图甚至是完全图，然后在此基础上进行随机化以及其他操作，这样可以保证生成的图是连通的，并且具有一定的复杂度。对于tag、account和message的相关指令生成也是类似。
    3. 对于一些实现易出错、复杂度过高的方法，可以有针对性地进行压力测试；其他指令的分布也可在测试过程中有针对性地进行调整。

二、大模型辅助下的复杂任务完成和引导分析

利用大模型来辅助规格化设计与代码实现，需要清晰地描述任务要求，并提供详细的功能流程，确保大模型能够准确生成预期代码。 具体有以下几个方面：

  1. 任务描述与明确需求
  • 对每个任务及其子功能进行详细说明，例如测试代码中的数据生成器，需要告知大模型需要维护的数据、采用的算法和需要输出的指令要求。直接粘贴JML给大模型可能会导致其无法理解或产生歧义。
  1. 分解任务与流程设计
  • 将复杂任务拆分为若干可执行的子模块，如对于数据生成，给出不同函数的具体功能和输出要求。
  • 为每个子模块设计明确的流程或示例框架，可以使用伪代码来展示模块的代码逻辑。
  1. 引导大模型生成一致性代码
  • 在提示中给出准确的指令要求和示例，确保大模型能理解任务的核心要求。
  • 比如对于询问关注者存储公众号文章的数据结构，给出如下要求：有没有数据结构能够根据时间戳进行顺序存储，并且查询与增删的时间复杂度都是O(1)？，大模型便提供了HashMap<id, LinkedNode>的建议。
  1. 交互反馈与代码优化
  • 在大模型生成代码后，人工审核并反馈调整提示，确保生成的代码逻辑清晰且符合设计需求，达到预期效果。
  • 在第11次作业中，由于person中存储的文章id可以重复，导致了HashMap<id, LinkedNode>的实现无法满足要求。我选择在提示中说明：现在由于在receiveMessage()需要将文章加入receivedArticle中，所以其中的文章id可以重复，但在删除时需要保证将所有的相同id的文章都删除。同时还提供了具体案例，大模型便给出了HashMap<id, LinkedList<LinkedNode>>的实现。再要求大模型使用Hasset来存储LinkedNode，以保证删除时的时间复杂度为O(1)，最终得到了HashMap<id, HashSet<LinkedNode>>的数据结构。

通过清晰的任务描述、模块化的流程设计和交互反馈机制，可以有效引导大模型在不同场景下完成复杂任务，实现既有逻辑正确又具有较高扩展性的代码实现。

三、架构分析

项目架构设计

Network

实现了 NetworkInterface 接口，提供了添加用户、添加关系、修改关系、查询关系、发送消息、管理标签、管理公众号、管理文章等一系列操作。Network类是整个社交网络的核心，负责管理其他类和它们之间的交互。存储了所有的 Person 对象、OfficialAccount 对象、待发送的 Message 对象、全局的articles文章ID集合、articleContributors文章贡献者映射和emojiMapEmoji表情及其热度。

  • 图模型管理: 内部持有一个Graph对象，用于表示用户之间的连接关系，主要用于判断用户是否连通（isCircle）以及
  • 标签管理: 内部持有一个TagStorage对象，用于辅助管理用户与标签之间的复杂关系，特别是涉及到标签内用户间关系值总和的计算。
  • 缓存机制:1. shortestPathCache: 缓存用户间的最短路径结果，通过 shortestPathCacheDirty 标记来判断是否需要更新。2. tripleSum: 缓存网络中的三元组数量。
Person

实现了 PersonInterface 接口，代表社交网络中的用户。每个用户有ID、姓名、年龄等基本信息，同时维护着自己的acquaintance好友关系、好友间的情感值value、拥有的标签tags、金钱money、社交活跃度socialValue、收到的消息messages以及收到的文章articleNodeMap。

  • Person 维护了PriorityQueue优先队列的内部类来快速查询最佳好友。
  • Person 内部使用自定义的双向链表ListNode和 HashMap 来提供多种访问方式（头结点、尾结点或是哈希表），从而高效管理收到的文章列表，支持 O(1)O(1) 时间复杂度的查询、添加和删除操作。
Tag

实现了 TagInterface 接口，表示用户可以拥有的标签。每个标签有ID，并记录了拥有该标签的用户列表 persons，缓存了标签内用户的年龄总和ageSumCache、年龄平方和ageVarSumCache以及标签内用户间关系的总和valueSumCache，用于快速计算平均年龄、年龄方差和TagValueSum。

Message

作为消息的基类，定义了消息的基本属性，如ID、社交价值、类型、发送者和接收者（可以是个人或标签）。

  • EmojiMessage: 继承自 Message，表示表情消息，包含表情ID (emojiId)。
  • ForwardMessage: 继承自 Message，表示转发消息（文章），包含文章ID (articleId)。
  • RedEnvelopeMessage: 继承自 Message，表示红包消息，包含红包金额 (money)。
OfficialAccount

代表公众号。有所有者ID、公众号ID、名称，并管理关注者列表 (followers)、发布的文章列表 (articles) 以及每个关注者的贡献度 (contributions)。

  • 使用 PriorityQueue 优先队列来找到最佳贡献者。
辅助类

Graph: 使用并查集 (Disjoint Set Union, DSU) 数据结构来表示用户之间的连通性。

  • parent: 存储每个节点的父节点。
  • rank: 用于按秩合并优化，减少树的高度。
  • adjacentMap: 存储部分人的直接邻接关系，用于在删除关系后重建并查集。
  • dirty: 标记，当发生关系删除操作时，此标记设为 true，表示需要在下次查询调用isCircle前通过 remake() 方法重建。

TagStorage: 主要用于优化 queryTagValueSum 这类涉及到标签内成员之间关系值的计算。

  • personInTag: 存储一个映射，key是用户IDpersonId1，value是一个 HashSet，包含了所有 personId1 作为成员存在于其中的 Tag 对象。当两个用户personId1、personId2之间的关系值发生变化时，可以通过这个结构快速找到所有同时包含这两个用户的标签，并更新这些标签的 valueSumCache。

图模型构建和维护策略

关于用户关系图:

  • 构建:
    • 当通过 Network.addPerson() 添加用户时，用户节点被加入到网络中，并在 Graph 中通过 graph.addPerson() 初始化，添加到并查集。
    • 当通过 Network.addRelation() 添加用户关系时：
      • 在 Person 中，互相将对方添加到自己的 acquaintance 列表并记录 value。
      • 在 Graph 中使用并查集，通过 graph.addRelation() 将这两个用户所在的集合合并，通过路径压缩和按秩合并进行优化，adjacentMap 记录这条边便于后续重建。
  • 维护:
    • 添加关系: 更新 Person 对象的邻接列表和 Graph 对象的并查集及 adjacentMap。
    • 修改关系 Network.modifyRelation():
      • 如果修改后的 value 大于0，则只更新 Person 对象中存储的 value。
      • 如果修改后的 value 小于等于0，则相当于删除关系：从 Person 对象的 acquaintance 和 value 中移除，调用 graph.deleteRelation()从 adjacentMap 中移除这条边，并将 dirty 标记设为 true，shortestPathCacheDirty 也会被设为 true。
    • 查询连通性 (Network.isCircle()):
      • 首先检查 Graph 对象的 dirty 标记。
      • 如果 dirty 为 true，则调用 graph.remake() 方法。remake() 方法会清空当前的并查集结构，然后遍历 adjacentMap 中仍然存在的边，重新执行 addRelation 操作来重建并查集。
      • 使用并查集的 findRoot() 操作判断两个用户是否在同一个连通分量中。
    • 查询最短路径 queryShortestPath():
      • 首先通过 graph.isCircle() 判断两人是否连通，如果不连通则抛出异常。
      • 如果连通，则执行 bfsShortestPath()。
      • bfsShortestPath() 使用广度优先搜索 (BFS) 来计算最短路径，时间复杂度为 O(V+E)O(V + E)，其中 VV 是节点数，EE 是边数。
      • 我设计了一个简单的缓存机制。如果 shortestPathCacheDirty 为 false 且缓存中存在结果，则直接返回。否则，执行 BFS，并将结果存入缓存，同时将 shortestPathCacheDirty 设为 false。当添加/删除关系导致图结构变化时，shortestPathCacheDirty 会被设为 true，使得下次查询时重新计算。

标签-用户图:

  • 构建:
    • 当用户创建标签 Network.addTag() 时，标签与创建者关联。
    • 当用户被添加到某个标签中 Network.addPersonToTag() 时：
      • 在 Tag 的 persons 列表中添加该用户，更新其内部缓存的 ageSumCache、ageVarSumCache 和 valueSumCache。valueSumCache 的更新会遍历新加入用户的好友，看其好友是否也在该标签内，并累加对应的关系值。
      • TagStorage.linkPersonToTag() 会记录 personId1 现在属于这个标签Tag (通过 personId2 的 tagId 找到的标签对象)。
  • 维护:
    • 从标签中删除用户 Network.delPersonFromTag():
      • 从 Tag 对象的 persons 列表中移除用户，相应地更新 Tag 的 ageSumCache、ageVarSumCache 和 valueSumCache，其中 valueSumCache 的更新逻辑与添加时相反。
      • TagStorage 中的记录无需删除，因为此时 Tag 内的 persons 列表已经不包含 Person1，所以无法访问，在更新valueSum时会被忽略。但下次再将该用户添加到标签时，TagStorage 需要检查 personInTag 中的记录，避免重复添加！(hw10 因为这个出bug了)
    • 删除标签 Network.delTag():
      • 从用户的 tags 列表中移除该标签。TagStorage 的相应记录也不会再被访问到，因此无需删除。(不过这让Java无法自动回收内存，属于是偷懒之举)
    • 关系值变化的影响 Network.addRelation() 、 Network.modifyRelation():
    • 当两个用户之间的关系建立或关系值发生变化时，会调用 tagStorage.modifyTagValueSum()。
    • TagStorage 会查找所有同时包含这两个用户的标签（通过 personInTag 查找第一个用户所在的标签集合， tag.modifyValueSum 内部会做判断然后判断这些标签是否也包含第二个用户），并调用这些 Tag 对象的 modifyValueSum() 方法来更新它们的 valueSumCache。

图构建和维护策略分析:

  • 惰性重建并查集: Graph 类中的 dirty 标记和 remake() 方法是一种惰性更新策略。只有在需要查询连通性且图结构发生过删除操作时，才会重建并查集，从而避免了每次删除关系都完全重建的高昂代价。
  • 缓存利用:
    • shortestPathCache 用于缓存最短路径查询结果，减少重复计算。
    • Tag内部的 ageSumCache, ageVarSumCache, valueSumCache 都是为了 O(1)O(1) 查询相关统计值而设计的缓存，在成员变动或相关关系变动时进行增量更新。
    • Person 内部的 articleCache 和 dirtyCache 用于缓存最近的文章列表，使得调用queryReceivedArticle 时可以快速返回结果。
  • 数据一致性:
    • 在添加/删除关系时，同时更新了 Person 内部的好友列表和 Graph 的并查集。
    • 在修改关系值时，如果关系被删除，则会触发并查集的 dirty 状态。
    • TagStorage 辅助类的引入是为了存储所有的Tag对象，从而在关系值变化时有效地更新所有相关 Tag 的 valueSumCache，维护数据一致性。
  • 潜在优化点:
    • Graph.remake() 的开销: 如果删除操作非常频繁，且之后紧跟着大量的 isCircle 查询，remake() 的开销可能会比较大。不过 考虑到通常查询比修改更频繁，采取了缓存策略 。
    • TagStorage 的维护: 如前所述，delPersonFromTag / delTag 后 TagStorage 中的 personInTag 的记录没有清理。如果一个用户从很多标签中被移除或者很多标签被移除，personInTag 中可能会有很多不再需要的 Tag 对象，这在 modifyTagValueSum 遍历时可能会带来轻微的性能损耗（虽然正确性不受影响）。

四、性能问题和规格与实现分离

作业中出现的性能问题及其修复情况

本单元中我并未出现性能问题，主要是因为我在设计时就考虑到了性能问题（在写任何双重循环前都极为慎重，思考复杂度有没有到O(n2)O(n^2)），并且在实现时也进行了充分的考虑和处理，保证整体的时间复杂度在合理范围内。在hw10中出现了上述的bug，主要是因为我在设计时没有考虑到TagStorage中personInTag的记录会导致重复添加的问题，导致在强测和互测中出现问题，只需要在 addPersonToTag 方法中添加一个判断即可。

规格与实现分离的理解

规格与实现分离是软件开发中的一个重要原则，旨在将系统的功能需求（规格）与其具体实现（代码）分开。这样做的好处包括：

  • 更清晰的系统设计: 降低了系统不同子模块之间的耦合，通过规格定义接口和约束条件，使得开发者专注于思考组件的职责和交互方式，而不是实现细节。
  • 更高的灵活性和可维护性: 实现的改变不影响接口的调用者，从而在不影响其他模块的情况下，独立地修改或替换实现而不用担心引起其他模块的错误。
  • 更好的团队协作: 接口作为不同模块或开发者之间的契约，使得不同开发者可以并行开发，减少了沟通成本。
  • 增强的可测试性: 可以针对接口规格进行测试，而不需要依赖具体的实现细节或是受其影响。这样可以更容易地编写单元测试和集成测试，确保系统的正确性。

五、Junit实现

Junit 绝对是本单元中我体验最差但也收获最多的一个部分，要说它对于我完成作业或者debug的帮助，那可以说是zero，但让我对于手动构造测试样例以及随机数据生成这样的自动化测试手段有了更深刻的理解。此外，本单元中测的Junit黑箱测试点让我必须考虑到数据覆盖性和JML的每个约束条件。

利用规格信息设计 JUnit 测试

JML 规格为设计 JUnit 测试提供了极其宝贵的信息来源。一个完备的 JML 规格几乎可以看作是测试代码的 “设计图纸”。测试的过程中需要细致考虑到 JML 中涉及的所有情况以及规格信息。例如 pure，assignable，ensures等等。

JUnit 测试检验代码实现与规格的一致性的效果

测试代码与规格的匹配程度直接影响了测试的有效性。好的测试方法应该能够覆盖到 JML 中的所有约束条件，并且遵照 JML 中的约束条件进行设计，这能够实现代码实现和测试的分离，在实现过程中由于性能等限制，具体实现不一定完全按照 JML 的流程来实现，但测试代码可以完全按照 JML 的约束条件实现，避免了实现和测试之间的耦合以及开发者思维惯性导致的错误。
本单元中，我的 Junit 测试主要问题出在规格理解不够细致，忽略了一些pure的约束，又或者是浅拷贝的问题没有注意，至于数据覆盖本身，由于采取了随机生成的方式，还是比较全面的。

六、学习体会

JML 单元的重点似乎只是在性能优化和Junit测试上，我在实现上几乎把所有能够优化的地方都优化了，从而没有出现性能问题，但又导致实现过于复杂，花费了很多时间，还出现了一处bug。Junit测试根本无法做本地测试，交上去全靠听天由命，甚至有可能因为PersonInterface写成Person导致过不了编译，测试点也都是不公开的，我其实很想看看比较明显的bug究竟是什么样（）