BUAA_OO_Unit3_JML规格化开发

本单元我们学习了JML规格化语言，并据此实现一个简单的社交网络。我们首先来简单回顾一下三次迭代开发的任务：

• 新建Person、Network、Tag类维护一个简单社交网络，并通过标签来管理存在关系的其他用户。
• 新增OfficialAccount类，实现公众号与文章发布推送功能
• 新增Message类及其子类，实现消息收发机制

架构设计

hw9

UML类图

容器选择

在作业实现中存在许多person和tag容器中的查询操作，为了提升查询效率。我选择了HashMap作为容器，通过键值对查询提高查询效率，时间复杂度为O(1)

变量维护策略

在社交网络中，存在许多query查询操作。如果每次查询都重新计算query所需要的特征值，可能会带来大量的循环操作，增强超时风险。我们可以将所需要的特征值存储起来，数据变化时对特征值进行相应修改，查询时直接返回对应的特征值，降低时间复杂度。

动态维护

• query_tag_age_var :计算tag对应群组的Person的年龄的方差。我在Tag中维护了ageSum和agePowSum两个变量，代表persons的年龄总和与年龄平方和，只需要在addPerson和delPerson中即使更新就好。

  public int getAgeMean() {
      if (persons.isEmpty()) {
          return 0;
      }
      return ageSum / personNum;
  }
    
  public int getAgeVar() {
      if (persons.isEmpty()) {
          return 0;
      }
      int ageMean = getAgeMean();
      // 需要注意/的向下取整效果
      return (agePowSum - 2 * ageMean * ageSum + personNum * ageMean * ageMean) / personNum;
  }

• query_triple_sum:计算返回社交网络中的三元组个数（A-B-C-A）。在NetWork中维护tripSum变量，对应三元组个数只有在addRelation或者modifyRelation中会更新，且只有在关系改变的两人之间会有三元组改变，我们只需要在此处更新维护tripleSum变量即可。

脏位标记与维护

在并查集的维护中，如果删除某个关系，并查集需要重建。如果继续采取简单的动态维护策略，在每次关系删除时都进行并查集重建，且两次并查集查询指令之间间隔很多关系删除指令，那么会带来许多不必要的时间消耗。

针对类似的动态维护代价大的变量，我们设置一个脏位标记。当对相关维护变量有所修改时，脏位置true。在查询操作时间，如果脏位为true，重新计算并维护新值；否则直接返回旧值。

并查集维护如下：

public class Network implements NetworkInterface {
    private UnionFind unionFind;    // 维护封装并查集操作
    private boolean dirtyUnionFind = false;        // 是否删除了某关系，为true时需要重新更新unionFind
    
	public void addRelation(id1, id2, value){
        ...
        if (!dirtyUnionFind) {      // 增加关系时维护代价小，采取动态维护策略
            unionFind.merge(id1, id2);
        }
    }
    
    public void modifyRelation(id1, id2, value){
        ...
        if(newValue < 0){
            ...
            dirtyUnionFind = true;     // 删除了某一对关系，并查集需要重新构建，脏位置1
        }
    }
    
    public boolean isCircle(id1, id2){
        if (dirtyUnionFind) {
            remakeUnionFind();
        }
        return unionFind.isConnected(id1, id2);
    }
}

并查集优化可达性判断

在Network的isCircle(int id1, int id2)方法中，需要判断person1和person2之间的连通性。这当然可以通过dfs递归查询来实现，但不是我们的最优选择。我们采用并查集算法进行可达性判断优化。

并查集是一种树形数据结构，用于处理不相交集合的合并以及查询问题。可以判断两个节点是否属于同一个连通分量

并查集实现原理如下：并查集维护一个父节点数组，其中存储对应节点的父节点ID

• 加入一个新的元素时，初始父节点为该节点本身
• 合并两个集合时间，通过修改父节点数组，其中一个集合的根节点的父节点指向另一个集合的根节点，进而实现两个集合的合并
• 查询两个元素是否联通（属于同一集合）时，判断其根节点是否相同

