BUAA OO第三单元总结：模拟社交网络

本单元作业的主要任务为根据JML规格，完成对应的社交网络系统。

不得不说这一单元的代码量相比之前降低了很多，需要思考和完成的部分相比之前也有所减少，然后不幸的是本单元的分数却实在惨不忍睹：40->10->0，归根结底原因是没有进行足够充分的测试，也没有想着如何才能更好地优化代码，最终导致本单元作业只能低分划过。

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

本次完成作业的基本策略是先照搬规格，再整体性优化。

1. 由于规格其实对于代码的要求说明的较为清晰，因此一开始只要老老实实地按照规格进行翻译，其实基本可以完成代码需要的工作，除了对于部分需要利用到图论的内容，需要撰写对应的代码实现相应的功能。（但是每一次作业都有因为看错规格导致代码出错的情况，泪目）
2. 在利用规格完成代码之后，就是对原代码进行一定程度的优化，例如性能上用更高效的算法（例如并查集解决iscircle），对部分o（n*n）复杂度的计算，设计一个临时变量，及时记录了当前计算的结果，并在数据增添删除的时候，对相应的结果进行相应的更新，可以很大程度上降低复杂度。还有一点就是整体化的考虑，由于几个类myperson,mynetwork,mymessage之间联系密切，所以对于部分数据的计算和处理可以根据实际情况进行适当地迁移。

---

二、测试方法和策略

本单元我做的最不好的一点可能就是没有进行充分和全面的测试，虽然有时间等多方面的因素，但是也实实在在地告诫了我测试的重要性。

其实从测试的角度来说，有以下几个方面进行考虑。

1. 对于边界数据和运行时间的测试，由于性能优化等相关问题，本单元的作业经常会出现ctle的情况，因此构造相对来说复杂度较高的指令进行密集型测试来逼近最长运行时间是一个很重要的测试，也是优化的重要依据。
2. 对于各指令的基本测试，虽然这个测试最基本，但是前期若未进行足够的测试，仍然会出大问题，比如在第一次作业中，我对qbs指令完全没进行相关的测试，认为通过了中测就没有问题，结果导致强测中所有涉及到qbs的代码全部炸锅。
3. 生成一定量的大代码量的随机数据进行对拍测试，由于代码之间联系密切，通过随机数据测试也能较好地测试代码的正确性，对于部分较为明显的错误能较快发现。

不过这个单元我还是没有学会使用Junit模块进行测试，测试部分的缺失也是本单元强测分数较低的重要原因。

---

三、容器的选择和使用

• arraylist:在第二次作业及之前，由于没有充分考虑到性能的重要性，因此所有的存储数据的结构都使用了最经典的arraylist，然而效果就是最后带来了痛苦的重写过程。当然对于Myperson中存在的messages等数据单元，由于涉及到插入的特定顺序，最终还是保留了arraylist的形式进行存储。
• hashmap:仔细分析本单元作业，由于各个实例id的独立和唯一性，以及对于相关数据顺序方面的要求没有这么强，因此利用hashmap真的是无比合适的选择，首先对于相关数据查找的复杂度直接降到o(1)，从而简化了大量的操作。

---

四、性能问题和相应的解决方法

性能问题可能是本单元思考算法和代码方面最富有难度的部分，每次被ctle卡到的时候也总是需要重新去思考对应的代码解决方法。

1. 很重要的一点全局性优化可能是由arraylist转换为hashmap，这个对查找方面的性能提升很大，同时也减少了代码量（确信）。
2. 除此之外就是一系列的特定指令优化，例如iscircle判断是否连通，从最开始一步步的遍历法进化到了并查集的方法解决，每次添加相应的关系对各节点的信息进行更新，很大程度上降低了复杂度。
3. 再比如处理queryGroupValueSum的时候可能会涉及到o（n*n)的复杂度计算，也会卡t,之后在处理这部分代码的时候，我对于Mygruop类进行了新的构造，设置了valuesum,ageVarSum,ageSumsq,ageSum等变量来时刻保存当前状态的对应值，每当对原数据进行增添和删除时及时更新计算相应的变量，从而降低复杂度。
4. 对于最短路径的算法使用了Dijkstra算法，虽然可以完成强测大部分的测试点，但是由于效率问题仍然会卡t，正在考虑使用堆优化的方法来提高效率。

五、最终结构设计分析

本单元完成了一个基本社交网络的模拟，最基础的类为Myperson，该类存储了最核心的根节点之后各种各样的类也是围绕该节点展开，节点之间存在联系，即构成边，并赋值为value。同时还存在Mygroup这种结构可以保存多个person，以及相应的数据内容。除此之外还有Mymessage的结构可以实现人与人直接，人与组织之间信息的传递。最后Mynetwork类将之前的各类联系和囊括在一起，保存了之前各类存在的信息。

• Myperson为基础类
• Mymessage一部分基于Myperson的相应性质。
• Mygruop基于以上两个类进行了实现
• Mynetwork囊括和保存了以上三个类。