面向对象第三单元总结

一、实现规格所采取的设计策略

1.浏览public instance model non_null
通过浏览这这些instance，对整个类的属性进行了一定的了解，心里对需要对那些数据进行存储有个大概了解，知晓整个类是对哪些属性进行操作。

2.阅读函数内容
阅读每个函数的JML代码，通过其前置条件、后置条件和副作用范围限定来明确其代码的作用。事实上，在理解代码的时候需要对JML的语言进行简化，比如说dfg，事实上就是从group中删除一个人，由于JML需要保持的严谨性，就会写非常长的一串。这些需要自己去理解并简化代码，同时不能忽略细节。

3.通过整个类来选择容器
在阅读了所有函数之后，就需要选择合适的容器来配合整个类。以第一次作业的People为例，这个类需要容器来装载每个人的熟人以及对应熟人的value值。最开始的时候，我选择和JML最为接近的表述，使用两个ArrayList来分别装人，并且二者位置一一对应。但其实这两者可以合并成一个HashMap，并且HashMap的便利寻找操作比ArrayList更快，更节省时间。

4.对应方法进行算法选择
这一单元是完成社交模拟系统，事实上可以抽象为对图的操作，加点、加边、加权值。对其中的一些操作，需要选择合适的算法。例如是否联通的判断、联通块的总数判断、最短加权路径的判断等等。在算法的选择上最主要的考虑还是时间复杂度，空间复杂度基本上是不会超的，因此选择一个高效的算法很重要。

二、基于JML的测试方法和策略

本次的测试主要分成两种，一个是正确性测试，一个是性能测试。

正如指导书中所说，只要完全按照规格写出函数，按理来说是不会出现错误的。对于正确性测试，我也并没有做到全覆盖。一些简单的查找函数比如contains等等，我是直接进行了形式化验证，对照着函数和代码进行检查。对于一些略微复杂的函数，比如qci、qbs、sim这种对于进行整个图的遍历，我采用了构造数据法。首先自己构造一个图，使用ap和ar完成图的构造，在使用这些函数来比较正确值。这仅仅是对它们的正确性验证。

对于性能测试，主要就是对那些进行图遍历操作的函数的时间测试，就比如上文提到的qci、qbs和sim等。使用代码，构造2000个顶点的图，之后反复调用上述函数，观察运行时间。这里的运行时间可以通过python来得到。其实上，通过自己的代码的时间复杂度，大概就能知道自己是否会超时。比如第三次作业可以支持10000条指令，那么使用0n^2的算法在6s内是可以完成的。

对于指导书提到的JUnit，确实是一种不错的测试方法，它可以对单个函数进行全方位的测试。我使用其测试了一些函数，但是对于需要多个函数配合的函数就没有采用它。整个单元，我个人使用形式化验证的检测方式较多，这确实能保证正确性，但JML代码冗长，实在不好比对，效率比较低。

三、分析容器的选择和使用的经验

本个单元，最优的容器一定是图，所以我采用HashMap为主，ArrayList为辅的选择策略。事实上，其实就是全为HashMap，ArrayList也只是维护图的工具罢了。

1.图在查找的优势
本单元有不少查找的函数。这种情况下，图绝对是速度最快的选择。通过索引进行随机访问，无疑比数组或者ArrayList每次从头遍历效率高太多太多。基本上，如果采用HashMap来进行查找，极大地减少了时间复杂度，不会在查找这一地方出现超时问题。同理，事实上如果需要类似数组一样的存储，HashSet也是个不错的选择，原理一样，它的查找效率也比数组高太多了，但本单元我没有运用HashSet的场景。

2.ArrayList的运用场景
在一些容器所需容量小，并且需要顺序排列的地方，我采用了ArrayList。毕竟，如果需要按序排列的话，只能采用类似数组的实现方式了。比如在Person类中的getReceivedMessages函数，它只需要这个person收到的最多前4个message，这样的话，由于存在进队顺序，并且其实容量也不大，ArrayList就能很好地完成任务。

3.图和ArrayList公用的场景
事实上这个场景主要是在sim这个函数中，ArrayList是用于维护图的遍历的。在最短路径的寻找中，用于辅助存遍历节点。这个算法的具体操作下文会提到。

四、性能问题总结和与设计分析

性能问题主要就是与遍历挂钩。三次作业中一些小的遍历，例如寻找people里是否存在相应id，groups里是否存在相应的group，messages里是否存在相应的group之类的，这些遍历虽然简单，但是如果在一个函数中反复调用，也会带来性能的损失。接下来以三次作业为例，分析里面容易出现的性能问题。