为了进一步降低并查集的时间复杂度，我做了路径压缩与按秩合并两种优化

并查集实现与以下展示图片均参考了https://hyggge.github.io/2022/06/04/oo/oo-di-san-dan-yuan-zong-jie/

• 路径压缩：应用过程中可能会大量调用find()方法去寻找一个联通分量的代表元，如果不做优化，可能会出现树的深度过高，导致底层元素的代表元查找过程中循环或递归次数过多（如下图a）；我们可以采取路径压缩，在代表元查询过程中，将查询路径上的所有元素的父节点直接设定为代表元（即图b）。

  

• 按秩合并：在合并两个集合时，我们需要对两棵树进行合并。同时为了降低查找路径长度，我们应该使合并后的树的高度京可能低。我们通过将高度低的树指向高度更高的树来实现

  树的高度即为秩，按秩合并即为将“小秩”集合的代表元设置为”大秩”集合的代表元

  

public class UnionFind(){
    private final HashMap<Integer, Integer> parents;    //父节点数组
    private final HashMap<Integer, Integer> rank;	// 集合秩数组
    
    public void addPerson(int id) {
        parents.put(id, id);            // 新加入的personId的父节点是自身
        rank.put(id, 1);                // 深度是1
    }
    
    public int findParent(int id) {        // 不要采用递归实现，容易爆栈
        int root = id;
        while (root != parents.get(root)) {   // 寻找代表元
            root = parents.get(root);
        }

        int currentId = id;
        while (currentId != root) {        // 将查找路径上的元素的父节点均设置为代表元
            int currentParent = parents.get(currentId);
            parents.put(currentId, root);
            currentId = currentParent;
        }
        return root;
    }
    
    public void merge(int id1, int id2) {           // 按秩合并
        int root1 = findParent(id1);
        int root2 = findParent(id2);
        if (root1 != root2) {
            int rank1 = rank.get(root1);
            int rank2 = rank.get(root2);
            if (rank1 < rank2) {
                parents.put(root1, root2);
            } else {
                parents.put(root2, root1);
                if (rank1 == rank2) {
                    rank.put(root1, rank1 + 1);
                }
            }
        }
    }
    
    public boolean isConnected(int id1, int id2){
        return findParent(id1) == findParent(id2);
    }
}

hw10

UML类图

本次主要新增了公众号与文章相关的内容，这一部分难度没有很大，依据JML规格实现就好。此外新增了部分指令。

• query_couple_sum:统计“对偶关系”组的数量，我们采取动态维护策略进行变量维护
• query_shortest_path：最短路径查询，见下节

BFS查询最短路径

看到最短路径查询，我的第一想法是Dijkstra算法，但是由于此次路径中并没有权重。思虑再三之下，我还是采取了BFS广度优先搜索。

其实现原理如下，维护一个LinkedList创建的queue队列(相较于ArrayList在队首对尾操作效率高)

• 设置visited数组标记对应节点是否被访问，以及distance数组记录起始节点到各节点的最短距离
• 将起始节点加入queue队列,标记为已访问，距离为0
• 遍历循环队列直至为空
  • 取出队首元素i
  • 遍历与该元素相联通的节点j
    • 如果该节点被访问过，则继续循环
    • 将该节点标记为已访问，将该元素加入队列尾部，且与起始节点的距离为起始节点与节点i元素的距离加1
    • 如果该节点是目标节点，则查询distance数组并返回相应距离

BFS深度优先搜索以及边的权重相同保证了节点第一次访问时候的距离即为最短距离

public int queryShorestPath(int id1, int id2){		
		Queue<Integer> queue = new LinkedList<>();
        queue.add(id1);
        HashMap<Integer, Integer> distance = new HashMap<>();
        distance.put(id1, 0);
        HashSet<Integer> visited = new HashSet<>();
        visited.add(id1);
        while (!queue.isEmpty()) {
            int headId = queue.poll();
            for (int linkedId : ((Person) getPerson(headId)).getAcquaintance().keySet()) {
                if (!visited.contains(linkedId)) {
                    visited.add(linkedId);
                    queue.add(linkedId);
                    distance.put(linkedId, distance.get(headId) + 1);
                    if (linkedId == id2) {
                        return distance.get(linkedId);
                    }
                }
            }
        }
        return -1;
    }

