BUAA-OO-Unit3
BUAA-OO-Unit3
测试过程
这一单元的测试包括了课程组提供的 junit 测试练习，和课下对自己代码的测试。
junit 测试练习主要是使用随机数据生成后检查方法调用结果是否和 jml 语句预期相同，以及一开始往往被忽略掉的 pure 属性是否满足。
对自己代码的测试，正确性使用了随机生成数据并与同学对拍的方法来检验；时间复杂度则主要靠自己对代码方法的分析来把控（因为自己很难构造出边界数据，本地与评测机的运行环境也有差异，效果未必好）。
不过，这单元我出现的唯一一个 bug 并没有检测出来：在找关系最好的人的时候，如果没有关系，那么就返回 -1.然而，如果有人的 id 本身就是 -1，那么就会出问题。这个 bug 没有被自己检测出来主要是因为随机数据很难随机到这样一个特定的 id，覆盖面不够完善。
黑箱测试
黑箱测试是一种软件测试方法，其中测试人员不需要了解被测试的软件系统的内部结构、设计和实现。测试人员只关注软件的输入和输出，检查软件是否按照需求规格书正常运行。黑箱测试主要用于功能测试、接口测试、性能测试等，它不考虑程序内部的逻辑结构，而是通过测试来检测程序是否能够正确地接受输入数据并产生正确的输出结果。
在第三单元的学习中，对于 junit 的测试便是属于 黑箱测试，我们在编写测试代码时，并不知道被测程序的实现，而只是对于代码的正确性进行检查，检查代码是否符合 jml 规格中给出的限制。jml 接口规格，为黑箱测试提供了一定的便利性和准确性。由于被测程序未知，测试者可能并不能考虑到每一个测试的边界条件以及程序的易错点，这使得黑箱测试对测试人员的要求比较高，例如这单元的 junit 测试，很多时候大家并不能一遍通过，甚至需要反复多次修改和提交才能把所有情况都考虑到。
白箱测试
白箱测试与黑箱测试相反，它需要测试人员了解程序的内部逻辑结构、代码结构和实现。白箱测试基于代码的内部逻辑来设计测试用例，目的是检查程序的内部操作，确保所有内部组件已被测试。白箱测试通常用于单元测试，可以检测代码中的逻辑错误、循环复杂度、分支覆盖率等。
白箱测试往往要遵循以下几个原则：
- 保证一个模块中的所有独立路径至少被测试一次。
- 对所有的逻辑判定均需测试取真和取假两种情况。
- 在上下边界及可操作范围内运行所有循环。
- 检查程序的内部数据结构，保证其结构的有效性。
而此前在 pre 课上进行的 junit 测试，是对自己的代码进行的测试，自己的代码对自己是可见的，这种测试可以被归类为白箱测试。白箱测试主要可以测试代码的逻辑是否犯错，是否和自己期望得到的结果相符合；并可以有针对性的对一些易错语句进行测试评测时所关注的也是测试代码的覆盖率。
单元测试
单元测试是针对软件中最小的可测试部分进行检查和验证。通常，一个单元是应用程序中最小的可测试部件，例如一个函数、一个方法或一个对象。单元测试的目的是确保每个单元都能正确地执行其设计的功能。单元测试通常由开发者编写，可以自动化运行，以便在开发过程中快速检测和修复错误。
功能测试
功能测试验证软件的每个功能是否符合业务需求。它侧重于应用程序的主要功能，确保它们正常工作。功能测试通常由质量保证（QA）团队执行，可以在用户界面（UI）级别进行，也可以在没有用户界面的情况下进行，即通过 API 进行。
集成测试
集成测试是在单元测试之后进行的，它测试不同模块或服务之间的接口和交互。这种测试的目的是确保当多个组件组合在一起时，它们可以正常工作并且接口之间没有问题。集成测试可以是单级集成，也可以是多级集成，逐步将不同的模块或服务组合起来进行测试。
压力测试
压力测试是一种性能测试，它评估系统在极端工作负载下的稳定性和错误处理能力。压力测试的目的是确定系统的稳定性和最大工作能力，包括响应时间、稳定性和资源消耗。通过这种测试，可以发现系统的薄弱环节，并确保在正常工作条件下系统不会因为过载而崩溃。
回归测试
回归测试是在软件发生更改（如功能更新、bug修复、性能改进等）后进行的，以确保这些更改没有引入新的错误，也没有影响到现有功能。回归测试确保软件在修改后仍能按预期工作。
测试数据生成
测试数据生成主要要从数据量大小和数据种类覆盖两个方面来考虑。数据量需要根据测试的目的来考虑，如果测试的是针对正确性，那么需要适中的数据量：需要有一定的复杂度，但也不能过多导致程序运行时间过长；如果测试的是针对代码效率，那么需要较为大量的数据，既可以体现代码的性能，也不应该过于超出实际应用时的数据量。
架构设计
这个单元的架构其实 jml 已经基本上实现好了，对于部分在 Network 中的复杂查询方法，在更底层的类（Person, Tag）里增加实现即可。总体的架构还是比较清晰的，实际上就是一个顶层的图（Network），图里面存节点（Person），节点里存边（Acquaintance）以及其它信息（Tag, Message）。
这一单元建图基本都是直接加点、加边，对于一些可以在 $O(N)$ 复杂度内直接得出结果的方法，我都是直接算，比如查连通块什么的，都是直接 dfs。
部分查询方法的实现
isCircle
判断两个人是否在一个连通块中，我选择直接 dfs。
queryBlockSum
dfs 整张图即可，这里由于感觉每次都 dfs 开销有点大，我加了一个查询后只在加边和删边之后才重新计算。
queryTripleSum
这个操作显然是不能直接枚举或者是 dfs 两层的，时间复杂度不对。考虑维护这个信息。我们在加边的时候，考虑新边的两个端点，新增的 triple 数量其实是两个端点的邻居集合的交集，删边的时候同理，triple 数量会减少这么多。这样，虽然加边和删边的复杂度变成了 $O(N)$ 的，但是把查询 TripleSum 的复杂度降到了 $O(1)$ 的，这是我们乐意看到的。
queryTagValueSum
朴素算法需要 $O(N^2)$ 遍历，显然是不行的。考虑维护这个信息：往 tag 里加人的时候 $O(N)$ 扫一遍 tag 里的人维护；加边删边的时候 $O(N)$ 遍历所有 tag，看一下这条边是否对 tag 有影响，即边上的两个人是不是在同一个 tag 里（有想过维护每个人当前都被哪些 tag 所拥有，不过感觉意义不大就没有实现）。
queryTagAgeVar
维护 tag 里的年龄均值与方差，实际上维护年龄的和与平方和就行了（展开一下式子），就可以做到 $O(1)$ 维护 $O(1)$ 查询。不过理论上 $O(N)$ 查询也没啥问题…
queryBestAcquaintance
这个方法朴素的实现是 $O(N)$ 的，然而在 queryCoupleSum 方法中需要调用 $N$ 次这个方法，因此需要让这个查询复杂度为 $O(1)$。一开始写了在加边时 $O(1)$ 维护，删边时 $O(N)$ 维护，理论上复杂度也没错，后来改成了用大根堆存边，每次加边时 $O(\log N)$ 插入堆，删边不管，查询的时候先看堆顶的边是否还存在，如果不存在就 pop 掉，直到堆顶的边存在或堆为空。这个操作虽然看似复杂度比较大（有可能单次查询的时候堆里很多很多边都已经不存在了），但实际上它不会一直很大，复杂度是均摊下去的。
有趣的是，在改之前我的 test 代码可以在 1s 内跑完，但改成大根堆后代码需要跑 3s 多。理论上改成大根堆后维护的复杂度变成了 log 级别，应该显著优于改之前的。之所以出现这种与预期截然相反的情况，是因为 test 代码里只在一直加边，而改之前加边复杂度 $O(1)$，改之后复杂度变成了 $O(\log N)$，因此变慢了。这也反映了实际应用中，最坏时间复杂度有时并不能反映真实的运行时间情况。
queryCoupleSum
直接遍历就行了，正是因为这个方法的存在，限制了 queryBestAcquaintance 方法的查询复杂度必须 $O(1)$。
queryShortestPath
dfs 或者 bfs 都行。
性能问题
在完成作业的过程中，我对时间复杂度进行了一些思考，并在此基础上实现的比较好，这使得我的作业代码始终没有出现性能问题。
对时间复杂度的考量
参加过算法竞赛的同学应该普遍对于时间复杂度的概念比较敏感，在算法竞赛中考虑的时间复杂度通常是 最坏时间复杂度，因为出题人会设计各种极端情况来保证选手代码做法的严格正确性。
但在实际应用中则并不是这样，我们更多的可能是关心 平均时间复杂度。这是因为实际应用中的数据往往不会总是最坏情况，而是符合一定的分布，平均时间复杂度能够更好地反映算法在实际应用中的性能。并且，对于一些小的优化，也许对代码的时间复杂度并不会有任何影响，但是在实际应用中往往能起到一定的优化效果。
在OO这一单元的任务中，这个问题得到了很好的体现。
获取了数据范围后我们发现，最多会有 $10^4$ 次操作，而图上的点和边是通过操作慢慢进行添加的，查询操作的复杂度往往也只与点数和边数有关。对于这个数据范围我做了如下的考虑：假设极端情况下有 $5\times10^3$ 个点和 $5\times10^3$ 条边，有 $5\times10^3$ 次查询操作（这个情况显然超出了数据范围，但这样能够帮助我们对最坏的时间复杂度进行分析），一般而言时间复杂度为 $O(N^2)$ 的算法可以在 1s 内跑完大小为 $3\times10^3$ 的数据，那么我有 10s，$O(N^2)$ 的算法理论上可以跑完大小为 $5\times10^3$ 的数据，也即可以完美的完成这次作业。
那么理论上哪怕我所有操作都采用时间复杂度为 $O(N)$ 的实现，都可以通过评测。但真的是这样吗？考虑到 java 代码的运行效率本就远慢于 C/C++，以及常数问题，这样做还是有一定风险（不确定到底是否会强测 TLE，因为我没试也不敢试 qwq）。那么，是否又要考虑把所有操作的时间复杂度都降到 $O(N)$ 以下呢？首先这基本无法做到，其次也并没有必要。因为有很多操作的时间复杂度都是低于 $O(N)$ 的，或者操作时的 “N” 比较小（也即常数小）等等，综合到一起，虽然严格的时间复杂度仍然是 $O(N^2)$ 的，只看这个严格的时间复杂度，可能会得出无法通过评测的结论，但实际上还是可以跑得很快，很好的通过强测。
那么，我们的结论是：首先我们需要严格保证每次操作的时间复杂度不能超过 $O(N)$，这是最最基础与关键的；其次，即使一个操作的时间复杂度是 $O(N)$ 的，但我们要尽可能的让它的常数减小。打个比方，如果一张图在两次查询之间没有过加点或加边，那第二次查询时我完全没有必要再 $O(N)$ 算一遍，我可以直接给出结果。这种小优化在算法题里甚至不能被称之为优化，不会起到什么效果，也不会有人这样写；然而在实际应用中，它有的时候确实能起到作用，但如果陷入到写算法题的思维中，往往会忽视这些小地方。
规格与实现分离
在根据 jml 实现代码的过程中，我们发现对于一些复杂的方法，直接按照 jml 上的阐述来实现（例如多重循环），是满足不了性能要求的。
实际上，jml 只是对方法运行 最终结果 的一个限制，而并不是对实现过程的要求或提示。虽然有的 jml 看似给出了实现的方法，但这并不是 jml 真正想要提供给我们的。因此，规格和实现分离是一个很正常的现象。
我认为 jml 只是一个设计者和实现者之间的一个沟通的桥梁。人的思考往往是借助自然语言来进行的，而自然语言的描述往往是不够精确的。虽然自己能够明白自己的意思，但同样的话阐述给其它人，语义很可能产生一定偏差。因此，往往是设计者把自然语言转换成 jml 传递给实现者，实现者再阅读 jml，并将它转换成自己能够理解的自然语言，再据此实现代码。而实现者在将 jml 转换成自然语言的过程中，理应会丢失 jml 中的实现方法，而自己根据自己的架构设计与需要，来选择算法，实现代码。
junit 测试心得
相较于之前的“盲目测试”，这次的 junit 测试有了 jml 规格进行参考，这使得测试更为规范。不过，在测试的过程中需要严格的考虑到 jml 中涉及的所有情况以及所有规范要求，而不是仅仅关注结果。例如 pure，assignable，以及抛出异常等等。
junit 用来检测 jml 规格和代码的一致性还是非常不错的，前提是 junit 写的好，能够完全符合 jml 的要求，以及数据生成的规范性和覆盖率足够好。
本单元学习体会
相较于前两个单元，这一单元其实更符合实际生产生活中的设计开发：理解需求，实现需求，测试代码。
本单元的代码实现也让我对面向对象设计有了更深的理解。通过设计合理的类和接口，我可以更好地管理和扩展代码。我也学会了如何根据jml规格进行代码实现，而不是盲目地根据个人理解去编写代码。虽然，对于更复杂的一些问题的阐述，jml 可能会带来更多理解上的困难，进而本末倒置，这是一个值得思考的问题。