2021面向对象第三单元总结 BUAA_OO

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的时候从后面反向读,一样实现了需求。

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

大体架构

  • 废话少说,上图(没有异常类
    2021面向对象第三单元总结 BUAA_OO

  • 作业的架构大体上就是按照标准的来(甚至名字也听取了课程组的建议),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;
    }
    

复杂度方面

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

测试&BUG

测试

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


下一篇:如何检查java中的当前键盘语言