hw11

UML类图

架构变化

此次作业主要是在原有基础上，依据继承接口机制维护Message类及其子类，实现消息收发模拟。并没有出现算法要求或者新的维护策略，我在此主要介绍一下我的部分层次设计及容器选择

Person中的messages数组

由于messages只实现在队首插入新的消息，并无articles那样的随机删除操作，所以messages选用LinkedList效率由于ArrayList

sendMessage()方法处理

在发送消息时，由于消息种类的多样性，如果在Network中通过许多if-else结构不免显得有些凌乱。

我们可以依据层次结构Message中实现send()方法，并在三个子类中重写，直接在Network中调用即可

// 1. Network
public void sendMessage(int id){
    ...
    getMessage(id).send();
}
// 2. Message 实现基础send()方法
public void send(){
    if(type == 0){...}
    if(type == 1){...}
}
// 3.以ForwardMessage为例，重写send方法
public void send(){
    if(getType() == 0){... && do_article}
    if(getType() == 1){...}
}

bug&&规格与实现相分离

我在第二次作业中，有两个点出现了超时问题，主要是由于Person中的receivedArticles采用了LinkedList,在大量的随机删除消息情况下会超时。改为ArrayList后解决问题

规格实现与分离

规格与实现相分离原则指的是在软件开发过程中，我们需要宏观描述规格-做什么，也需要微观实现实现-如何做，并且将规格与实现显示地分离开来。

规格描述了软件应该做什么，应该对外提供哪些功能，应该实现用户的哪些需求。而实现包括了如何实现这些功能，包括内部数据结构的组织，具体算法选择或者业务逻辑的实现，类或者函数的设计等细节。

在我们面向对象编程中，我们可以把规格设计抽象出来接口，规定了用户的功能接口，并不对其方法实现做要求。而在具体的接口实现类中，则需要兼顾底层细节，选择合适的算法与数据结构实现接口的要求，提供完整的功能

规格与实现相分离可以提高系统的可维护性，增强了可扩展性与复用性，便于测试与验证。同一规格的不同实现可以迅速扩展复用，同时也可依据规格进行测试。

Junit测试

JML辅助Junit测试

JML清晰界定了方法的前置条件、后置条件以及不变式等，我们可以将规格说明或者要求转换为测试样例的验证依据

• 针对前置条件，生成违反条件测试用例，测试待验证方法是否正确抛出异常。对于符合条件用例，是否如期开展了后续正常化测试
• 针对后置条件，既要检验返回值的正确与否，并根据后置条件检验对象状态变化是否符合预期或者发生了其他的不符合期待的变化。特别是对于pure方法，检查是否修改了成员的数据状态
• 不变式检验：检验一些数据的状态或者变化过程是否满足不变式要求

JML的正确表述可以使得测试逻辑更加聚焦于规格，避免因为经验不足导致测试遗漏。

Junit测试检验代码实现与规格的一致性

Junit测试是依据代码规格来展开的，包括前置条件、后置条件以及不变式的检验，与待测试方法的规格是高度一致的。同时Junit测试的是具体的已经实现的方法，即规格的实现，如果待测方法经验证正确，即其符合Junit要求，进而符合了方法规格的要求，这也就体现了代码实现与规格的一致性。

测试过程

测试种类

单元测试

单元测试指对软件中的最小可测试单元(类的方法或者独立逻辑)进行测试与验证。如果类的实现中遵循实现了类的单一职责原则，利用Juint进行单元测试将具有高效性。在代码实现初期对于一些关键方法进行有效的单元测试将确保后续迭代时的高效性与准确性

功能测试

功能测试是黑盒测试的一种，它验证系统是否满足用户需求和功能规格。功能测试不关注内部实现，只关注输入和输出。如果测试中发现问题，并不能帮助我们很快定位出错问题。

