OO 第三单元总结
1. JML梳理
根据JML LEVEL 0手册梳理常用条目
1.1 JML 理论基础
- \result表达式 : 表示方法返回值
- \old( expr )表达式:表示方法执行之前expr表达式取值,若expr为相关引用,只能判断引用本身是否发生了变化
- \type(type)表达式:返回类型type对应的类型。
- \typeof(expr)表达式:该表达式返回expr对应的准确类型。
- \forall表达式:(\forall int i ; exprA ; exprB) 通俗理解为 ∀i(exprA -> exprB)
- \exists表达式: (\forall int i ; exprA ; exprB) 通俗理解为 ∃i(exprA -> exprB)
- 前置条件(pre-condition) : requires expr
- 后置条件(post-condition) : ensures expr
- 副作用范围限定(side-effects) : assignable、modifiable
- 正常功能 :public normal behavior
- 异常功能 :public exceptional_behavior
- 抛出异常 : signals
- 不变式invariant : 要求在所有可见状态下都必须满足的特性
- 状态变化约束constraint : 对象状态变化是两次满足的一定约束,不变式的子集。
1.2 JML应用工具链
对于含有JML注释的代码,可以使用如Openjml进行JML注释语法检查、静态检查、编译成支持rac的class文件。可以配合junitng自动化生成的测试用例对代码运行时正确性进行测试。
2. JMLUnitNG自动生成测试尝试
2.1首先是讨论区大佬给出样例的复现
哪怕是复现讨论区中测试仍然菜出了许多问题,归结于原因为不是很了解java和javac寻找文件的方式,同时报错信息只有找不到***让人十分头大,最终笔者采用将Demo.java直接放到Openjml文件夹中才得以解决相关问题。
$ tree
.
|-- JMLTest.iml
`-- openjml-0.8.-
|-- LICENSE.rtf
|-- OpenJMLUserGuide.pdf
|-- Solvers-linux
| |-- cvc4-1.6
| |-- z3-4.3.
| |-- z3-4.3.
| `-- z3-4.7.
|-- Solvers-macos
| |-- cvc4-1.6
| |-- z3-4.3.
| |-- z3-4.5.
| |-- z3-4.6.
| `-- z3-4.7.
|-- Solvers-windows
| |-- cvc4-1.6.exe
| |-- z3-4.3..exe
| `-- z3-4.7..exe
|-- VERSION_INFO
|-- epl-v10.html
|-- jml-reference-manual.pdf
|-- jmlruntime.jar
|-- jmlspecs.jar
|-- jmlunitng
|-- jmlunitng.bat
|-- jmlunitng.jar
|-- openjml
|-- openjml-template.properties
|-- openjml.bat
|-- openjml.jar
`-- src
`-- demo
`-- Demo.java
初始文件树
第一步:jmlunitng生成测试代码
jmlunitng src/demo/Demo.java
$ tree
.
|-- LICENSE.rtf
|-- OpenJMLUserGuide.pdf
|-- Solvers-linux
| |-- cvc4-1.6
| |-- z3-4.3.
| |-- z3-4.3.
| `-- z3-4.7.
|-- Solvers-macos
| |-- cvc4-1.6
| |-- z3-4.3.
| |-- z3-4.5.
| |-- z3-4.6.
| `-- z3-4.7.
|-- Solvers-windows
| |-- cvc4-1.6.exe
| |-- z3-4.3..exe
| `-- z3-4.7..exe
|-- VERSION_INFO
|-- epl-v10.html
|-- jml-reference-manual.pdf
|-- jmlruntime.jar
|-- jmlspecs.jar
|-- jmlunitng
|-- jmlunitng.bat
|-- jmlunitng.jar
|-- openjml
|-- openjml-template.properties
|-- openjml.bat
|-- openjml.jar
`-- src
`-- demo
|-- Demo.java
|-- Demo_InstanceStrategy.java
|-- Demo_JML_Data
| |-- ClassStrategy_int.java
| |-- ClassStrategy_java_lang_String.java
| |-- ClassStrategy_java_lang_String1DArray.java
| |-- compare__int_lhs__int_rhs__0__lhs.java
| |-- compare__int_lhs__int_rhs__0__rhs.java
| `-- main__String1DArray_args__10__args.java
|-- Demo_JML_Test.java
|-- PackageStrategy_int.java
|-- PackageStrategy_java_lang_String.java
`-- PackageStrategy_java_lang_String1DArray.java
第一步后文件树
第二步:javac 编译 JMLUnitNG 生成文件
javac -cp jmlunitng.jar -sourcepath src src/demo/**/*.java
$ tree
.
|-- LICENSE.rtf
|-- OpenJMLUserGuide.pdf
|-- Solvers-linux
| |-- cvc4-1.6
| |-- z3-4.3.
| |-- z3-4.3.
| `-- z3-4.7.
|-- Solvers-macos
| |-- cvc4-1.6
| |-- z3-4.3.
| |-- z3-4.5.
| |-- z3-4.6.
| `-- z3-4.7.
|-- Solvers-windows
| |-- cvc4-1.6.exe
| |-- z3-4.3..exe
| `-- z3-4.7..exe
|-- VERSION_INFO
|-- epl-v10.html
|-- jml-reference-manual.pdf
|-- jmlruntime.jar
|-- jmlspecs.jar
|-- jmlunitng
|-- jmlunitng.bat
|-- jmlunitng.jar
|-- openjml
|-- openjml-template.properties
|-- openjml.bat
|-- openjml.jar
`-- src
`-- demo
|-- Demo.java
|-- Demo_InstanceStrategy.java
|-- Demo_JML_Data
| |-- ClassStrategy_int.class
| |-- ClassStrategy_int.java
| |-- ClassStrategy_java_lang_String.class
| |-- ClassStrategy_java_lang_String.java
| |-- ClassStrategy_java_lang_String1DArray.class
| |-- ClassStrategy_java_lang_String1DArray.java
| |-- compare__int_lhs__int_rhs__0__lhs.class
| |-- compare__int_lhs__int_rhs__0__lhs.java
| |-- compare__int_lhs__int_rhs__0__rhs.class
| |-- compare__int_lhs__int_rhs__0__rhs.java
| |-- main__String1DArray_args__10__args.class
| `-- main__String1DArray_args__10__args.java
|-- Demo_JML_Test.java
|-- PackageStrategy_int.class
|-- PackageStrategy_int.java
|-- PackageStrategy_java_lang_String.class
|-- PackageStrategy_java_lang_String.java
|-- PackageStrategy_java_lang_String1DArray.class
`-- PackageStrategy_java_lang_String1DArray.java
第二步文件树
第三步 :Openjml 编译
openjml -rac demo/Demo.java
$ tree
.
|-- LICENSE.rtf
|-- OpenJMLUserGuide.pdf
|-- Solvers-linux
| |-- cvc4-1.6
| |-- z3-4.3.
| |-- z3-4.3.
| `-- z3-4.7.
|-- Solvers-macos
| |-- cvc4-1.6
| |-- z3-4.3.
| |-- z3-4.5.
| |-- z3-4.6.
| `-- z3-4.7.
|-- Solvers-windows
| |-- cvc4-1.6.exe
| |-- z3-4.3..exe
| `-- z3-4.7..exe
|-- VERSION_INFO
|-- epl-v10.html
|-- jml-reference-manual.pdf
|-- jmlruntime.jar
|-- jmlspecs.jar
|-- jmlunitng
|-- jmlunitng.bat
|-- jmlunitng.jar
|-- openjml
|-- openjml-template.properties
|-- openjml.bat
|-- openjml.jar
`-- src
`-- demo
|-- Demo.class
|-- Demo.java
|-- Demo_InstanceStrategy.java
|-- Demo_JML_Data
| |-- ClassStrategy_int.class
| |-- ClassStrategy_int.java
| |-- ClassStrategy_java_lang_String.class
| |-- ClassStrategy_java_lang_String.java
| |-- ClassStrategy_java_lang_String1DArray.class
| |-- ClassStrategy_java_lang_String1DArray.java
| |-- compare__int_lhs__int_rhs__0__lhs.class
| |-- compare__int_lhs__int_rhs__0__lhs.java
| |-- compare__int_lhs__int_rhs__0__rhs.class
| |-- compare__int_lhs__int_rhs__0__rhs.java
| |-- main__String1DArray_args__10__args.class
| `-- main__String1DArray_args__10__args.java
|-- Demo_JML_Test.java
|-- PackageStrategy_int.class
|-- PackageStrategy_int.java
|-- PackageStrategy_java_lang_String.class
|-- PackageStrategy_java_lang_String.java
|-- PackageStrategy_java_lang_String1DArray.class
`-- PackageStrategy_java_lang_String1DArray.java
第三步文件树
第四步 :运行
java -cp jmlunitng.jar demo.Demo_JML_Test
[TestNG] Running:
Command line suite Passed: racEnabled()
Passed: constructor Demo()
Passed: static compare(-, -)
Failed: static compare(, -)
Failed: static compare(, -)
Passed: static compare(-, )
Passed: static compare(, )
Passed: static compare(, )
Failed: static compare(-, )
Passed: static compare(, )
Passed: static compare(, )
Passed: static main(null)
Passed: static main({}) ===============================================
Command line suite
Total tests run: , Failures: , Skips:
===============================================
测试结果
2.2 对Graph 进行测试
对graph测试时由于相关原因没能引入规格,因此只进行了边界测试,结果如下(仅给出Fail Case):
[TestNG] Running:
Command line suite ...... Passed Case ignored. Failed: <<MyGraph@47d384ee>>.getPathById(-)
Failed: <<MyGraph@2d6a9952>>.getPathById()
Failed: <<MyGraph@22a71081>>.getPathById()
Failed: <<MyGraph@3930015a>>.getPathId(null)
Failed: <<MyGraph@629f0666>>.getShortestPathLength(-, -)
Failed: <<MyGraph@1bc6a36e>>.getShortestPathLength(, -)
Failed: <<MyGraph@1ff8b8f>>.getShortestPathLength(, -)
Failed: <<MyGraph@387c703b>>.getShortestPathLength(-, )
Failed: <<MyGraph@224aed64>>.getShortestPathLength(, )
Failed: <<MyGraph@c39f790>>.getShortestPathLength(, )
Failed: <<MyGraph@71e7a66b>>.getShortestPathLength(-, )
Failed: <<MyGraph@2ac1fdc4>>.getShortestPathLength(, )
Failed: <<MyGraph@5f150435>>.getShortestPathLength(, )
Failed: <<MyGraph@1c53fd30>>.isConnected(-, -)
Failed: <<MyGraph@50cbc42f>>.isConnected(, -)
Failed: <<MyGraph@75412c2f>>.isConnected(, -)
Failed: <<MyGraph@282ba1e>>.isConnected(-, )
Failed: <<MyGraph@13b6d03>>.isConnected(, )
Failed: <<MyGraph@f5f2bb7>>.isConnected(, )
Failed: <<MyGraph@73035e27>>.isConnected(-, )
Failed: <<MyGraph@64c64813>>.isConnected(, )
Failed: <<MyGraph@3ecf72fd>>.isConnected(, )
Failed: <<MyGraph@483bf400>>.removePathById(-)
Failed: <<MyGraph@21a06946>>.removePathById()
Failed: <<MyGraph@77f03bb1>>.removePathById()
Failed: <<MyGraph@326de728>>.removePath(null) ===============================================
Command line suite
Total tests run: , Failures: , Skips:
===============================================
Graph边界测试结果
可以看到测试主要数据由0、null、MAX、MIN等边界数据构成。
3.架构设计
3.1 Project 9
搜索利用Hashmap,保存使用ArrayList
3.2 Project 10、11
后两次使用了bfs + 优先级队列求最短路径的思路,加入了缓存计算的概念。记录数据通过键值对<CacheEntry, value>构成,每次算法遍历之前优先审查Cache中是否有相应结果,当然最重大的bug也出现在这里,下面会提到。
4. Bug分析
在第三次作业中,由于缓冲层的加入翻了车。由于这个bug很有意思,在此和大家分享:
从初始结点A bfs,每次从优先级队列中取出队首元素,优先级队列中排列的元素为各种走法,排在队首的为当前队列中长度(或票价、换乘数量、不舒适度)最小的走法之一。被取出的合法走法被认为是当前两点间的最优解(因为如果有更优解的话应该在这之前被取了)。
Cache的工作原理是每当出现最优解时便将最优解存入。Cache的使用方法为如果当前中转点 B 与终点 C 中存在CacheEntry,便将 B 后的搜索全部剪枝,因为我们可以确定的是不可能存在经过当前起点 B 的更优解。
错误 1 :最初的bug比较低级,即当Cache搜索成功后直接返回,但是错误在于Cache查询成功并不代表找到了A点 -> C点的最优解,由于B点不一定在最优解路径上。
错误 2 :当查出错误1后便松懈了,没有意识到更重大的bug :当我们使用Cache进行剪枝后,实际上这之后从队首取出的走法就不是最优解了,因此此处应该在是否继续更新Cache和剪枝之间做出权衡。
5. 心得体会
此次题目与实际生活真实情况相差较远,甚至在关键定义上有悖常理,给代码架构设计与理解上主观上加入许多bug的可能。比如一条Path可以重复经过同一个站点多次,虽然这一要求在第一次作业中已经提出,但是仍然让人感到很困惑。以第三次作业为例,设想一条Pathid为1的Path为 1 2 3 4 5 3 6 3 7, 如果我们将3这一数字抽象为一个地铁站,经过地铁站的不同Pathid抽象为站台的话,考察站点3的1号线站台会意识到乘客可以在此站台不换乘而选择去往2、4、5、6、7五站,这不禁让人感到困惑列车为何可以随乘客意愿选择路线而无需乘客换乘。虽说合理的设计可以解决这些问题,但是我并不认为这种架构是解决实际地铁问题时良好的设计思路。
最新文章
- Firefox访问https出现 ssl_error_weak_server_ephemeral_dh_key错误
- Web - 客户端存储的几种方式
- HDU 5115 Dire Wolf 区间dp
- graph | Max flow
- PostgreSQL与RPM
- 【Android 界面效果37】ViewStub的应用
- 分解XML方法
- 安装aptana(1)
- bootstrap ch2清除浮动
- PHP判断点是否在多边形区域内外
- Android编码学习之Fragment
- 异常分类VS垃圾分类
- [转] Java中的final、static、this、super
- FastDFS分布文件系统Java客户端集成
- C#爬取京东手机数据+PowerBI数据可视化展示
- VS生成后事件对文件的copy以及更换扩展名
- wingIDE设置支持中文注释
- web前端----css选择器样式
- ElasticSearch(十):springboot集成ElasticSearch集群完成数据的增,删,改
- 【linux报错】安装好虚拟机后,挂载光盘报错:mount:you must specify the filesystem type
热门文章
- Servlet编程实例 续3
- 15. Bypass 360主机卫士SQL注入防御(多姿势)
- 高性能服务器设计(Jeff Darcy&#39;s notes on high-performance server design
- Linux下ping加上时间戳
- OpenStack基础知识-tox的详解介绍
- [Java]构造函数内部多态的行为所引起的灾难
- 对 React Context 的理解以及应用
- cf837D(01背包)
- ios json转model的简单现实
- C. Increasing by Modulo