2025_BUAA_OO_Unit3

作业9传送门
作业10传送门
作业11传送门
OO第三单元的主题是JML规格化设计，通过社交网络的例子让我们学会遵守规格，并在规格的限制内灵活实现规格。本单元看似难度不大，但想要顺利通过强测互测，需要仔细考虑所采用的数据结构以及算法。

测试

单元测试

单元测试是对程序中的最小的可测部分进行测试，一般就是我们在各种类里面实现的方法。该测试能够确保每个单元能够独立正确工作，及时进行单元测试能够尽量保证我们程序的正确性，但是编写单元测试的过程可能较为繁琐，同时需要尽可能地覆盖到方法的每一个分支及边缘情况，这样才能确保测试的准确性。

功能测试

功能测试是指从用户的角度触发去验证程序功能是否符合规格。这对于规格化设计来说是十分重要的。对程序进行功能性测试时，一般要根据面向规格来构造数据，然后进行手动或自动化测试。功能测试能够尽量保证功能实现正确，但对程序内部实现逻辑不过多关注，这也容易造成一些结果正确但逻辑错误的隐藏bug难以被发现。

集成测试

集成测试是将已经通过单元测试的单元组合在一起进行测试，验证这些单元之间的交互是否正确。其能够检测到单元之间的交互问题，提高系统的整体质量。但是对于复杂的程序实现，多个方法之间相互联系的情况，集成测试的成本会很高，因为要考虑这些方法之间的交互情况。

压力测试

压力测试是通过模拟高负载的情况，测试系统在极限条件下的性能表现。在互测时很多同学想要检测其他同学是否有TLE的产生对相应程序进行测试应该都是压力测试。压力测试能够提高程序在高负载情况下的可靠性，但如何去模拟这样的高负载情况是压力测试的一大难点。

回归测试

回归测试是在软件修改后重新进行测试，以验证修改是否引入了新的问题。课程的bug修复环节就是典型的回归测试。回归测试保证我们出于增删功能、修复错误、改善性能等需求而对程序进行的修改没有对其他功能产生负面影响。这对于程序的迭代等有重要意义。

数据构造策略

本单元的背景是一个社交网络，里面还有公众号、文章、信息等元素，所有这些元素都可以被一张图展示得很好，因此，构造数据时考虑的其实就是图中点和边的关系。我在进行数据构造时主要有两个策略，一个是随机生成，另一个是面向JML构造数据。
随机生成比较简单，即人、关系等等都完全随机的生成，但是这有个毛病，虽然本单元的输入几乎没什么限制，只要你按照指令格式给予程序指令，那么都有异常处理帮你兜底，但如果完全随机，可能会导致一直在异常处理，所以随机生成也要不那么随机。比如我们可以建立目前已有的人的集合，已有的关系集合等，这样能够方便我们在生成其他指令时能够限制随机的范围，让数据更加合理。
面向JML构造数据就需要根据相关的JML描述来构造特定数据，这些数据一般都是一些特殊情况下的数据，或者是压力数据，常拿来对一些可能忽视的小点或者程序整体性能测试。比如说针对某个查询方法，根据其JML可能会发现该操作的时间复杂度可能较高或是与当前类的其他属性相关联，那构造数据的时候就可以先修改其他属性，在进行查询，这样一直循环，构造一个压力数据。

大模型体验

其实本单元我并未太多使用大模型，使用大模型的情景更多地是询问其相关数据结构的实现以及性能改善的建议。但是在完成本单元的代码作业后再回顾，发现确实有很多地方可以通过大模型来减少自己的工作量，但需要良好地引导大模型才能提高效率，我认为可以根据以下步骤让大模型对我们的实现过程提供帮助：

• 将JML规格提供给大模型，让其分析完整个项目的JML规格并给予我们有关每个类的内部属性使用哪种数据结构的反馈。
• 让大模型分析出哪些方法的实现较为复杂，并提供实现它的简要思路以及推荐相关算法。
• 让大模型分析出哪些方法的实现可能因为一些潜在的难以察觉的因素而出错，并列举出相关因素。
• 根据大模型的反馈完成代码，途中可以不断询问大模型有关数据结构或算法的疑惑。
• 将实现好的代码提供给大模型让其分析可能存在的bug，以及询问其是否有性能优化的推荐，并根据反馈修改代码。
• 在个人发现某些需要改善的点后，针对性地向大模型询问改善的建议，比如有关性能，要将自己现在使用的方法提供给大模型，并提供给大模型预期实现的效果，比如我现在的方法时间复杂度是o(n)，我想优化到o(1)，那就要给大模型讲清楚需求，并理性采纳其建议。

以上步骤及引导方法是我对本单元三次作业的认真回顾下所想出的，拿第一条来举例，我们实现代码首先写的肯定都是一个类里面的相应属性，不会一上来就写类的方法，而像一些数组属性，JML里面不会规定你实现的数据结构，我们需要自己选择，但选择哪种数据结构肯定又要根据使用该属性的方法来确定，而我们就算通读了整个JML，大概理解了每个方法要干什么，但通读下来之后可能仍然对每个方法的内部实现不清晰，要真正到了编写相应方法的代码时，才能加深对方法内部的理解，而这时便可能会发现相关属性的数据结构使用不当而回去调整，我在完成作业时就经常遇到该问题，如果能在一开始就确定要使用的数据结构，那一定能提高不少效率。

架构设计

