OO第三单元单元总结

JML知识梳理
- JML理论基础
- JML应用工具链
部署JMLUnitNG/JMLUnit
按照作业梳理自己的架构设计，并特别分析迭代中对架构的重构
按照作业分析代码实现的bug和修复情况
阐述对规格撰写和理解上的心得体会

JML知识梳理

JML理论基础

关于JML的相关介绍其实课程给出的指导书就已经足够使用了，由于指导书上都有相关知识的梳理，所以这里不花费大量篇幅去书写这部分内容，只是简单提及一些东西。首先是什么是JML，课程进行，其实阅读简单的JML已经没有多大障碍了，但是对于JML的定义这种概念已经忘记的差不多了。JML是用于对Java程序进行规格化设计的一种表示语言，JML是一种行为接口规格语言，基于Larch方法创建。通过使用JML及其相关的支持工具，我们可以基于规格自动构造测试样例，并整合了SMT Solver 等工具以静态方法来检查代买实现对规格的满足情况。目前学习到的JML语言特征只是level0级别，所以只是入门啊(虽然入门就已经能够解决许多问题了)。

JML应用工具链

JML拥有丰富的工具库，可以给用户提供JML规范检查，或者是随机测试数据生成测试。现仅举出课程中所涉及的几个.

1.OpenJml来检查JML的规范性

2.使用SMT Solver检查代码等价性

3.使用JMUnitNG生成数据测试代码

4.JMLAutoTest...

部署JMLUnitNG/JMLUnit

针对Graph接口的实现自动生成测试用例，并结合规格对生成的测试用例和数据进行简要分析。

按照作业梳理自己的架构设计，并特别分析迭代中对架构的重构

第一次作业

第一次的架构其实很清晰了，因为最顶层的架构关系指导书已经指定了，实际上我们实现的是相关方法和细节（都是些比较底层的东西），所以这样主要提一提相关方法和细节的设计实现，顶层架构为将path抽象成一个类，并且在MyPath中实现相关path内的方法，用PathContainer，处理path间的相关操作，并存储所有的path。

path和不同点的存储：采用三HashMap的结构。

private HashMap<Path,Integer> ptoid = new HashMap<>(1024);

private HashMap<Integer,Path> idtop = new HashMap<>(1024);

private HashMap<Integer,Integer> valuepoint = new HashMap<>(102400);

复杂度分析

其中valuepoint中的key是当前路径中所出现的结点id，对应的value是该结点出现的次数。这样对于getDistinctNodeCount()方法，我们只需要输出valuepoint.size()即可。其他查询方法类似。

第二次作业

第二次作业与第一次作业的主要区别在于最短路和连通块上，而其他需求和第一次作业是一样的，所以我的第二次的架构，首先保留了第一次的架构设计（拷贝粘贴到MyGraph，MyPath类消失），在此基础上，在MyGraph类里主要实现了两个操作，一个是维护并查集，一个是用bfs求最短路。由于求最短路的问题，是一个图相关的问题，所以实现了相关的建图函数（邻接表建图）

具体来说，

//新增类 MyGraph , 删除类 MyPath

//新增方法

public int anc(int x)

public void unin(int x, int y)

public void buildufset() // 并查集

public void buildgraph() // 建图

public void buildsp() // 最短路

//bfs求最短路

 public void buildspforone(int x)

    {

        int [] vis = new int [300];

        for (int i = 0;i < 300;i++)

        {

            vis[i] = 0;

        }

        int [] node = new int [90000];

        node[0] = x;

        vis[node[0]] = 1;

        sp[x][x] = 0;

        int l = 0;

        int r = 0;

        while (l <= r)

        {

            int nd = node[l];

            for (int i = 0;i < edges[nd].size();i++)

            {

                int nnd = edges[nd].get(i);

                if (vis[nnd] == 0)

                {

                    vis[nnd] = 1;

                    r++;

                    node[r] = nnd;

                    sp[x][nnd] = sp[x][nd] + 1;

                }

            }

            l++;

        }

    }

//新增数据成员

private int [][]sp = new int[300][300]; // 最短路。

private int [] father = new int[300]; // 并查集

private ArrayList<Integer> [] edges  = new ArrayList[300]; // 存储边

复杂度分析

由于维护了并查集，所以对于连通块的平均查询是O(1)的，显然可以接受。

对于最短路，由于第二次作业并没有票价之内的问题，所以可以使用bfs来解决无权图的最短路问题，复杂度是O(V+E),由于边数最多为4000，所以也是可以接受的。

对于floyd，由于它的复杂度是稳定在O(n^3)的，所以虽然它好写，我还是没有写,但是事实证明也能过。

第三次作业

第三次作业与第二次作业在需求上有几个主要的不同点：不满意度、票价、换乘、连通块个数。仔细分析可以发现

对于不满意度、票价、换乘都可以抽象成有权图的最短路问题。所以实际上第三次作业与第二次作业的最大区别就是

图有权了，至于连通块个数，由于第二次作业已经实现了并查集，所以直接通过n-times(unin)就得到连通块个数了。

前面说到抽象成有权图的最短路问题，是有一个问题的，如果不拆点，图中的结点同时在多条路径中，也就是说图中结点具有多种性质，朴素的建图是解决不了这种问题的。

