一、 设计策略
实现规格时我的策略是先通读规格，将其大致翻译为自然语言并找出细节的重点，之后针对某一方法的规格进行如下分析
如果没有以上的优化方法，则按照规格原样实现该方法（比如dce由于要在messages中删除包含这些表情的消息，故而还要遍历部分表情，用堆优化的意义不大，用普通的遍历就可以）。
二、 测试设计
1) 单元测试阶段：
各独立单元模块在与系统地其他部分相隔离的情况下进行测试，单元测试针对每一个程序模块进行正确性校验，检查各个程序模块是否正确地实现了规定的功能。
2) 集成测试阶段：
集成测试是在单元测试的基础上，测试在将所有的软件单元按照概要设计规格说明的要求组装成模块、子系统或系统的过程中各部分工作是否达到或实现相应技术指标及要求的活动。
3) 系统测试阶段：
将通过确认测试的软件，作为整个给予计算机系统的一个元素，与计算机硬件、外设、某些支持软件、数据和人员等其他系统元素结合在一起，在实际运行环境下，对计算机系统进行全面的功能覆盖
2. 单元测试阶段：
1) 基础知识
Junit是一个可编写重复测试的简单框架，是基于Xunit架构的单元测试框架的实例
常见注解
@Test:这个注解说明下面的方法作为一个测试方法。
@BeforeEach:每一个测试方法之前运行，为它们准备共同需要的资源。
@AfterEach:在每一个测试方法之后运行，如果外部资源在 Before 方法中分配，那么就需要在测试运行后释放他们。
@BeforeAll:在类中的所有测试执行前运行一次，所修饰的必须是静态方法，常用于加载配置文件。
@AfterAll:在所有测试结束后执行，可以用来进行清理活动。
检验方式
assertArrayEquals(expecteds, actuals) 查看两个数组是否相等。
assertEquals(expected, actual) 查看两个对象是否相等。
assertNotEquals(first, second) 查看两个对象是否不相等。
assertNull(object) 查看对象是否为空。
assertNotNull(object) 查看对象是否不为空。
assertSame(expected, actual) 查看两个对象的引用是否相等。
assertNotSame(unexpected, actual) 查看两个对象的引用是否不相等。
assertTrue(condition) 查看运行结果是否为true。
assertFalse(condition) 查看运行结果是否为false。
assertThat(actual, matcher) 查看实际值是否满足指定
2) 实现方法
以该方法(dfg)的规格为例，需要测试四个情况：从未加入过该组，加入过该组但没有加入过人，加入过该组和该人但人不在这个组中，以及加入过该组和该人且人在组中。针对四种情况分别构造测试样例，看程序在各情况下能否按预期抛出异常或正确运行结束。在测试时期输出删除前后组内人员情况以检查删除效果。
/*@ public normal_behavior @ requires (\exists int i; 0 <= i && i < groups.length; groups[i].getId() == id2) && @ (\exists int i; 0 <= i && i < people.length; people[i].getId() == id1) && @ getGroup(id2).hasPerson(getPerson(id1)) == true; @ assignable groups; @ ensures (\forall int i; 0 <= i < groups.length; \not_assigned(groups[i])); @ ensures (\forall Person i; getGroup(id2).hasPerson(i); @ \old(getGroup(id2).hasPerson(i))); @ ensures \old(getGroup(id2).people.length) == getGroup(id2).people.length + 1; @ ensures getGroup(id2).hasPerson(getPerson(id1)) == false; @ also @ public exceptional_behavior @ signals (GroupIdNotFoundException e) !(\exists int i; 0 <= i && i < groups.length; @ groups[i].getId() == id2); @ signals (PersonIdNotFoundException e) (\exists int i; 0 <= i && i < groups.length; @ groups[i].getId() == id2) && !(\exists int i; 0 <= i && i < people.length; @ people[i].getId() == id1); @ signals (EqualPersonIdException e) (\exists int i; 0 <= i && i < groups.length; @ groups[i].getId() == id2) && (\exists int i; 0 <= i && i < people.length; @ people[i].getId() == id1) && !getGroup(id2).hasPerson(getPerson(id1)); @*/ public void delFromGroup(int id1, int id2) throws GroupIdNotFoundException, PersonIdNotFoundException, EqualPersonIdException;
3. 集成测试阶段：
1) 基础知识：测评机
针对主要情况：功能性和覆盖性测试为主，校验正确性。
针对主要算法：卡数据结构最坏情况。
随机生成数据：查漏补缺性质。
2) 实现方式：
借用了别人（感谢ch大佬）的测评机，在其基础上自己手动构造了一些反复sim和qbs等卡时间的数据点。
4. 系统测试阶段：
1) 基础知识：集成测试CI
持续集成是一种软件开发实践，即团队开发成员经常集成（此集成非彼集成）他们的工作，通常每个成员每天至少集成一次，也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建（包括编译，发布，自动化测试)来验证，从而尽快地发现集成错误。
2) 实现方式：
无，摘自大佬的PPT，自己不知道该怎么用，所以选择提交前手动check style。
三、 容器选择
（一）--Map
由一组键值对的储存形式来保存，可以用键对象来查找值。
Map
包括HashMap和TreeMap，键值对都可以为null，可以多维扩展。而如HashTable则不允许插入空值。
HashMap更适合查找、删除、插入；TreeMap更适合遍历。TreeMap是有顺序的HashMap。
public Set keySet()： 返回这个Map的所有键的集合，因为Map中键是唯一的，所以返回使用一个set
public Collection values()： 返回这个Map的所有值的集合，因为值可能重复，所以返回一个Collection
public Set entrySet()： 返回一个实现Map.Entry接口对象集合，使用这个方法可以遍历每一条记录。
（二）Collection
主要是单个元素的集合
包括HashSet和TreeSet，set代表的是数学上的集合的意思，所以set中的元素不可以重复（用HashCode进行区分）。
Set中无序，不存在indexOf
(1) HashSet：
底层使用散列函数，性能优于TreeSet，除非需要排序否则一般选择此。
(2) TreeSet：
底层使用红黑树，其中元素要求实现Comparable接口
2. List
包括Vector、ArrayList和LinkedList，所有元素可以重复。
(1) Vector：
已经被弃用，线程同步，访问速度慢
(2) ArrayList：
底层用数组实现，但可以动态增长（初始容量为10）.
随机访问速度快（按下标查找），插入删除较慢。
(3) LinkedList：
底层用链表实现，可以实现很多队列、栈的数据结构
插入和删除速度快，但是查找需要遍历整个链表，速度较慢
3. Queue
包括PriorityQueue。LinkedList提供的支持队列操作的方法事实上是实现了Queue接口（LinkedList可以向上转型为Queue）
满足“先入先出”。
offer:讲一个元素插入对尾
peek:不移除的情况下将元素插入队尾，队列为空返回null
element:不移除的情况下将元素插入队尾，队列为空报错
poll:移除并返回队头，队列为空返回null
remove:不移除的情况下将元素插入队尾，队列为空报错
（三）总结
考虑到Network接口需要实现的方法中存在许多由id取用户、取组群、取消息等的需求，故而用Map。而考虑到散列函数的查询基本上达到O(1)了，所以用户、群组、消息的储存全部选择了用HashMap，此外对孤立用户的维护基本上每次都要遍历，就用了ArrayList，方便查找。
而Person接口中的熟识用户和亲密度一一对应，所以直接HashMap管理。消息经常操作第一个和前四个，所以考虑到用下标取消息的要求，用了ArrayList（其实用LinkedList会好一点）。
Group接口中要求管理用户我用了自己实现的FHQ-Treap，但其实用HashSet也可以。
四、 性能问题
1) qc和qbs：
判断两个用户是否连通只能用qc（isCircle方法），如果没有维护每个连通图的公共节点的话，只能每次遍历，qbs会变成O(n^3)，这样多次qbs必然超时。
2) qgam和qgav：
如果在向组群中加入用户时没有维护年龄和的话，qgam就要遍历，时间复杂度为O(n)，此时qgav先算平均再遍历求方差，时间复杂度为O(n^2)。
3) sim：
这个方法的问题主要是最短路径的查找，朴素的Floyd方法的时间复杂度为O(n^3)，原始的Dijkstra方法时间复杂度为O(n^2)。
2. 避免原因
1) qc和qbs：
使用路径压缩并查集的qc时间复杂度为O(log* n)，近似为O(1)。而qbs我在加人的时候同时建立了孤立用户的ArrayList，在加边的时候动态调整该List，所以qbs的时间复杂度变为O(1)（平摊下去）。
2) qgam和qgav：
在向组群中加入用户时维护年龄和以及年龄的平方和，计算方差时手动化简，可以得到“方差=年龄平方和-2*平均值*年龄和+人数*平均值^2”，故这两条指令时间复杂度都是O(1)。
3) sim：
考虑到模型事实上为稀疏图，大部分节点只和少数节点之间有边，故Dijkstra算法中将遍历全部节点改成遍历与当前节点直接相连的节点，时间复杂度变为O((m+n)*log n)
五、 架构设计
感觉没什么好说的了……前面也差不多介绍了……那么就分享一下并查集和我对FHQ-Treap的应用吧
首先节点间的关系是无序的。
事实上是一种树状结构，通过一层一层往上访问父节点，直达树的根节点（父节点即其本身），判断两个元素间是否有关系只要看其根节点是否相同即可。每个节点维护自身编号、父节点编号和自己子树的秩（初始为1，为了后续优化）。
如果两个父节点合并时随机，或者固定A并入B中，有可能退化为一个单向链表。故合并时固定选择使新的树秩最小的合并方法。
查找时递归调用寻找根节点即可。
2. FHQ-Treap
具体基本上就是按训练讲解实现的，考虑到用户名可能重复但id独一无二，故将用户id作为值，用户名作为权重。
3. 堆优化的Dijkstra算法
Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。
Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，
然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。
但在本单元的社交网络模型中，大部分点只和少数几个点连通，考虑到不连通的点间距离为无穷大，即使遍历也没有用，不会被松弛，故只需要考虑和这个点连通的几个点即可。
将优先队列定义成小根堆，将源点的距离初始化为0加入到优先队列中，然后从这个点开始扩展。先将队列中的队头元素 ver 保存到一个临时变量中，并将队头元素出队，然后遍历这个点的所有出边所到达的点 j，更新所有到达的点距离源点最近的距离。
如果源点直接到j点的距离比源点先到ver点再从ver点到j点的距离大，那么就更新dist[j]，使dist[j]到源点的距离最短，并将该点到源点的距离以及该点的编号作为一个pair加入到优先队列中，然后将其标记，表示该点已经确定最短距离。因为是小根堆，所以会根据距离进行排序，距离最短的点总是位于队头。一直扩展下去，直到队列为空。
原文：https://www.cnblogs.com/Heather-He/p/14819441.html