BUAA OO 第三单元总结

• 关键词：JML、规格、图论

前言

• 第三单元总的来说可能是更考验助教们的一章
• 总体来讲难度很平顺，JML，算法，都有训练到。更重要的是让我 真真正正对于复杂度有了一定的认识（当然是以强测挂点，互测挂点体会到的
• 不得不说，JML本身写起来很费劲，但是读着很爽，毕竟具有了代码的基本雏形，并且考虑的已经十分严谨。所需要做的无非是想好如何去实现。这便是规格的优势吧

综述

• 本单元一共包含三个Homework，其难度依次递增，总体完完全全是迭代式开发的需求。通过这次单元作业（加一次很难的课上实验），我完全掌握了理解JML规格的能力，大致具备了书写JML的能力。并且，我也学习、复习了各种各样的数据结构，图算法，性能分析工具，收获较大。
• 在这里要感谢一下助教们的辛苦劳动，毕竟JML写着太难了，还还需要经常修改bug。
• 此次作业的题目分别是：
  • Homework9：完成基本的社交关系网络的基本功能。（大部分可以照搬JML完成，求连通路径函数有O(n^2)性能要求）
  • Homework10：进一步完成社交关系网络。（新增统计函数具有性能要求）
  • Homework11：进一步完善社交关系网络。（最短路径算法的应用，强性能要求）

作业分析

• 由于这一单元作业完全是迭代开发，所以仅分析第三次作业。

设计策略

• 本次作业由于是按照以给的规格实现功能，总体来说很多函数的书写可以按照JML的书写逻辑直接照搬。但是对有些有性能要求的函数来说，其算法需要自己去书写。并且在总体函数输入输出可以保证的情况下，其内部的数据结构实现，逻辑实现完全可以*发挥。

• 比如在Network类里，我的数据结构使用如下：（为了更优的查询性能，全部使用了Hashmap）

  private HashMap<Integer, Person> people = new HashMap<>();
  private ArrayList<HashMap<Integer, Person>> relationMap = new ArrayList<>();
  private HashMap<Integer, Group> groups = new HashMap<>();
  private HashMap<Integer, Message> messages = new HashMap<>();
  private HashMap<Integer, Integer> emoji = new HashMap<>();
  

• 又比如在sendMessage函数中，JML要求的是新的信息应当插到信息容器的前面

  @ensures (\forall int i; 0 <= i && i < \old(getMessage(id).getPerson2().getMessages().length);
  @          \old(getMessage(id)).getPerson2().getMessages()[i+1] == \old(getMessage(id).getPerson2().getMessages()[i]));
  @ ensures \old(getMessage(id)).getPerson2().getMessages()[0].equals(\old(getMessage(id)));
  

  这是因为Person的getReceivedMessage函数中，需要选取最新的几个message，就是说message这个容器需要有序

  但是考虑到性能方面，我实际上是采用了尾插，然后get的时候从后面反向读，一样实现了需求。

• 至于那几个核心的性能要求的函数，将在下面介绍

大体架构

• 废话少说，上图（没有异常类
  

• 作业的架构大体上就是按照标准的来（甚至名字也听取了课程组的建议），Person以Group的方式组织，可以在Network里实现Message的分发，以及增添改查功能。数据结构方面，能使用Hashmap的地方完全使用了Hashmap。下面来分函数具体说一下：

具体说明

HW9

• 首先是query_circle函数，其本质上是求Person之间是否连通，最基础的图的遍历算法。由于听说DFS和BFS都会超时，所以提前避开了这两个做法，采用了空间换时间的策略实现了类并查集操作。
  • 就是根据人们之间的关系来动态维护一个个Block，而每一个Block之间的人们即可连通。具体实现就是当add_person时，在总的Block集中加入一个只包含该人的Block以表明其与所有人不连通，当两个人间add_relation时，边将这两个人的Block合并。
  • 其优点在于实现起来十分简单，而且不容易出错。但缺点也很明显：无法处理删除边以及节点的操作。当然，并查集本身也不具备处理这种操作的能力。但是但我了解到可以采用新增parent来溯源构造Block时，还是眼前一亮的。

HW10

• HW10的问题在于需要计算Group组内的一些统计数据，如query_group_value_sum、query_group_age_mean、query_group_age_var等。求和，求平均值，求方差这类问题很显然是不能一遍遍的反复求的。所以我很常规地在Group类里维护了几个变量，当有add_person或者其他一些改变数值的请求时，动态维护这几个值。

HW11

• HW11唯一的难点在于一个求最短路的函数send_indirect_message。显然普通的Dijkstra是满足不了需求的，所以我上网学习了堆排序改进的Dijkstra算法，并利用java的数据结构PriorityQueue来实现堆。在学习算法时，显然我并没有完全理解其优化本质。我的做法是对于每一个连通Block里的人，包装成Pair，全部加入堆中，更新到达最短路长度，poll点更新，如此反复。算法复杂度依旧很高，仅仅是把Dijkstra的找最小路径的部分简化了，但优化不大，很遗憾的强测挂了一个点。

