由于三次作业为迭代开发的关系,在技术博客撰写的内容上较为相似,因此并不按每次作业单独做一次分析,而是将其综合起来如下。
设计策略
①整体上先通读指导书,理解程序整体结构和设计需求。
②在三次作业中,可以看出Network接口为顶层模块,而Person、Group、Message等接口为其底部模块,且均较为简单,因此首先实现这些底部模块,最后再完成顶部模块。
③阅读JML,根据JML的描述选择合适的容器。完成各模块内部方法的实现。
④对于部分较复杂的方法,在其它接口中加入一些private方法以优化其复杂度。
测试方法和策略
在有完整的JML规格的情况下,可以使用Junit、JMLUnitNG等工具进行较为完备的单元测试。
JUnit
JUnit是java语言的单元测试框架,根据规格自行构造测试,可以检查覆盖率,尽量保证覆盖率高(但高覆盖率也并不能保证没有bug)。
JMLUnitNG
JMLUnitNG可以根据规格自动生成测试用例,主要是针对边界数据的测试。
OpenJML
OpenJML最基本的功能是堆JML注释的完整性进行检查,包括经典的类型检查、变量可见性与可写性等等,但不支持高版本java。
在实际测试中主要采用的还是黑箱测试,通过指导书的样例验证了程序的基本测试性之后,在充分理解JML规格的基础上对方法的各个分支做了针对性的测试,尤其是前置条件和后置条件的满足,边界情况和异常抛出情况的处理等。
容器选择
本单元作业中存在对于某些数据的频繁查找,例如Person的acquaintance和values、Network等,因此采用HashMap,对于没有频繁查找需求的数据则直接采用的ArrayList,此外在深度优先搜索算法中还引入了栈Stack。
性能问题
本单元主要的性能问题来自于isCircle方法和sendIndirectMessage方法;
isCircle方法意在查询两个人是否连通,最开始使用的是深度优先搜索算法,但是可能会被TLE,后改为并查集。
sendIndirectMessage方法需要实现最短路径查找,最开始仍使用的深度优先搜索算法,后在同学的建议下改为堆优化的dijkstra算法。
架构设计
在本单元的架构设计上,整体模块架构已由课程组给出,在图模型的构建上,以Person类的实例作为无向图的节点,Person之间的isLinked即表示边,其中acquaintance存放下一节点,values存放权值,也即边和边的权值,由此构成了整张社交关系模型图。
心得体会
本单元的重点是对JML规格的阅读与实现,虽然实现难度相比之前两个单元要简单,但实现过程中对JML规格的意义与应用有了更深入的了解。作为逻辑严格的规格语言,它对编程人员来说要比指导书这类自然描述语言要友好的多,无疑在工程开发标准的制定中有着重要意义。但JML的理解与撰写难度也成为其一大掣肘,这点在指导书关于JML规格的多次修改中也有体现。另外就是java程序与算法的结合,也算是对图算法的温故而知新了。