OO第三单元总结

骑猪看日落 2021-09-30 12:46 330阅读 0赞

# 第三单元作业总结 #

## JML语言的理论基础 ##

JML是用于对Java程序进行规格化设计的一种表示语言，是一种行为接口规格语言(Behavior Interface Specification Language，BISL),基于Larch方法构建。BISL提供了对方法和类型的规格定义手段。所谓接口即一个方法或类型外部可见的内容。JML主要由Leavens教授在Larch上的工作，并融入了BetrandMeyer， John Guttag等人关于Design by Contract的研究成果。近年来，JML持续受到关注，为严格的程序设计提供了一套行之有效的方法。通过JML及其支持工具，不仅可以基于规格自动构造测试用例，并整合了SMT Solver等工具以静态方式来检查代码实现对规格的满足情况。一般而言，JML有两种主要的用法：

1) 开展规格化设计。这样交给代码实现人员的将不是可能带有内在模糊性的自然语言描述，而是逻辑严格的规格。

2) 针对已有的代码实现，书写其对应的规格，从而提高代码的可维护性。这在遗留代码的维护方面具有特别重要的意义。

通常情况下设计者在写代码时会在设计类代码结构时比较充分地使用面向对象的思想而淡化面向过程，但是在实现具体类和方法时，通常会恢复到面向过程的编程方式，但是如果有一种像类结构设计一样的能够高屋建瓴的忽略具体实现方式，但是能够较为明晰的体现该类或方法的输入与输出以及过程中应当时钟保持的约束的语言就会改善这种情况。这也就是为什么JML会存在。

## JML工具链 ##

在完成JML的编写之后，我们需要一些工具来验证编写的JML是否正确以及JAVA程序是否满足JML的规格要求。通过开源的JML编译器，我们可以编译出含有JML标记的代码，若程序中有未满足规格地要求的存在，那么JML在运行中断言检查编译器就会抛出一个uncheckedExeption来说明程序违背了哪个规格。

JMLdoc工具可以在生成的HTML格式文档中包含JML规格。还有工具JMLUnitNG可以根据规格实现自动生TestNG测试样例。

根据 **hero6688**同学的博客了解到JML现行的几个开源工具

