面向对象第三单元总结
Java第三单元总结
本单元总览
本单元主要要求阅读并理解JML规格，在此基础上选择合适的数据结构实现规格所描述的方法和类，从而构建出整个代码模型。
难点在于JML的阅读，数据结构的选择，时间复杂度的优化。
一、总结分析自己实现规格所采取的设计策略
对于规格设计策略，笔者在本单元的学习中并未摸索出来一些特别突出的高效的阅读JML并编写代码的方法，下面仅将简略的介绍在完成作业的过程中尝试使用的方法。
首先对于JML的语法和编写规则应当进行一定程度的熟悉和掌握，其中对方法规格要求较为细致，因为在作业中方法规格出现的频次最多。对方法规格中的前置条件、后置条件、负作用范围限定以及signals子句需要能够快速的阅读。
下面大致来总结自己实现规格时的设计策略，可能设计策略还谈不上，顶多算是自己摸索出来的习惯吧。
在拿到JML规格并能以代码和文件的方式呈现以后，需要对其大致内容进行通读，从宏观上看懂其各个类之间的组织关系，主要是通过对类名的阅读和继承、实现关系的解读，这一阶段是类层次。其次需要深入到方法层次上，进入各个类的源代码，查看其方法名称，依据名称来推测该类可能拥有的属性、行为等，从而在思维中对其有一个大致的定位。接下来便是最熬人的一个步骤，正是对JML规格逐字逐句的阅读，首先是对属性定义的阅读、然后进入到对方法规格的熟悉。注意对JML的阅读一定需要足够的耐心，如果阅读的不仔细将会对方法的理解带来巨大的误差，今后debug时导致不知道是哪一个JML没有正确实现，还要重新阅读，极其耗费精力。
当理解了整个框架后就能明白这样一个JML约束是想起到什么作用，从而就可以选取合适的容器和合适的算法对其进行实现了。
具体的编码过程就不再详细展开，第一第二单元已经对编码有足够的联系，相信这样一个过程不会有太多的难点。
二、结合课程内容，整理基于JML规格来设计测试的方法和策略
本次笔者用到的基于JML规格来进行测试的方法有之下几种：
- 借助IDEA配置的Junit来对JML规格方法进行测试
- 编写数据生成器与同学对拍测试
- 细扣JML并自行构造测试样例
借助IDEA配置的Junit来对JML规格方法进行测试
首先在IDEA中配置Junit工具链，配置好之后对想要测试的类生成测试文件，以MyNetwork.java类为例，生成好的测试文件如下所示
package com.oocourse.spec3.myclass;
import org.junit.Test;
import org.junit.Before;
import org.junit.After;
/**
* MyNetwork Tester.
*
* @author
* @since 5 27, 2021
* @version 1.0
*/
public class MyNetworkTest {
@Before
public void before() throws Exception {
}
@After
public void after() throws Exception {
}
/**
*
* Method: contains(int id)
*
*/
@Test
public void testContains() throws Exception {
//TODO: Test goes here...
}
// etc... the rest of file is not listed here
找到自己想要测试的文件进行编写并运行，下面将通过填充测试文件方法来进行对单元模块进行测试。
package com.oocourse.spec3.myclass;
import org.junit.Test;
import org.junit.Before;
import org.junit.After;
import static org.junit.Assert.assertEquals;
/**
* MyNetwork Tester.
*
* @author
* @since 5 27, 2021
* @version 1.0
*/
public class MyNetworkTest {
private static MyNetwork myNetwork = new MyNetwork();
@Before
public void before() throws Exception {
System.out.println("Test Begin");
}
@After
public void after() throws Exception {
System.out.println("Test End");
}
/**
*
* Method: contains(int id)
*
*/
@Test
public void testContains() throws Exception {
//TODO: Test goes here...
myNetwork.addPerson(new MyPerson(0, "jack", 19));
myNetwork.addPerson(new MyPerson(1, "john", 18));
myNetwork.addPerson(new MyPerson(2, "pick", 20));
myNetwork.addPerson(new MyPerson(3, "bob", 35));
assertEquals(true, myNetwork.contains(0));
assertEquals(true, myNetwork.contains(3));
assertEquals(false, myNetwork.contains(10));
assertEquals(false, myNetwork.contains(9999999));
}
上述代码以测试MyNetwork中的testContains为例编写了对应的测试函数，运行对应的测试函数得到如下的结果表示测试样例通过：
当然也可以编写各个测试函数后在main主函数入口进行统一测试，统一得出测试结果都是可行的。
写数据生成器与同学对拍测试
通过对上述测试方法的分析，发现利用Junit进行测试虽然显得比较“高级”也确实只是显得比较“高级”，其实就使用体验来讲并非很好，因为你不仅要考虑构造出测试样例，还将花费大量时间在编写测试函数上，而大部分工作却都是重复性的。
下面将介绍一个高效一点的方法，就是编写数据生成器并和同学对拍。
数据生成脚本可以利用python来进行编写，大致生成和测试的流程如下
# -*- coding: utf-8 -*-
"""
Created on Sat May 22 09:48:30 2021
@author: 16922
"""
import random
import os
NumOfPeople = 9
NumOfRelations = 29
NumOfMessages = 20
def addPerson(fw):
for i in range(1, NumOfPeople):
'''
add a person randomly
'''
def addRelation(fw):
for i in range(1, NumOfRelations):
'''
add a relation randomly
'''
def addMessage(fw):
for i in range(1, NumOfMessages):
'''
add a message randomly
'''
def addSendMessage(fw):
for i in range(1, NumOfMessages):
'''
send a message randomly
'''
def checkResult(fr1, fr2):
i = 0
while True:
str1 = fr1.readline()
str2 = fr2.readline()
if (not str1) or (not str2):
break
if (str1 != str2):
print("Not well ! At line:", i)
return False
i = i + 1
return True
# Generate testing point file
fw = open("testInput.txt", "w");
addPerson(fw)
addRelation(fw)
addMessage(fw)
addSendMessage(fw)
fw.close()
# run the different jar file
run1 = "java -jar HW_11WithAddRe.jar re_1.txt"
run2 = "java -jar HW_11NoAddRe.jar re_2.txt"
os.system(run1)
os.system(run2)
# test different result whether they are equal
fr1 = open("re_1.txt", "r")
fr2 = open("re_2.txt", "r")
if checkResult(fr1, fr2):
print("Very NICE !!!")
fr1.close()
fr2.close()
其中具体的生成流程被注释掉了（为了避免漏题的嫌疑），需要说明的是，编写数据生成器不一定必须要生成覆盖全部方法的测试样例，可以针对实现困难，可能出现bug多的方法生成特定的测试样例，上述生成方法便是如是，主要针对sendIndirectMessage方法生成特定的测试样例来测试Dijkstra算法的正确性和方法的时间复杂度。当遇到结果不同的测试点时终止自动测试并查看结果进行debug。
细扣JML并自行构造测试样例
对于JML还可能有很多容易出错的地方，对JML仔细阅读找到潜在的出错点或者是普遍的容易被同学们忽略的问题进行样例的自行构造也不失为一种好的办法。
笔者在测试的初级阶段就是采用的这样的方法进行数据构造和测试的，对程序的正确性和功能性验证有很大的帮助。
三、结分析容器选择和使用的经验
想要选好合适的容器，必不可少的一个环节就是去了解各个容器类的底层实现方法是什么以及其API，能够对其已有的方法实现有足够细致的掌握。
容器类的大致分类如下图所示
用语言来表述一下便主要是三种结构：1、数组结构 2、链表结构 3、哈希表结构 下面我们来看看各自的数据结构的特点：
- 数组结构： 存储区间连续、内存占用严重、空间复杂度大（
ArrayList）
优点：随机读取和修改效率高，原因是数组是连续的（随机访问性强，查找速度快）
缺点：插入和删除数据效率低，因插入数据，这个位置后面的数据在内存中都要往后移动，且大小固定不易动态扩展。
ArrayList底层是基于数组来实现容量大小动态变化的。 扩容机制为首先扩容为原始容量的 1.5 倍。如果1.5倍太小的话，则将我们所需的容量大小赋值给 newCapacity，如果1.5倍太大或者我们需要的容量太大，那就直接拿 newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE 来扩容。 扩容之后是通过数组的拷贝来确保元素的准确性的，所以尽可能减少扩容操作。 ArrayList 的最大存储能力：Integer.MAX_VALUE。 size 为集合中存储的元素的个数。elementData.length 为数组长度，表示最多可以存储多少个元素。 如果需要边遍历边 remove ，必须使用 iterator。且 remove 之前必须先 next，next 之后只能用一次 remove。
- 链表结构：存储区间离散、占用内存宽松、空间复杂度小（
LinkedList）
优点：插入删除速度快，内存利用率高，没有固定大小，扩展灵活
缺点：不能随机查找，每次都是从第一个开始遍历（查询效率低）
LinkedList类的底层实现的数据结构是一个双端的链表。LinkedList类中有一个内部私有类Node，这个类就代表双端链表的节点Node。这个类有三个属性，分别是前驱节点，本节点的值，后继节点。
- 哈希表结构（
HashMap, HashSet）
结合数组结构和链表结构的优点，从而实现了查询和修改效率高，插入和删除效率也高的一种数据结构。
在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
结合上述分析，不难发现查找和添加操作都特别多的时候适合用哈希表结构作为主要的数据管理结构。依据这样的分析，本次作业中的合适的数据结构主要还是哈希表结构。说到这里突然想到基于队列的一种PriorityQueue优先队列（也即堆的实现）可能会在堆优化的Dijkstra算法中用到。
四、针对本单元容易出现的性能问题，总结分析原因，如果自己作业没有出现，分析自己的设计为何可以避免
本单元三次作业中均有可能出现性能问题，主要是在时间复杂度的降低没有处理好。
作者本人在前两次作业中并未出现性能问题，而在第三次作业中由于Dijkstra算法优化没有处理好导致了CPU超时。
对于前两次作业来说，时间性能主要卡在数据结构的选择和计算处理方式的选择，上文已经介绍过了采用基于哈希表结构的数据管理方式能够更好的解决查询操作，而采用每次添加数据（人员、关系）时即时记录关键信息(totalAge, totalAge^2等)有利于在多次处理大规模数据计算时获得优势。
第三次作业时间性能卡在Dijkstra算法的优化，优化点有三：
-
Dijkstra算法需要进行堆优化，可以自行构建数据结构，也可以利用
PriorityQueue来进行优化。此时需要注意何时需要触发PriorityQueue进行重新排序 -
在第二重循环（取到最小的距离点
p再进行遍历时）可以获取到p的认识的点的集合进行遍历这样可以大大缩短遍历的人数。 -
需要新建一个
Pair类管理一个结点，并储存结点的距离，在一重遍历内判断该距离和最短距离，即时跳过二重循环。Pair minPair = collected.poll(); MyPerson minPerson = minPair.getPerson(); int minDist = minPair.getDistance(); if (dist.get(minPerson) < minDist) { continue; }
五、梳理自己的作业架构设计，特别是图模型构建与维护策略
-
容器结构的选择
主要是选择了基于哈希表的数据结构，方便快速进行查询操作
-
算法构建
-
并查集的思想
第一次作业中，针对
isCircle方法，为了降低复杂度，选择并查集。在MyNetwork类中，实现HashMap存储每个用户和其祖先的id。在addPerson方法中，新增id对应的键值对，将father_id设为自己。在addRelation方法中，合并两个人的father_id。另实现find方法，路径压缩+返回祖先。在isCircle方法中，对两个id分别find出祖先，以判断二人是否连通。 -
图模型
作业中的图模型比较抽象，作者并未采用像面向过程语言里那种二维数组或是链表的方法来构建图模型，而是采用了简洁的利用哈希表来表示图的方法，哈希表的Key值代表一个节点，而Value代表于其相关的一个节点（或者在不同类中有不同的表现形式）总之这样可以将一个个结点串起来。
维护图模型时只需要关注几个比较关键的方法，添加人、添加到组、从组移除、添加关系，这样几个操作与图的形态关系较为密切，需要即时对相应的数据结构进行更新。
-
作业感想
其实在进行作业之前，也看过很多往年学长关于这一单元的博客，也有同学认为JML这个东西太死板现在也很少遇到。自己经历了这一单元后感觉还好，JML确实不如语言描述通俗易懂，但毕竟本单元需要锻炼的就是这样的一种阅读能力，基础打扎实了以后同时结合文字描述、代码描述、JML描述等等都可以轻松的阅读，这可能是课程组培养的目的吧，所以还是觉得所学的东西必有益处所在，开卷有益嘛。另外想提到的是Junit测试似乎确实不是那么理想或者说好用，有功夫把Junit搞出来，可能其他同学已经搞出自动测评机或者对拍结束了哈哈。
总之，每一单元都能学到不少东西，这也是难能可贵的。