OO-第三单元总结-2021

2024-03-08 21:44:34

Unit 3：JML/社交网络 单元总结

一 实现规格所采取的设计策略

本单元都是基于JML给出的具体函数规格进行设计。由于JML已经给出，对每个函数的基本功能实现几乎没有难度、也不需要整体架构设计；实现难度主要体现在

  1. 对JML细节把控是否到位
    • 包括：是否能体察各个函数之间的相互作用使代码完全覆盖规格要求 以及 是否能注意到一些边界情况
  2. 代码性能是否较优

在解决策略上，对于难度中的第1点，需要设计较为全面的测试样例（尤其是在中测过弱的情况下）；对于第2点，则需要在编写代码时对自己的实现基于评测数据量限制进行有效的复杂度评估，并结合JProfiler等工具进行实际检测。

二 基于JML规格设计测试的方法和策略

JML给出程序测试的全部信息。由于JML的存在，在本单元测试时能够进行分函数、有针对性的测试，即使用JUnit编写针对重点函数的测试样例。

关于JUnit测试：

  • 优点：自动化测试，使用简单，作业之间可以复用；能够具体、详细地捕捉出错位置和情况。
  • 缺点：样例为自行编写的，由于考虑不全、强度不够导致不能捕捉到较为复杂情况下会出现的错误；不能有效捕捉性能问题。

自动样例构建 与 JProfiler

  • 由于上述JUnit无法覆盖到的问题，进一步根据JML编写数据构建程序以获得较大规模（类似强测）的测试样例
  • 使用JProfiler对大测试样例进行检测，可以定位到有可能导致超时的方法。

三 容器选择和使用经验

在本单元我使用或曾尝试使用过的容器及特性如下：

  • HashMap / HashSet：
    • 复杂度：空间换时间，增删查 $$O(1)$$
    • 本单元绝大部分属性都涉及随机查找，故几乎都是用Hash类容器进行存储。
    • 需要注意的：
      1. 如要判断key是否存在，若存在则获得value，实现时应直接get并检查value是否为null，而不应先做containsKey判断再get，这样相当于查了两遍，浪费时间。
      2. 最好在初始化时依照评测数据量限制初始化容量，以防止容器容量自增长导致的大量空间浪费
  • LinkedList：
    • 双向连接链表，元素之间相对位置固定。
    • 复杂度：在链表首尾增删 $$O(1)$$，随机查找 $$O(n)$$
    • Person类中messages属性使用，因为message有序，且不涉及随即查找。
  • PriorityQueue:
    • 优先队列，元素按（元素类compareTo方法中规定的）大小排序
    • 复杂度：增offer$$O(logn)$$ ,获得最大/最小元素poll $$O(logn)$$, 随机查找 $$O(n)$$
    • 主要在堆优化的Dijkstra中使用。一开始还考虑为了queryNameRank方法单设一个使用优先队列的peopleRank属性，但由于qnr指令使用上限为333，直接遍历不会造成时间上的过大负担，同时单开属性会造成较大空间浪费，故作罢。

四 关于性能问题的具体分析

三次作业中，在实现上我认为比较挑战性的方法/方法组及对应设计思路如下：

  1. isCircle()
    • 相当于求图的连通性。
    • 开始尝试采用dfs（如果正确使用应该能够通过测试），但感觉不保险，故使用并查集。
    • 并查集
      • 实现：单建UnionFind类，在Network类初始化时初始化，在方法addPerson(),addRelation()中进行维护。
      • 复杂度：
        • 加人addPerson：平均复杂度为常数级（设为$$k$$）
        • 查询：$$O(k*p)$$，p为人数
        • 添加关系addRelation：$$O(kr)$$，r为关系数
  2. queryGroup的几个运算方法
    • 如果每次query都遍历所有人的属性进行计算，会导致超时。故需要动态维护需要用于计算的变量并及时更新。
    • Group类中使用类属性存储年龄和ageSum，年龄平方和ageSqrSum以及值和valueSum，并在向group加人、删人以及在Network中添加关系（hw10中测时就忘了，于是强测gg）时及时更新，query时直接调用类属性进行。
      • 年龄方差计算公式：$$ageVar=ageSqrSum/n - ageSum ^2 / {n^2}$$，n为人数
  3. sendIndirectMessage()
    • 需要求图的最短路径。使用Dijkstra可能导致超时
    • 可采用堆优化的Dijkstra -- PriorityQueue