> SMT在形式化方法、程序语言、软件工程、以及计算机安全、计算机系统等领域得到了广泛应用。SMT Solver工具可以以静态方式来检查代码实现对规格的满足情况。Openjml使用SMT Solver来对检查程序实现是否满足所设计的规格(specification)。目前openjml封装了四个主流的solver。z3由Microsoft开发的，并已在github上开源：[https://github.com/Z3Prover/z3][https_github.com_Z3Prover_z3] 其正式发布版可通过[https://www.microsoft.com/en-us/download/details.aspx?id=52270][https_www.microsoft.com_en-us_download_details.aspx_id_52270]获得。cvc4由Standford开发，可以通过[http://cvc4.cs.stanford.edu/downloads/][http_cvc4.cs.stanford.edu_downloads]下载。

## 使用JUNIT进行测试 ##

通过安装jmluniting工具，测试了Graph接口的，生成TestNG测试结果如下

[TestNG] Running:
      Command line suite
     
    Failed: racEnabled()
    Passed: constructor MyGraph()
    Passed: <<mycode.MyGraph@64cee07>>.addPath(null)
    Passed: <<mycode.MyGraph@27abe2cd>>.containsEdge(-2147483648, -2147483648)
    Passed: <<mycode.MyGraph@6fdb1f78>>.containsEdge(0, -2147483648)
    Passed: <<mycode.MyGraph@51016012>>.containsEdge(2147483647, -2147483648)
    Passed: <<mycode.MyGraph@29444d75>>.containsEdge(-2147483648, 0)
    Passed: <<mycode.MyGraph@2280cdac>>.containsEdge(0, 0)
    Passed: <<mycode.MyGraph@1517365b>>.containsEdge(2147483647, 0)
    Passed: <<mycode.MyGraph@4fccd51b>>.containsEdge(-2147483648, 2147483647)
    Passed: <<mycode.MyGraph@44e81672>>.containsEdge(0, 2147483647)
    Passed: <<mycode.MyGraph@60215eee>>.containsEdge(2147483647, 2147483647)
    Passed: <<mycode.MyGraph@4ca8195f>>.containsNode(-2147483648)
    Passed: <<mycode.MyGraph@65e579dc>>.containsNode(0)
    Passed: <<mycode.MyGraph@b065c63>>.containsNode(2147483647)
    Passed: <<mycode.MyGraph@768debd>>.containsPathId(-2147483648)
    Passed: <<mycode.MyGraph@490d6c15>>.containsPathId(0)
    Passed: <<mycode.MyGraph@7d4793a8>>.containsPathId(2147483647)
    Passed: <<mycode.MyGraph@449b2d27>>.containsPath(null)
    Passed: <<mycode.MyGraph@5479e3f>>.getDistinctNodeCount()
    Failed: <<mycode.MyGraph@4f4a7090>>.getPathById(-2147483648)
    Failed: <<mycode.MyGraph@18ef96>>.getPathById(0)
    Failed: <<mycode.MyGraph@6956de9>>.getPathById(2147483647)
    Failed: <<mycode.MyGraph@769c9116>>.getPathId(null)
    Failed: <<mycode.MyGraph@6aceb1a5>>.getShortestPathLength(-2147483648, -2147483648)
    Failed: <<mycode.MyGraph@2d6d8735>>.getShortestPathLength(0, -2147483648)
    Failed: <<mycode.MyGraph@ba4d54>>.getShortestPathLength(2147483647, -2147483648)
    Failed: <<mycode.MyGraph@12bc6874>>.getShortestPathLength(-2147483648, 0)
    Failed: <<mycode.MyGraph@de0a01f>>.getShortestPathLength(0, 0)
    Failed: <<mycode.MyGraph@4c75cab9>>.getShortestPathLength(2147483647, 0)
    Failed: <<mycode.MyGraph@1ef7fe8e>>.getShortestPathLength(-2147483648, 2147483647)
    Failed: <<mycode.MyGraph@6f79caec>>.getShortestPathLength(0, 2147483647)
    Failed: <<mycode.MyGraph@67117f44>>.getShortestPathLength(2147483647, 2147483647)
    Failed: <<mycode.MyGraph@5d3411d>>.isConnected(-2147483648, -2147483648)
    Failed: <<mycode.MyGraph@2471cca7>>.isConnected(0, -2147483648)
    Failed: <<mycode.MyGraph@5fe5c6f>>.isConnected(2147483647, -2147483648)
    Failed: <<mycode.MyGraph@6979e8cb>>.isConnected(-2147483648, 0)
    Failed: <<mycode.MyGraph@763d9750>>.isConnected(0, 0)
    Failed: <<mycode.MyGraph@5c0369c4>>.isConnected(2147483647, 0)
    Failed: <<mycode.MyGraph@2be94b0f>>.isConnected(-2147483648, 2147483647)
    Failed: <<mycode.MyGraph@d70c109>>.isConnected(0, 2147483647)
    Failed: <<mycode.MyGraph@17ed40e0>>.isConnected(2147483647, 2147483647)
    Failed: <<mycode.MyGraph@50675690>>.removePathById(-2147483648)
    Failed: <<mycode.MyGraph@31b7dea0>>.removePathById(0)
    Failed: <<mycode.MyGraph@3ac42916>>.removePathById(2147483647)
    Failed: <<mycode.MyGraph@47d384ee>>.removePath(null)
    Passed: <<mycode.MyGraph@2d6a9952>>.size()
     
    ===============================================
    Command line suite
    Total tests run: 47, Failures: 27, Skips: 0
    ===============================================

通过测试可以看出，JUNIT主要卡一些边界值来对程序的正确性进行验证

## 作业架构设计以及迭代 ##

### 第九次作业 ###

第九次作业中实现了Path和PathContainer接口。这次作业主要是使用了很多以前没有使用过的容器。在Path中，我使用了ArrayList来存储点序列，同时存储的第一次即计算出不同点的个数，并存储起来以待查询。在PathContainer中则使用了一个HashMap来记录Path与Id的对应关系（导致运行速度上会有问题）

### 第十次作业 ###

第十次作业中实现了Graph接口，多了一些查询最短路径以及连通性的操作，在判断连通性和最短距离时，我使用了floyd算法，但是由于没有使用邻接矩阵，而是将连接的两个点用hashmap存储起来，速度会受到限制。每次图结构变更时都会对floyd的hashmap进行更新，从而保证正确性。

### 第十一次作业 ###

第十一次作业中实现了RailwayStation接口，这次多了自己到自己的权值，放弃了floyd算法改用了拆点的dijskra算法，在最短换乘则将每一条path记做一个点，在读入时，联通的path记录下来，对其使用floyd算法，从而将“最短路径”记录为最小换乘次数。而联通块我则使用了BFS来进行递归查找。

## BUG分析与修复 ##

### 第九次作业 ###

这次作业是JML单元的第一次作业，相对比较简单，只要注意一些在大一C语言中一些问题既可以避免。

### 第十次作业 ###

这次作业是相对上次有些许难度。这次作业中由于初始化floyd时，没有增加自己到自己的hashmap，所以导致所有自己到自己的距离计算都是2，出现了WA。同时，由于采用hashmap记录，可能是在构造时用时较长，导致超时。这方面在修改时，只能将存储结构修改成二维数组的存储方式来提高速度。

### 第十一次作业 ###

这次作业首先是dijskra算法在设计到缓存时，我错误理解了在执行dijskra时初始化已操作过的点的范围。应当是所有点都是未操作过的，但是我错误的将已经计算出最短路径的点直接记为未初始化的点，这个导致正确性错误。另一方面，由于测试数据不足，在测试联通性时，由于使用了更新当前两点的数据，所以有一个ArrayList没有注意是否为空的情况，这个十分不应该。最后就是算法太慢，我是将换乘点的所有拆分出来的点进行遍历，这样速度就会十分缓慢，但是实际上还应该另分出两个总点，一个设置为所有拆分出的换乘点的起始点，另一个记录成所有点的终点，通过这种抽象从而达成加速效果。

## 体会和感悟 ##

首先就是规格问题。规格规定了程序的输入约束以及程序的输出约束，在这种约束下，可以更好的去完成框架设计以及面向对象的思考。

另一方面，就是程序的算法必需要在设计程序之前搞清楚，否则无论是正确性亦或是运行速度都会很受限制。

转载于:https://www.cnblogs.com/17373363Liuzm/p/10900743.html

[https_github.com_Z3Prover_z3]: https://github.com/Z3Prover/z3
[https_www.microsoft.com_en-us_download_details.aspx_id_52270]: https://www.microsoft.com/en-us/download/details.aspx?id=52270
[http_cvc4.cs.stanford.edu_downloads]: http://cvc4.cs.stanford.edu/downloads/