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

• 首先需要先通读一遍官方仓库里给出的JML规格，大致对需要填写的类和方法有一个整体的印象，根据具体方法的实现初步确定需要的容器和实现细节。
• 实现各个类的方法时也应该从功能单一的底层类如处理异常的类和Person这样的简单类入手，最后在填写Network。
• 具体实现方法时应该先处理异常，根据方法的具体作用选择合适的容器以及复杂度较低的算法。

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

• Junit单元测试：对所实现的较为复杂的函数进行单元测试，构造情况时需要对照JML考虑所有情况，但不可否认的是，这个测试方法的本质还是基于自己的思路来进行测试，也就难免会有疏漏的地方。
• 利用管道构造评测机，随机生成数据和同学对拍进行测试，比对结果保证正确性。

容器选择和使用的经验

如果直接照着JML给的数组实现起来确实方便，但是性能显然是不能过关的，下面将简单罗列下在笔者代码中出现过的容器。

• HashMap: Hashmap由于存储着key-value的关系，查找某个值时只需要调用get就能实现，在本单元的作业中被大量使用于类似于根据id查找person的场景（下面是笔者MyNetwork中的所有属性）。

  private final HashMap<Integer, Person> people;
  private final HashMap<Integer, Integer> idToFatherId;
  private final HashMap<Integer, Group> groups;
  private final HashMap<Integer, Message> messages;
  private final HashMap<Integer, Integer> emojiId2Heat;
  

• Hashset: Hashset具有不包含重复元素的属性，在某些场景下颇有妙用，如queryBlockSum笔者就用Hashset存储了每个结点的祖先节点。

• PriorityQueue: 优先队列，作用是能保证每次取出的元素都是队列中权值最小的，在实现dijkstra算法时用到。java是通过二叉小顶堆实现的这个容器，反正我们的dijkstra算法也是需要堆优化的，这个容器就像java给我们量身定做的一样。

性能问题

• isCircle：放在图论里面就是看两点是否连通，直接DFS或者BFS也能实现，但是时间复杂度不能得到保证，笔者的作业中选择了并查集，利用一个Hashmap存储结点和其祖先结点的id，实现了一个找祖先的函数（路径压缩不能忘）。

      private final HashMap<Integer, Integer> idToFatherId;
      
      private int findAncestor(int id) {
          if (idToFatherId.get(id) == id) {
              return id;
          }
          int ancestorId = findAncestor(idToFatherId.get(id));
          idToFatherId.put(id, ancestorId);   // 路径压缩get√
          return ancestorId;
      }
  

• queryBlockSum：查询连通块个数，直接照着JML写是\(O(n^2)\)的复杂度，这里实现使用Hashset存每个结点的祖先结点，Hashset的size就是我们要的连通块个数。

• getAgeMean, getAgeVar, getValueSum：这三个函数分别是求Group中所有人的年龄的平均值、求Group中所有人的年龄的方差、求Group中所有边的边权之和。处理方法都是一样的，简单概括就是预处理，用ageSum、ageSquareSum、valueSum三个变量记录一个Group里年龄和、年龄平方和和边权和，查询时就是\(O(1)\)的复杂度。

• sendIndirectMessage：求两点间的最短路径。采用优先队列实现的dijktra算法（上面有提到）。

架构设计总结

贴一张第三次作业的UML图：

其中DijQueueMember是在dijkstra实现时放在优先队列里统一管理的成员类。其他主要就是按照JML给的规格实现（值得一提的点前面基本上已经讲完了），没有需要特别说明的地方。