BUAA OO UNIT3

一、实现规格的设计策略

​ 为了实现规格，我通过以下的策略来对规格进行分析、总结，在整体把握之后，再由简入难，最终完整地实现规格。

​ 之所以采用这样的分析模式，是因为Network是几个相对比较独立的类(Person;Message(不同种类的）;Group;各异常类）的综合的产物，其规格的实现需要在这几个相对独立的类的规格的实现的基础上进行，但是这几个相对独立的类的实现又不能只是按照它们自己的规格来，而应该服务于Network的规格的实现。因此，在先阅读各个相对就独立的类的规格之后，在了解他们的方法的规格的基础上，实现Network的规格。在遇到需要调用的那几个相对独立的类的方法的时候，根据实际的需要选择对应的方法，并实现其方法要求的规格。

​ 同时，面对Network中的类，还需要分析其复杂度，当遇到复杂度比较高的方法的时候，就需要考虑其实现的方式的选择，不能只是一味地按照规格来实现，因为规格只是给一种实现的要求，是一种参考，而不一定是最佳的实现方案。关于复杂度较高的方法所选择的策略及具体实现，详见第四部分“性能问题解决策略”。

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

JML专用的测试工具：

• 本单元三次作业围绕的是根据JML规格编程，因此可能需要一系列JML工具来辅助测试，主要有以下三个：
  • OpenJml，检查JML语法和进行规格静态检查，检查规格是否符合规格。
  • JMLUnitNG，自动生成测试样例动态检查程序是否符合规格。
  • JUnit，单元测试。根据规格自行构造测试，检查规格对应的代码是否正确地实现规格。

利用OpenJml进行JML语法检查：

• 在实现规格的过程中，为了使得实现规格的同时保证实现的性能，往往需要定义一些新的方法，这个时候就需要自己也写一些规格。并通过OpenJml来检验书写的jml规格是否符合语法规范。
• 下面写一下我利用OpenJml找到一处官方文档语法错误的过程：
  • 将官方文档中的Person中的规格粘到我自己实现的MyPerson规格中，然后将相应的属性替换为实际用到的属性，之后在powershell中执行以下的命令：

java -jar D:\OO_homework\openjml\openjml.jar -check .\MyPerson.java

• 第一次的执行结果中出现了以下报错信息：

通过阅读相关的规格，我发现最后的对result的表述不规范，(messages.length < 4)?messages.length,4;应当更改为(messages.length < 4)?messages.length:4;

更改之后，再次运行，不再出现以上的报错信息，则语法合乎规范。

结合JMLUnitNG生成测试样例检查：

• JMLUnitNG工具可以自动生成测试样例辅助检查。

java -jar D:\OO_homework\OpenJml\jmlunitng.jar .\MyNectwork.java -d .\
javac -cp .;
D:\OO_homework\OpenJml\jmlunitng.jar; .\*.java
java -jar D:\OO_homework\OpenJml\openjml.jar -rac .\MyNectwork.java
java -cp .;
D:\OO_homework\OpenJml\jmlruntime.jar;D:\OpenJml\jmlunitng.jar; MyNectworkTest.java

• 优点：可以自动生成测试数据，直接进行测试，实现简单。
• 缺点：生成的数据极为有限难以覆盖各个分支，而且多为边界极限数据，不够具有代表性。

使用JUnit进行单元测试

• 可以利用JUnit工具来自行构造测试点，可以做到有针对性地全面覆盖。
• 下面以测试queryValue为例。

在自行构造测试点之后，需要用Assert.assertEquals()来比较实际结果和预期结果是否一致。

如果不一致，则会出现报错信息，从而可以基于数据来debug。

反之，如果一致，则不会出现报错信息：

• 优点：可以较为全面地有针对性地制造测试数据，对每个规格进行全面的测试。
• 缺点：数据的构造基于自己对规格的理解，具有主观性，可能无法找到理解上的bug。而且数据构造较为麻烦，时间成本高，构造大量的数据较为困难。

自动生成数据+对拍器

• 第一次作业较为简单，直接根据所有的规格写出了生成综合测试数据的自动对拍器，成功发现了isCiecle的理解上的bug。
• 第二、三次作业在第一次的基础上，针对性地为新加的方法，尤其是对性能有要求的方法进行了针对性的测试。找到了分母为0的bug。
• 优点：数据较为全面，可以生成大量的数据进行测试，效率较高。
• 缺点：数据的构造有主观性，不一定可以覆盖全部情景。而且bug的发现基于对拍，如果对拍的几个人有相同的错误也难以发现。

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

• 基于性能的容器的选择

​ 由于本单元的设计，不仅需要规格上的正确性，而且需要一定的性能的要求，所以容器在选择的时候，也需要考虑到性能。

​ 比如，在存放不会重复的元素的时候，如EmojiId，就可以用HashSet来作为容器来储存，而不是用Arraylist。在deleteColdEmoji方法中，我的实现需要存储需要删除的EmojiId号，之后还需要反复查找。这个时候，如果用HashSet来存储，那么查找元素是否存在(contains)的时间复杂度为O(1),而Arryalist查找的时间复杂度却为O(n)。因此，在选择不存在重复元素的容器的时候，选择HashSet会比选择Arraylist具有更好的性能。

• 基于具体要求的容器的选择

​ 以Network中的EmojiIdList和EmojiHeatList为例，虽然在Network中的叙述是单独说明了这两个不同的容器，但是，经过仔细阅读会发现，两者其实是一一对应的，即每一个EmojiId对应着其相应的EmojiHeat，因此，在存放这两个元素的时候，可以以HashMap<Integer,Integer>的形式来存储，用EmojiId作为键值，用EmojiHeat作为value，这样不仅便于存储和统一管理，而且和涉及到他们的方法的规格中的实现非常契合。

​ 比如，在sendMessage的时候，如果message是EmojiMessage类型的，那么就需要将对应的EmojiId对应的EmojiHeat的数值加一，这个时候，如果用两个容器的话，就需要从第一个容器中查找到对应的EmojiId的位置，再在第二个容器的对应位置上找到对应的EmojiHeat，然后加一后再放回。不仅效率一般，而且处理的过程比较复杂，也增加了出bug的可能性，同时降低了代码的可读性。但是如果用上面所描述的HashMap容器来存放着两个属性，那么就会使得这个过程变得清晰简洁，达到更好的效果。

• 夯实基础，合理选择

选择合适的容器的基础是对JAVA中常见容器的了解，不仅要了解其封装好的各种方法的功能和使用方式，而且需要了解其实现的具体方式，从而进一步了解各个方法的时间复杂度等更加内部的结构和特征，从而选择最佳的容器来实现规格。

四、性能问题解决策略

• 第一次作业

在第一次作业中，各个方法都比较简单，最复杂的方法无非是查找两个人是否存在关系，即图中的两个节点是否是连通的。为了解决这个问题，我使用了一种经典的数据结构：并查集。并查集的基本思想，是将有关系的结点合并成一个集合，并用一个代表元素来代表整个集合。同时，为了提高这个方法的效率，我还采用了压缩路径的并查集模式来实现两个人之间的连通性的查找。

使用并查集后，这个方法的时间复杂度为：N次合并M查找的时间复杂度为O(M Alpha(N))，这里Alpha是Ackerman函数的某个反函数。这样的复杂度满足了第一次作业对性能的要求，强测和胡侧重没有因为性能而失分。

此外，queryBlockSum（）方法也需要额外的处理，如果直接按照规格中的描述来查找，方法的时间复杂度会很高，但是如果直接将blockSum作为一个属性维护起来，那么会大大降低该方法的时间复杂度到O(1)。维护的方法也很简单，每添加一个人的时候，那么blockSum就增加一。当添加关系的时候，如果两个人本来就是连通的，那么blockSum不变，否则blockSum的值减一。

• 第二次作业

第二次作业中的方法就相较于第一次的方法多出了几个较为复杂的方法。

1、查找平均数和方差

这两个方法都采用相同的方式：维护一个因子，在调用方法的时候利用维护的因子和对应的公式来计算。

平均数需要维护一个ageSum因子，即年龄的总和。在加减人的时候，sumAge需要加减对应的age。在调用方法，需要求出平均年龄的时候，则averageAge = ageSum/size。

方差需要维护一个ageSum2因子，即年龄的平方和。在加减人的时候，需要加减对应的年龄的平方。在调用方法的时候，利用公式：

(ageSum2 - 2*ageSum*averageAge + n*averageAge*averageAge)/n

即可利用维护的因子计算方差。这里还有一点要注意的，就是公式中的后两项不能随意合并，否则会因为取整问题导致结果和规格中的描述有偏差。

2、queryValueSum();

这个方法如果按照规格直接遍历计算的话，时间复杂度也会有点高，所以也是采用维护因子的方法来实现该规格。在group中加人、减人，以及在addRelation的时候，都需要根据规格的要求维护这个因子。其中addRelation的时候，我为每个人维护了一个“朋友圈”，每次维护只需要找到两个人共有的“朋友圈”，然后对它按照规格要求进行维护即可。

• 第三次作业

本次作业的复杂度的难点在于两个方面：

1、deleteColdEmoji(int limit);

需要现在保存EmojiId和EmojiHeat的HashMap中找到需要删除的EmojiId，然后再遍历Messages，找到EmojiId在需要删除的集合里的那些message，并从message中删除掉他们。

本来比较了两种方式，一种是利用遍历存放EmojiId和EmojiHeat的HashMap，并用HashSet来存放需要删除的EmojiId，然后用迭代器遍历Messages并删除需要删除的message。

另一种是为每个EmojiId维护一个朋友圈，在第一次遍历找到对应的EmojiId的时候，直接把它对应的朋友圈中的message从Messages中删除即可。

但是，经过比较，我发现两种方法的时间复杂度相差不多，但是第一种方法可读性高，而且易于理解、实现，不容易出错，故采用第一种方法。

2、最短路径问题

为了解决最短路径的查找问题，我采用了利用堆优化的Dijkstra算法。本算法的基本原理是利用小顶堆的特性来减少朴素的Dijkstra中耗时很大的查找下一个使用的顶点，从而达到减少时间复杂度的效果。

此外，我还在查找起点到所有的其他顶点之间的最短路径+缓存和查找到终点就停止+不缓存之间犹豫不定，不过最终选择了查找起点到所有顶点的最短路径+一次缓存的方式来实现该方法。

在强测和互测中，均未出现TLE的错误。

五、作业设计架构

由于这三次作业是逐级完善、丰富的，因此，仅对第三次作业进行作业设计架构的分析。

• Network中定义的属性如下：

private HashMap<Integer, Person> people = new HashMap<>(5000);
private HashMap<Integer, Integer> relation = new HashMap<>(4000);
private int blockNum = 0;
private HashMap<Integer, Group> groups = new HashMap<>(200);
private HashMap<Integer, Message> messages = new HashMap<>(2000);
private HashMap<Integer, Integer> emojiIdList = new HashMap<>(800);

这里面，people是来存放Network中的人的一个容器。

relation是为了实现isCircle中的并查集而维护的一个存放关系的容器。

blockNum是为了实现块查找方法而维护的一个因子。

groups是存放Network中的组的一个容器。

messages是存放Network中的message的一个容器。

emojiIdList是存放表情包和它的使用热度的一个容器。

• addPerson中的维护：

需要在people容器中添加新的person。

需要在relation中添加自己到自己的关系，维护并查集的实现。

需要维护blockNum，因为增加了一个人，且刚加入的时候他和其他人没有关系，那么互相有联系的块数应该增加，即blockNum++；

• addRelation中的维护

需要在relation中添加两个人所在集合的代表元素之间的关系，维护并查集。

需要在Person中的acquaintance中添加新的熟人。

需要在两个Person的朋友圈中找到交集，为交集中的group各自加上2*value，用来维护valueSum。

关于Person的架构如下图示：

需要根据两人是否连通来维护blockNum，若连通，则不变，否则，减一。

• addGroup中的维护

需要在groups中加上新的group。

• addMessage中的维护

需要在messages中添加上对应的message。

• sendMessage/sendIndirectMessage中的维护

需要messages中删除发送出去的message。

需要根据message的类型，有针对性地维护Person的socialValue属性/Money属性或者是Group的socialValue属性。

若message是EmojiMessage类型，还需要维护HashMap<EmojiId,EmojiHeat>，是EmojiId对应的EmojiHeat加一。

• deleteColdEmoji中的维护

需要删除HashMap<EmojiId,EmojiHeat>中的对应的键值对，同时删除messages中的对应的message。

六、总结

• 细节决定成败

本单元的作业整体较为简单，但是我还是在第三次的作业的时候出现了一个bug。原因是因为我在进行性能优化的时候，将ArrayList改为了HashMap，但是原来的语句是生成了一个新的ArrayList，改完之后的语句直接进行了浅拷贝，导致改变了本来不应改变的属性，从而出现了bug。

更改时觉得只是容器的改变不会出现bug，但是还是因此而出现问题

从这个惨痛的教训中，我懂的了一定要注重细节和一些看似无关紧要的地方，重要的地方是由一个个看似不紧要的语句构成的，只有对待每个细节都认真、正确，才能保证整体的正确性。