在功能性测试中，数据的强度与我们的测试结果息息相关，需要结合白盒测试构造强有力的测试数据

集成测试

集成测试主要为验证多个组件或系统之间的交互是否正常。

在进行集成测试时候我们可以在单元测试基础上，采取增量测试的方式，将单独的经过单元测试的模块不断增加到之前已经测试过的流程中，验证模块间的写通过关系是否良好。

压力测试

压力测试主要评估系统在极端条件下的性能表现，例如高并发场景，数据边界等，通过在大量超过或接近软件要求的范围内进行测试，确保系统的稳定性和可靠性。例如在第二单元中同一时刻发送大量请求，观察系统负载是否均衡。

回归测试

回归测试确保修改代码之后，原有功能是否任能够正常工作。回归测试实际上反映了增量开发过程中的不变性原则。

回归测试并无特定的测试数据或者代码要求，其本质上是一种测试策略，可以利用自动化测试框架等执行已有的单元测试、功能测试等的样例。

数据构造策略

数据构造过程实际上围绕以上测试方法展开的，我们大的可以分为黑箱、白箱测试和压力测试。

对于黑箱测试，我们主要通过数据构造器来随机生成数据进行测试，但是由于指令和数据之间的关联性。如果不采取措施加以限制，测试数据会包含很多无效测试，无法保证数据强度。对此，我们可以通过在数据生成器中维护一些数据结构，person,tag,message等，起到类似常量池的作用。

对于白箱测试，我们可以针对某些具有依赖关系的指令进行构造性测试，例如add_relatton和modify_relation以及queryCoupleSum等，实际上也起到了一个单元测试或者单指令测试的效果。

压力测试，可以通过某些指令多次执行，以验证时间上的效率。例如大量执行query_shortest_path指令，验证最短路径求解是否简洁高效。其他代码中压力测试也包括数据边界测试，但在此次数据溢出可能性较小。

如何引导大模型辅助规格化开发

我在目前开发中，主要是利用大模型进行一些模块辅助开发，其中架构及模块间关系设计依旧主要由我自己完成。

在人为进行架构整体粗略设计后，对于设计好的模块或者函数我们可以借助大模型实现。假设在此次作业第一次迭代中，我们首先设计出了Network-Tag-Person几个模块以及模块间的交互关系，在之后Person等的实现中，我们可以借助AI生成。其中最容易让AI理解我们的想法的是JML规格化，但不得不承认的是JML的完成也极其耗时（虽然JML也可以借助AI生成）。我通常采用的依旧是语言描述，包括

- 背景叙述：假设你是软件开发人员，现在需要进行简单的社交网络开发，包括用户标签管理...等功能
- 模块描述：现在需要你实现person模块，并且支持对其用户进行标签管理等
- 属性叙述：其包括id,age，熟人数组···等属性
- 方法叙述：对于id等提供get方法···实现传入熟人参数等增加熟人方法等
- 实现要求：采用hashMap等高校的数据结构

通常大模型并不可能一两次内完美实现我们的要求，通常需要增加一些后续的修订要求实现渐进式迭代

- 后续要求：采用红黑树实现熟人数组管理，实现value最高&&id最小的朋友的高效查询

此外，我们可以利用AI辅助我们的测试逻辑编写，对于单元测试，我们可以将源代码投喂之后阐述我们的测试逻辑，用以帮助我们撰写测试逻辑

心得体会

JML是一个优秀的规格化语言，可以帮助我们避免一些通用语言表达上的二义性问题，同时可以提高代码的可读性和维护性。但不可避免的是，由于其严谨性也带来其体量的庞大，会对实现者的快速阅读能力有较大考验，例如对于在队首添加新的元素，原有元素顺序保持不变这一条要求可能需要5行左右代码描述。同时，如果每个方法都编写JML，对于架构设计者也是一个不小的工作量

对某些高要求场景或者系统中的关键方法，采用JML规格可以帮我们理清思路辅助高校开发测试，是一个不错的契约式开发工具。

你可以在https://github.com/KingCB0501/BUAA_2025_OO的仓库中获得对应源码，与评测机（部分作业）。