• PriorityQueue的使用实际上也是一个难点。其必须要在取出元素或者新加入元素的时候才可以排序，并且排序完的队列只可以通过特定方法依次取出，不可以擅自更改其中元素的信息。并且，由于我需要排序的是包含距离信息的Person，所以新建了一个类Pair来存储，并重写了其的compareTo方法，继承了comparable接口

• public int compareTo(Pair o) {
      if (distance > o.getDistance()) {
          return 1;
      } else if (distance < o.getDistance()) {
          return -1;
      }
      return 0;
  }
  

复杂度方面

• 不出所料Dijkstra复杂度爆炸了，这是由于大量的遍历，更新每一点的动态路径，并且有一些无用的循环。仔细思考，让这些数据进一步下降其实很难了。其原因还是开始的算法没有吃透，本质上维护每一个点的最短路径完全可以直接用Hashmap，而PriorityQueue的使用可以更为暴力。
• 其次是sendMessege方法。由于涉及到人人信息，群发信息，以及三种不同种类的信息，还有异常的判定，便出现了三层if嵌套，并且还有遍历蕴含其中。但是由于规格便是如此，所以应该考虑将单一函数进行拆分，以降低单一函数的复杂度。

测试&BUG

测试

• 使用了Junit来进行单元测试。首先Junit实际上就是一个模板化工具，其测试眼力需要手动构造。他所能够提供的是对于每一个函数开展单独的测试，并简洁的按照预设的输入输出来运行。
• 测试样例的构造方面，大概是按照如下几个原则：正常数据，异常测试、错误数据、边界数据。当然构造起来十分麻烦，也并没有发现什么错误。
• 其次就是非常有用的对拍方式。通过与同学的共享测试样例，并且对拍输出结果，运行时间等，可以轻而易举地找到自己的bug所在。我就在第三次作业中这样找到了自己Djikstra的bug，其产生原因是我并不熟悉PriorityQueue的使用，并完成了修复。
• 在测试性能方面，我部署了Jprofiler，用里面的CPU VIEWs来分析程序的性能。我对于第三次作业的Dijkstra进行了分析，其分析结果如下：

• 可以见到函数的cpu时间时间花销大部分都被反复的getPerson、PriorityQueue的添加操作，和判断Person连接关系的查询操作占据了。但是经过我仔细考虑，这些函数是不可避免的，没有变量可以被缓存下来，其占用时间过多完全是因为大量的遍历查询导致的，是属于算法涉及层面的问题。如此一来，我便锁定了性能提高的方法。

BUG

• 出现的BUG有两个，都是性能相关。
• 一个是在第一次作业互测被hack了。原因是完完全全按照JML硬搬了一个query_block_sum。是O(n^3)的复杂度lol。因为当时我以为因为他的JML要求的存储容器是有序的的，所以只能使用Arraylist来完成。但时候当我进一步理解了他的本质含义以后我才恍然大悟，其要求的就是我本来已经维护好的并查集的集合数，是一个O(1)复杂度的查询罢了。这告诉我们一定要不能被JML局限，活读书
• 第二个就是出现在了Dijkstra上。性能不过关，但总体上我还是可以接受的。毕竟算法的实际应用没有练过很多，只是大多数也比较生疏了，这次能实现出来并且虚摸假样的使用了PriorityQueue，总体来说还是有所提高。在之后我与同学交流了他们的算法,总结如下：
  • PriorityQueue的使用并不应该直接把各个人加进去，因为这会直接带来一个问题：查询找人无法通过id直接查找，必须要遍历，会带来极大的性能损失。所以应当把各个人的最短到达距离Pair构造成HashMap，PriorityQueue里存的是新更新后的边，以此可以做到其的只添不减。并且更新距离也可以直接根据Acquaintance的id直接查找判定，加入Queue中，避免不必要的遍历。

感想体会

收获

• 总的来说，本单元实际上是较为抽象的一章。不比以往的两个单元：贴近数学的求导，贴近生活的电梯，本单元的PersonNetwork实际上还是较为抽象。而且由于总体的架构其实是助教已经给完成了，所以对于总体架构这方面参与的不多。另外这一次作业的代码量很少，大致迭代到第三次作业一共也就只有700-800行左右。算法层面呢，没有了性能分，实际上要求也并不高，没有卡的太严格。可以说，这单元的作业大概并不是着眼于对于代码能力的直接锻炼了，而是起到了书写规范化，工程化思维的植入作用。
• JML实际上就是工程化的产物吧。在设计整个工程的时候，我们是否能够在最开始将所有函数功能细分，并想出其相应的JML？在测试的时候，我们又是否能够完全的测试样例覆盖？在找到bug之后，又是否能锁定其究竟是设计的JML的问题，还是实现层面的疏忽？这些思想，实际上就是我在这单元学习的最大收获。任何一个项目，都是可以拆分的。不单单是函数可以解耦，设计、实现、测试，更是可以解耦的。
• 当然，我还复习了之前学过的数据结构，图论算法等。由于可能并不是课程组认为的重点，所以就不多讲了。

不足

• 感觉最大的不足大概是Dijkstra爆点了，对于算法的理解还是浅了一点。在图论算法中，其肯定属于基本中的基本，可以见得，在算法层面我还需要不断的提高。