由于本单元要求我们按照规格实现代码，所以整体上的架构都是JML给出的，简单来说就是一个社交网络负责添加人员、添加关系、修改关系、管理公众号和文章、管理消息等。

图模型构建

社交网络中，很自然地把人作为点，同时在Person内部通过一个HashMap来存储和其他人的关系，也就是整个图里面的边，有关其他元素，例如文章或公众号等，也在Person内部通过HashMap或其他数据结构进行存储，同时在Network里面也用一个大的容器来存储这些元素方便管理。

维护

整个社交网络里面需要维护的东西十分多，因为涉及到很多查询方法，为了尽可能使查询的性能较优，对于大多数查询方法我们都需要对所查询的内容进行维护。
比如Tag里面的平均年龄，年龄方差、不同人之间的社交价值总和等，需要在每一次在tag内部相关属性发生改变时对这些属性进行实时修改来维护，同理对Person的最好朋友、OfficialAccount里面的最佳贡献者等等。需要注意的是，维护的时候不能只将目光聚焦在某个类的内部实现中，很有可能在大的Network中也存在某些修改影响到了某些类的内部属性，这时也需要进行维护。

规格理解

规格限制了我们方法的参数、返回结果等，但是对于整个方法的实现并没有做特别的限制，因此根据一个方法的规格可以有很多种实现该方法的思路，这也是大家都按照规格完成代码但性能差距巨大的原因，在本单元中，我也遇到了很多性能问题，修复这些性能问题是整个单元最为艰巨的任务。

性能优化

• 在本单元第一次作业，对于查询联通的方法，我使用了并查集算法，但仍然未能顺利通过强测每一个点，但是原因也非常诡异。我首先是对并查集进行缓存，也就是如果没有删除关系，那我就会继续使用上一次建立的并查集，当有关系被删除时，我会重新建立并查集，但这样修改后并没有提升我太多的性能，强测未通过的点仍然没通过。再之后我检查了我建立并查集的实现，发现我建立并查集时采用了广度优先遍历的思想，这让我在建立并查集的时候就耗费了不少时间，我将其修改为按点建立后通过了原来大部分未通过的点，但仍有一个点没有通过。最后我将按点建立修改为按边建立后，诡异地通过了最后一个点，至今我仍然觉得匪夷所思，因为这样的修改仅仅只是让原来的时间复杂度除2而已，但整体上来看二者的时间复杂度仍然是相同的。
• 本单元第二次作业，虽然强测通过的点较第一次更多，但实际上遇到了更多的性能问题，分别有如下：
• • 我在实现Person内部的文章数组时使用的是LinkedList结构，但这样在删除文章的时候复杂度就会是o(n)，又因为Network里面进行删除文章操作时还需要对所有人遍历，这样时间复杂度就飙升到了o(n^2)，因此需要一种数据结构来让在头部增加元素以及删除元素的时间复杂度都是o(1)，这样才能解决这个问题，我通过链表加HashMap的一个结构解决了该问题。
• • 对于qba方法，没有在Person内部维护导致时间复杂度为o(n)，整体导致了qcs的复杂度为o(n^2)，在Person内部维护最好的朋友之后解决了该问题。
• • 对于qtvs方法，没有在Tag内部维护相应的valuesum，改为动态维护之后解决了该问题。
• 本单元第三次作业并没有什么特别的涉及性能的问题，很多性能问题还是前两次作业的，因此前两次作业如果将能优化的地方尽可能优化之后，第三次作业也不太可能出现性能问题。

规格与实现分离的理解

规格只是对参数、结果以及一些不变量的限制，并不限制我们实现方法的细节，同理对属性，就比如有一个List[]型的属性，你大可以选择ArrayList、HashMap、HashSet等去实现它，只要你选择的数据结构方便你在方法中的使用即可，对方法也是，你完全可以选择不同的算法去实现，只要结果以及不变式满足规格说明即可，这也要求我们就算按照规格实现程序也不能照着规格就开写，而是要大致对实现的东西有了自己的理解之后再去编写代码。

Junit测试

在对一个方法编写Junit测试时，其JML规格是我们编写测试的一个很好的参考。因为JML里面的描述一般是针对该方法的朴素实现，因此方便我们在编写测试时避免使用自己实现的其他结构，而是按照朴素的实现来获取方法的正确结果，这样能有效防止因为自己实现的其他结构的错误而导致的测试不准确。
同时，JML规格还能为我们构造数据提供思路，比如一些边界情况等，我在自己编写本单元的Junig测试时就通过伪随机生成、完全图生成、空图生成这三种数据生成策略来为测试提供数据，并取得了较好的测试结果。
我们的Junit测试还需根据JML的描述来检验方法的实现，具体来说，不能只检验方法的结果正确性，还要检验方法的实现是否满足规格中的不变式限制，以及是否产生了副作用等，这样才能保证代码实现与规格一致。

学习体会

通过本单元的学习，我了解到了契约式设计，并认识到这是一种较为安全的设计模式。同时在完成作业的过程中我也深刻体会到了规格与实现分离，意识到契约式设计不是死的，而是活的，留给程序员操作的空间仍然是巨大的。同时通过本单元的作业，我更深地意识到数据结构和算法对于程序设计的重要性，当同样一个需求，别人的程序只需要你的十分之一的时间就能完成的时候，你会感到难以置信，而现实中的众多用户肯定是希望自己的需求能尽快得到解决，所以我认为这对于我们未来对实际项目的开发的启发意义是重大的。