五 架构设计

关于图模型的架构，共分为三级：人Person --> 组Group --> 网络Network，涉及到的核心概念有两类：关系Relation和消息Message。

在人Person级别上

  • Relation的存储和维护

    • Person类中的acquaintance属性 和 value属性：

      private final HashMap<Integer, Person> acquaintance = new HashMap<>(5000); // id - Person
private final HashMap<Integer, Integer> value = new HashMap<>(1000); // id - value
      • 相当于存储邻接矩阵的一行，当已知某两人id，可以直接利用HashMap迅速查找两人是否直接为熟人以及value多少。
      • 但对于查找两人是否连通，若旨在Person级别上做，则需要对某人的熟人集进行遍历，复杂度过高；故在Network级别上使用并查集解决连通性问题。

  • Message的存储和维护

    • Person类中的messages属性：

      private LinkedList<Message> messages = new LinkedList<>();

      红包、通知和emoji三种不同Message通过继承Message类进行具体实现。

在组Group级别上

  • 关于存储：

    • 其中对组的存储主要在Network中的groups属性

      private final HashMap<Integer, Group> groups = new HashMap<>(10); // id - Group

      以及Group类自身：

      public class MyGroup implements Group {
    private int id;
    private HashMap<Integer, Person> people;
    private int ageSum;
    private int ageSqrSum;
    private int valueSum;
}

  • 具体方法实现：

    • 组的创建和查找：由于数据量限制，组的创建和查找直接对上述HashMap操作即可，无需过多考虑。

    • 组内部统计方法：在Group类中利用类属性进行维护（具体见本文第四部分的2）。

    • 组内Relation的维护：

      组中只使用值和，故对关系的记录只维护一个类属性valueSum即可。

      1. 向组里加人时，利用isLinked遍历加的人的熟人属性，如果两人认识则修改valueSum。

      2. Network类中addRelation时需要判断加关系的两人是否在同一组内，若在则需要更新该组的valueSum:

        public void updateRelation(int addRelationValue);

在网络Nerwork级别上

  • Relation的储存和维护

    • 新建并查集类UnionFind，并在Network类中实例化为类属性unionFind:

      private final UnionFind unionFind = new UnionFind();

      public class UnionFind {
    private final HashMap<Integer, Integer> roots; // 记录该节点的根节点信息
    private final HashMap<Integer, Integer> numEachChain; // 记录各个节点(key)所对应的分量大小，即每条链的节点数
    private int chainNum; // 根结点个数
    
    public void add(int id); // 增加节点
    public int find(int id); // 查找某节点的根节点
    public void merge(int p,int q); // 合并两个节点
    public int getChainNum();
      • 每次addRelation时即调用并查集merge方法进行节点合并，在isCircle查询联通性时调用并查集find方法查看两个节点是否具有相同的根节点。
      • 关于具体用法和复杂度分析见本文第四部分的1。

  • Message的存储和维护：

    • Network类中messages：

      private final HashMap<Integer, Message> messages = new HashMap<>(5000);

      在addMessage中增，在sendMessage，sendIndirectMessage中删。

    • *关于emojiMessage的热度Heat:

      Network类中设置类属性emojiMap --><int emojiId, int Heat>对每类emoji的热度进行保存，在storeEmojiMessage中增，在deleteColdEmoji中删，在sendMessage，sendIndirectMessage中修改。

六 感想与总结

JML规格化在一个大型代码工程中是必要的，其利用规范语言对代码功能进行了详尽的描述。在JML使用上，我认为有以下三个难点：

  1. 如何将想象的架构转化为完善的JML表述。本单元作业中未涉及JML的编写，但在实验中走马观花似的尝试已令我感受到很大压力，还需要后续练习熟悉。
  2. 如何没有遗漏地实现JML。大致理解JML语义是不困难的；重点在于如何透彻分析JML察觉到一些JML规定框架以外的属性变动，以及确认自己的代码全覆盖繁复的JML表述。
  3. 如何基于JML编写测试样例。利用JML相关工具链比如Junit可以进行一定程度的自动化测试，但如果要进行全面、大规模的测试以及性能评测，则还需要基于JML编写自动评测机自行构造大型测试样例。
上一篇：OO第三单元总结——JML系列


下一篇：OO第三单元