设计思路与策略
-
细节捕获
首先阅读JML规格，要意识到JML规格是对某一任务实现的具体精确描述，在阅读时，应该要捕捉每个细节，要保证解读的正确性。
-
使用自然语言
可以将JML规格转化为自然语言，比如将addPerson规格转化为“加入一个先前没有加入的人，否则抛出异常”。因为自然语言可以直
白地简述该做的任务，抛弃了JML复杂冗长的描述，并且不透露实现过程，让代码编写者灵活地实现某一方法而不被JML规格的思维
框定死。但要注意不能忽略所有的细节，毕竟准确性为先，自然语言只是用于帮助代码编写者跳出JML规格的实现思维的工具。
-
选择算法与容器
在提取了JML规格中的细节，以及具体任务的描述之后，根据已有知识选择适合的算法与容器，在选择上应该在保证正确性的前提之
下追求时间效率。
测试的方式与策略
-
JUNIT
手动构造一些简单数据用于单元测试，可以进行一些初步简单的测试，但是由于样例是手动构造，测试还是有一定局限性。
-
随机样例生成器
使用java或c等其他语言编写一个随机样例生成器，使用此方式存在的难点是如何保证生成的样例测试覆盖率较高，针对此本人采取以
下设计思路：将本单元的指令分为查询指令（不修改数据）与修改指令（修改数据），由于每执行一个修改命令就有可能影响所有查
询指令的结果，因此每随机生成一条修改指令，就要在其后生成当下所有有效的查询指令（通过遍历每个Person，每个Group，每个
Message，可以实现有效查询指令的全覆盖，再次基础上，扩充一些无效的id来检测异常类）。对于修改指令的生成顺序，可遵循先
增加后删除的原则生成，即将删除指令留在最后，也可以直接随机排列，但要保证修改指令的参数需要使用随机数。构造完后，将样
例再不同的代码上运行，比较输出，不同的输出就是bug存在的地方。根据本人实践，此方式测出了不少的bug，效果显著。
容器选择
-
ArrayList
ArrayList容器内的存储结构与普通数组类似，对于随机查询更改某一下标的元素、交换两个不同下标的元素、在尾部删除或增添元素等操作具有较高的效率。因此
ArrayList容器可用于实现栈（尾部增删）、堆（尾部删除、交换元素）等数据结构，此外也可以用于基于交换的排序算法（交换元素）。
-
LinkedList
LinkedList容器顾名思义，就是以链表方式实现的线性表，其相比于ArrayList优势是随机在某一位置插入删除元素的效率较高，因为
ArrayList的插入操作需要移动后续元素而LinkedList不需要，两者在头部插入删除元素的操作上效率差异十分显著（O(n)与O(1)的区别）。因此
LinkedList非常适用于实现队列数据结构（头部删除，尾部插入）。 -
HashMap & HashSet
HashMap用于存储键值对，实现key到value的映射，将一个key值传入get()方法时，首先调用hashCode()计算哈希散列值，哈希值相同的key，被链表结构组织起来，因此还需要遍历链表中的元素，由于散列后链表的长度不会很长（一般散列效果较好的情况下
每个链表的长度是常数级别的），复杂度近似于O(1)。
HashMap适用于依据value对象的某个特征key值快速查找到value的所有信息（例如本单元作业中，依据person_Id快速查找到对应的person）。
HashSet实现基于HashMap，只不过HashSet用于存储互不相同的元素value而不是键值对，用于快速判断某个元素在不在一个集合内部。
-
TreeMap & TreeSet
TreeMap与TreeSet分别具有HashMap与HashSet的功能，区别在于TreeMap与TreeSet支持元素的排序，其通过红黑树（是一种准平衡二叉树）数据结构实现。因此若需要有序遍历键值对或集合中的元素，可使用
TreeMap与TreeSet，但是其get()与put()方法复杂度是O(log(n))级别（因为要维护红黑树），相比于
HashMap与HashSet的O(1)复杂度还是有较大差距的，因此没有排序的需求尽量不要使用。
性能问题
-
queryNameRank
qnr是查询某人姓名在所有姓名当中的字典排序名次的指令，若直接按照所给JML规格的描述实现，则需要O(n)的复杂度，因此当
人数较多时查询的性能较差。实际上这也是有优化的余地的，可以采用平衡二叉树的数据结构实现在O(log(n))复杂度内实现查询，当
然代价是addPerson方法需要额外增加O(log(n))的时间复杂度来维护平衡树。本人使用AVL树（一种严格平衡的二叉查找树）维护
姓名数据，因为AVL树的插入元素的性能好，删除元素的性能差，但本单元恰恰没有从NetWork中删除Person的方法，所以选择了
相比于红黑树更易于实现的AVL树。在具体实现上，只要在AVL树的每个节点上维护左子树大小、右子树大小和姓名这三个量，并以
姓名为关键字建树即可（因为左右子树大小代表了比当前节点姓名字典序小或大的元素个数）。
-
isCircle & queryBlockSum
这两个查询指令主要的优化是使用并查集方式实现而非使用图搜索算法(dfs或bfs)。对于并查集仍然有路径压缩与按秩合并两个优
化，若不采用则总体性能会差一些，对于一些极端的例子，并查集需要加上这两个优化才能完全发挥其在时间性能上的优势。
-
queryGroupValueSum & queryGroupAgeMean & queryGroupAgeVar
qgvs、qgam、qgav这类操作的特点是可以通过额外增添一个全局的变量，在addPerson、delPerson等方法中对全局变量进行维护
来实现。对于qgav计算age的方差，通过公式恒等变化知，只需维护age的总和与总平方和即可，即在addPerson、delPerson等方
法中对总和与平方和增减。这样的好处是查询时，只需要经行少量的运算，而不需要遍历计算所有的age数据。对于qgvs，注意需在
addToGroup、delFromGroup、addRelation方法中维护。
-
SendIndirectMessage
找最短路径，思路比较明显，使用dijkstra算法，可采用优先队列的方式实现进一步的优化。
架构设计
-
将
NetWork类的对象视为图结构，Person类的对象视为图中的节点，Group类为图中某些节点的集合，Message类为两个节点或Group中节点之间的通信。每个Person需要记录其邻接节点，采用HashMap存储personId与person之间构成的映射关系，这样可快速查找到某个personid对于的Person对象。除了邻接节点外就是各种Person的个人信息数据，在
NetWork中采用各种方法对这些数据进行维护，对于queryNameRank采取了AVL树作为维护的数据结构，isCircle、queryBlockSum使用并查集来维护，
SendIndirectMessage 使用堆优化版本dijkstra。