第一单元对性能要求较高的便是qci和qbs这两个函数。前者判断两个人是否联通，后者输出整个系统的联通块数目。最开始的时候，我是采用的dfs算法来判断两人是否联通。因此，每一次调用qci，就需要对整个二者的熟人进行一次遍历，若没找到，还要继续遍历，复杂度是很高的。况且，我又按照JML中的代码，在qbs中调用isCircle函数，而且每两两之间都要调用一次isCircle，这样的时间复杂度真的高的离谱。当然，强测一些没过是因为我dfs算法没有提前退出导致的超时以及一些小问题。在bug修复环节，我采取了并查集的方式，将时间复杂度一部分转移到ap和ar中，并且采取的是HashMap存的连接点，效率高。系统的总联通块数在每一次ap和ar中都能算好，调用qbs时实际上是一个O(1)算法，时间复杂度大大降低。

第二单元对性能要求比较高的是qgvs这个函数。按照经典做法，每一次qgvs时都需要遍历组中的所有人并且算出总的value，实质上是不可取的。吸取了上一次作业的教训，我将groupValue单独列为Group类的一个属性，每当atg，ar和dfg时，就对组进行遍历，相应地改变组的groupValue值。这种情况下，复杂度最高的也就是ar。它首先需要遍历所有的组，判断person是否在该组中。如果在该组中，再对该组中的人进行遍历，相应地改变groupValue。而这最坏的情况，也只有O(n^2)的复杂度，完全可以满足题目要求。可惜的是，由于我在平均年龄和方差等时候，完全按照JML中来写，没有考虑组中人数为0的情况，导致强测全挂。

第三单元性能要求比较高的是sim这个函数。这个函数本质上是要求找到两个顶点的最短加权路径。这里我新建了两个容器，一个HashMap和一个ArraryList。具体算法如下：

HashMap<Person, Integer> minPath = new HashMap<>();
ArrayList<Person> path = new ArrayList<>();
Person person1 = message.getPerson1();
            minPath.put(person1, 0);
            path.add(person1);
            Person person2 = message.getPerson2();
            for (int i = 0; i < path.size(); i++) {
                putAc(path.get(i), path, minPath);
            }

minPath的key为Person，value为Integer，存的是person1到联通块中每个人的最短权值。path是用来遍历的person。初始时，将perosn1的最短权值设为1，并且加入遍历列表path。之后就开始循环调用putAc这个函数。

putAc这个函数的主要功能如下：它对传入的person的熟人进行遍历。如果在minPath中不存在该熟人，就往里面加入person与该熟人的value，并且在遍历列表path中加入该熟人；如果在存在，就计算新的value值，并与原value值进行比较，如果新value值更小，就更新minPath，并且将该熟人加入path中。

因此，这种算法的时间复杂度为O(n^2)，足以满足题目要求。

五、架构设计

总体而言，架构设计与JML大体相同。

1.MyPerson

    private int id;
    private String name;
    private int age;
    private HashMap<Person, Integer> acAndValue = new HashMap<>();
    private int socialValue;
    private int money;
    private ArrayList<Message> messages = new ArrayList<>();

采用HashMap来存此人的熟人以及对应的value值，采用ArrayList存放改任收到的message。

2.MyGroup

    private int id;
    private HashMap<Person, Integer> people = new HashMap<>();//person + age
    private int groupValue = 0;
    private int ageMean = 0;
    private int ageVar = 0;

采取了HashMap来存group中的人，每个person与它的age一一对应。

3.Counter

    private int pinf = 0;
    private int epi = 0;
    private int rnf = 0;
    private int er = 0;
    private int ginf = 0;
    private int egi = 0;
    private int emi = 0;
    private int minf = 0;
    private int einf = 0;
    private int eei = 0;

    private HashMap<Integer, Integer> personPinf = new HashMap<>();
    private HashMap<Integer, Integer> personEpi = new HashMap<>();
    private HashMap<Integer, Integer> personRnf = new HashMap<>();
    private HashMap<Integer, Integer> personEr = new HashMap<>();
    private HashMap<Integer, Integer> groupGinf = new HashMap<>();
    private HashMap<Integer, Integer> groupEgi = new HashMap<>();
    private HashMap<Integer, Integer> messageEmi = new HashMap<>();
    private HashMap<Integer, Integer> messageMinf = new HashMap<>();
    private HashMap<Integer, Integer> emojiEinf = new HashMap<>();
    private HashMap<Integer, Integer> emojiEei = new HashMap<>();

这是一个异常计数类，每一个定义的int类型属性都是该类型异常的触发总数，每个HashMap的属性都是对应的每个id触发该异常的次数。在每一个异常类中调用该静态类，即可实现正确的异常计数。

4.MyNetwork

    private HashMap<Integer, Person> people = new HashMap<>();
    private HashMap<Person, Person> link = new HashMap<>();
    private HashMap<Integer, Group> groups = new HashMap<>();
    private HashMap<Integer, Message> messages = new HashMap<>();
    private HashMap<Integer, Integer> emojiIdAndHeat = new HashMap<>();
    private int block = 0;

people对应的是id与该person，link是用于并查集的调用，对应的是person与此人的直接根节点，groups对应的是id与该group，messages对应的是id与该message，emojiIdAndHeat对应的是emojiId和其对应的emoji的热度。

面向对象第三单元总结

原文：https://www.cnblogs.com/xgl010607/p/14829182.html