面向对象第三单元总结

1. 设计策略

先暴力后优化的设计策略

1. 为了让代码尽量符合jml的标准，减小出错的机会。由于jml基本给好了代码，我就先按照jml的写法实现。这一版出错概率较低，也可以当作后期测试的基础。
2. 当第一版写完后，一点一点进行重构，选择复杂度较低的做法来实现。

2. 基于jml规格设计测试的方法和策略

根据jml寻找复杂函数的各种情况进行测试

1. 找到边界情况进行对拍
   1. 最大值（构造超过1111的数据）
   2. 复杂度上限的情况（疯狂query group value sum）
   3. 各种可能抛异常的情况
   4. jml里特判的一些情况（除0）
   5. 一般这些数据构造出来之后都是知道答案的，直接生成答案和代码跑出来的进行对比。
2. 找到不易发现的情况进行对拍
   1. 通过随机超大数据进行对拍，找到一些手动构造可能构造不出来的问题
   2. 这里可以自查有无异常，也可和同学进行对拍
3. 枚举小数据进行对拍
   1. 小数据因为种类过多，随机难以全部覆盖，但是小数据数据量小，可以进行枚举，通过dfs枚举几乎所有情况，一个一个测试，进行对拍。

3. 分析容器选择和使用的经验

能o(1)就o(1)，否则能log就log

1. 对于异常类型，均使用HashMap<Integer, Integer>统计每个id出现异常的个数

2. 对于MyPerson也使用的是

   private HashMap<Integer, Boolean> acquaintanceNew;
   private HashMap<Integer, Integer> valueNew;
   

   来维护一个对于一个人，是否有连接以及连接的权值是多少。

3. 对于MyGroup也使用的是

   private HashMap<Integer, Boolean> peopleNew;
   private HashMap<Integer, MyPerson> people;
   

   来维护group里一个人是否存在以及存在的人对应的MyPerson

4. 为了Network能够高效的实现，同时我定义了一种数据类型，叫做MyNode，是一种二元结构，有

   private int messageid;
   private int heat;
   

   其主要功能是二元排序，排序规则为先按heat排序，再按id排序。

5. 对于MyNetwork 使用的容器较为复杂，原因见代码里的注释部分。

   private HashMap<Integer, Integer> realid;
   private ArrayList<Integer> fa;
   //由于id范围较大，先用realid进行离散化，接着再用并查集
   private ArrayList<Group> groups;
   // 由于group<=5，用arraylist维护常数较小 
   
   private HashMap<Integer, Person> peopleNew;
   private HashMap<Integer, Message> messagesNew;
   //维护network里的人和message
   
   private HashMap<Integer, Integer> dis;
   private HashMap<Integer, Integer> vis;
   //dijikstra算法中使用
   
   private TreeMap<Integer, MyNode> emojis;
   //维护存在的emoji
   private TreeSet<MyNode> heats;
   //维护存在的emoji，并按照heat进行排序，这样后期迭代器就可以按照heat从小到大进行枚举了。
   
   private ArrayList<Integer>[] emojimessages;
   //按照id维护emojimessage
   

4. 本单元容易出现的性能问题

统计有多少个连通块

如果直接按照JML实现，复杂度为\(n^2\),用并查集后均摊复杂度基本为o(1)

并查集直接维护即可

统计块内边权和

单次暴力统计复杂度是\(n^2\)，但是注意只有每次修改的时候会最多和n个人修改，所以统计目前的group内的权值和，修改的时候只考虑加入/删除的人对权值和的影响即可，复杂度为o(n)

其实还有一种很妙的分块做法，复杂度为根号n，不过最短路复杂度过大，这里不是复杂度瓶颈，就不多写了

最短路

众所周知，最短路有各种算法可以求，而spfa以及在NOI2018宣告了死刑，所以要用dijikstra来求最短路

求平均值与方差

平均值即为和/人数，统计和之后可以单次o(n)求

方差为\(\sum(a[i]-avg)^2\) 展开后即为\(\sum a[i]^2 -2*\sum a[i]*avg + n*avg^2)\)，统计相关参数即可

求排名

这里用二分更合适一些，单词复杂度为log，不过有很多on的了，我就没有写log的做法。

5. 作业架构设计

MyPerson最基础。

MyMessage用了MyPerson进行维护。

MyGroup用了MyMessage和MyPerson

MyNetWork用了MyMessage MyGroup和MyPerson

6. 心得体会

向优秀的ACM选手致敬

感谢XX, CJY, LXH, GYP 四位优秀的ACM选手给我参考了他们的数据与思路，让我受益匪浅，尤其是XX同学的数据，出一个hack掉我一个，没有她我估计就是0分了。

迭代代码的时候要注意前后的区别

总是改错代码

潜心写代码 相关关系密切的尽量一气呵成

不然容易乱

面向对象第三单元总结

原文：https://www.cnblogs.com/yyxzhj/p/14831924.html