然后想到了拆点，结果写完拆点复杂度爆炸，因为极端情况下，拆点使得点数扩大了几十倍，而对于边数更是扩大了上千倍，这种情况下使用现有的算法都面临爆炸的风险，所以当时以为凉凉了...

//拆点 + Dij 思路

public int predij(int x,int y,int model,int num,int ans)

    {

        for (int i = 0;i < 130;i++)

        {

            for (int j = 0; j < 50; j++)

            {

                dis[i][j] = 1070000000;

                vis[i][j] = false;

            }

        }

        dis[x][num] = 0;

        int w  = 0;

        Queue<Edge> q = new PriorityQueue<>();

        Edge e0 = new Edge(x,x,w,num);

        {

            q.add(e0);

            for (int j = 0;j < namount;j++)

            {

                Edge ne;

                int nn;

                do {

                    ne =  q.poll();

                    nn = ne.getV2();

                } while (vis[nn][ne.getPid()]);

                vis[nn][ne.getPid()] = true;

                if (nn == y)

                {

                    if (ans >  dis[nn][ne.getPid()])

                    {

                        return  dis[nn][ne.getPid()];

                    }

                    else { return ans; }

                }

                for (int k = 0;k < edge[nn].size();k++)

                {

                    costs++;

                    Node nm = edge[nn].get(k);

                    w = caculw(nn,nm.getId(),ne.getPid(),nm.getPid(),model);

                    if (dis[nm.getId()][nm.getPid()] > dis[nn][ne.getPid()] + w)

                    {

                        dis[nm.getId()][nm.getPid()] = dis[nn][ne.getPid()] + w;

                        Edge e = new Edge(nn,nm.getId(),

                                dis[nm.getId()][nm.getPid()],nm.getPid());

                        q.add(e);

                    }

                }

            }

        }

        return ans;

    }

直到看到了分层图,顿时发现了新世界，通过把path压缩成小图，然后在把各个图进行合并，最终保留下来的图满足，任意两个直接相连的结点一定属于小图，并且该边权值最小。然后通过对每一个path跑一遍最短路，再对合并之后的大图跑一遍最短路就得到了解。

//分层图 + floyd 

//建小图，跑最短路

for (int i = 0;i <= 60;i++)

        {

            if (ridtop.containsKey(i))

            {

                Path p = ridtop.get(i);

                clearpathedge(pathedge);

                nnode.clear();

                for (int j = 0;j < p.size() - 1;j++)

                {

                    int s1 = p.getNode(j);

                    int s2 = p.getNode(j + 1);

                    if (vtoidx.containsKey(s1) == false) {

                        vtoidx.put(s1,++nodecnt);

                        idxtov.put(nodecnt,s1);

                    }

                    if (vtoidx.containsKey(s2) == false) {

                        vtoidx.put(s2,++nodecnt);

                        idxtov.put(nodecnt,s2);

                    }

                    int idx1 = vtoidx.get(s1);

                    int idx2 = vtoidx.get(s2);

                    {

                        pathedge[idx1][idx2] = caculw(idx1,idx2,1,1,model);

                        pathedge[idx2][idx1] = caculw(idx2,idx1,1,1,model);

                        if (!nnode.contains(idx1)) { nnode.add(idx1); }

                        if (!nnode.contains(idx2)) { nnode.add(idx2); }

                    }

                }

                addpathedge(model);

            }

        }

//采用朴素的floyd

 public void floyd(int [][]a,int type)

    {

        for (int k = 0;k < 130;k++)

        {

            if (type == 0 || nnode.contains(k))

            {

                for (int i = 0; i < 130; i++)

                {

                    for (int j = 0; j < 130; j++)

                    {

                        if (a[i][j] > a[i][k] + a[k][j])

                        {

                            a[i][j] = a[i][k] + a[k][j];

                        }

                    }

                }

            }

        }

    }

//最后对大图进行一次然后再跑一次floyd就OK了，^@^

按照作业分析代码实现的bug和修复情况

三次作业中，强测测试和互测测试我都没有丢分（开心..）,这里主要是针对提交测评前曾经遇到的bug。

作业一bug分析

path的hashmap实现

path是自定义的对象，所以需要去手动实现它的hashcode和equals方法，这里主要说一下hashcode一定

要保证能够复现....
判断大小

判断大小要注意直接减会数值溢出。

作业二bug分析

并查集的实现

并查集最好实现路径压缩和按秩合并，否则容易被卡成链造成tle.
bfs的实现

bfs注意标记数组，以及bfs只能跑连通块，不连通的点的最短路无限大
标记数组初始化

由于有重建图操作，以及会跑多次bfs和并查集，所以需要每一次初始化好标记数组的值

作业三bug分析

Dijkstra及Floyd的正确书写

这个算法网上都有，但是由于不熟练，debug弄了很久。
容器内元素是自定义对象时，重写相关方法

第三次作业中由于自定义了Edge对象，所以使用ArrrayList.contains的时候

就需要重写equals方法，要不然会按照地址进行查找。

阐述对规格撰写和理解上的心得体会

写规格的速度贼慢，写完之后感觉有语法错误，语法错误de完了，发现还有bug。但是，规格确实比自然语言表意清晰的多，在编写代码的时候也更明白自己到底要做些什么。

具体的规格撰写我的一点小心得就是，从上到下，先思考顶层功能是什么，约束是什么？然后逐层向下思考相同问题。

巴特西