BUAA-OO-Unit3

这是2025年北航OO第三单元的总结博客，希望能对你有所帮助😊

各种测试

• 作业要求，这里就不说了😆

测试数据构造

未测代码永远是错的 ——jyy

• ==以hw10数据生成器为例==

• 在我的测试数据生成器generator.py中，设计了几种测试场景，分别测试不同的输入模式与程序功能，主要测试几个需要动态维护的属性相关的指令

• 由于通过了中测，所以大部分的基本指令单独的功能是没有问题的，因此我设计了几种设计模式来重点测试qba、qtvs以及公众号、文章相关的指令

• 采用随机策略+指定概率来生成

mode_probabilities = {
    	'normal_data': 0.05,
        'stress_test_data': 0.1,                                        
        'special_qtvs': 0.3,                        
        'structured_social_media_test': 0.25,      
        'special_qba_stress_test': 0.3         
    }

• 总共5种模式
  • normal_data：常规测试数据，添加用户、标签、公众号后，剩余的指令随机生成
  • stress_test_data：在常规测试的基础上，增大数据量，同时会先随机设置关系值，然后随机生成指令
  • special_qtvs：专门针对qtvs的生成模式。首先创建用户，接着建立所有其他人与1号人物的关系，并随机添加一些关系，然后全部加入1号人物的标签中，然后分2阶段测试，第一阶段在网络中随机修改关系，添加关系，查询qtvs；第二阶段大致与第一阶段类似，但添加了指令dft，以及增加了qtvs 的概率。
  • special_qba_stress_test：专门针对qba的测试。首先建立一个总人数20%的核心用户群，然后在核心用户中每个用户随机添加2-3个关系，然后开始第二阶段，混合测试：40%概率执行qba查询，并且80%概率查询核心用户，20%概率查询其他用户；30%概率新增或修改核心用户与其他用户之间的关系；30%概率新增用户和关系值，其中一半概率新增用户并添加关系，一半概率在所有用户中随机添加关系
  • structured_social_media_test：第一阶段：添加用户和关系；第二阶段：添加公众号，并添加少量关注和文章；第三阶段：海量的数据来随机进行以下几种操作：贡献文章、删除文章、添加关注、删除公众号、查询接受文章、查询最佳贡献者
• 😁现在回头看，还是有很多可以完善的地方 qwq

架构设计

• jml的架构已经很好了，跟着无脑实现就可以了

维护策略

query_shortest_path

• 这个不太好维护，我是直接计算的，时间复杂度也不会超
• 可以采用的方法比较多：Dijkstra、BFS、双向BFS，可以选择自己喜欢的

query_best_contributor

• 直接算，一层循环就可以

query_triple_sum

• 这个是可以动态维护的，只需要考虑下面这几点
• 写一个计算共同好友数量的方法private int countCommonNeighbors(Person p1, Person p2)
• 每次添加关系时，triple_sum加上countCommonNeighbors返回值
• 每次删除关系时，减去方法返回值即可

query_best_acquaintance

• 动态维护的，而且后面的query_couple_sum依赖这个方法，所以这个方法最好要优一点，不然后面的方法可能要寄
• 在Person中添加int bestAcquaintance, bestValue和bestDirty这三个属性
• 朴素遍历实现一个public void reSetBestAcquaintance()方法
• 添加关系时直接与目前的最值比较，然后维护
• 删除关系时，如果删除的是bestAcquaintance，那么置位bestDirty
• 修改关系时，有这么一些情况
  • 如果修改的就是bestAcquaintance，如果是把value改大了，那么直接维护bestValue即可；如果是value改小了，那么置位bestDirty
  • 如果修改的不是最好的，那么只需要在newValue大于现在的bestValue或者二者相等但id更小的时候维护bestAcquaintance 和 bestValue
• 查询时，如果bestDirty置位了，那么调用reSetBestAcquaintance()方法更新，否则直接返回即可

query_couple_sum

• 没想好怎么维护，比较麻烦。直接计算，一层循环就可以解决
• 遍历每个人p1,然后得到p1的最好朋友p2，如果p2的最好朋友也是p1，那么num++
• 由于每一对算了2遍，所以最后return num / 2;

query_tag_age_var

• 参考的是hyggge的博客，链接在这里
• 有一个小坑点，学长已经说的很详细了

query_tag_value_sum

• 动态维护试了很久，最后放弃了 qwq，用了一个阉割版的动态维护
• Tag里的addPerson和delPerson方法中，遍历一遍person，如果与这个要添加、删除的人有关联，就将valueSum 加上或减去二者关系值的2倍，一定注意是 2 倍，看看jml应该就能知道
• Network中添加关系、修改关系时，遍历全局所有tag,如果同时包含这两个人，就将tag的dirty置位
• 查询时，如果dirty，就重新算一遍，否则直接返回
• 重新算的方法也有讲究，肯定不能直接用jml的双层全遍历，我们可以发现，在我们的关系网中，两个人之间的value一定是相等的，那么在遍历时，第二层循环就可以直接从i + 1开始，不算重复的，最后返回 sum * 2即可

query_received_articles

• 主要是维护这个received_articles这个数据结构，用链表实现的话，头部插入没问题，但是删除的话，需要遍历链表；用hashmap的话并没有办法实现顺序、头部插入这些操作，于是我便自行设计了一个类，LinkedMap，在类中用hashmap存下索引对，然后主体使用链表，这样在删除时，直接根据索引得到目标Object,再设置它的prev next指针即可，这样便实现了头部插入和删除均为O(1)的复杂度
• 但是在hw11中，比较变态的是articles可以重复，也就是一个人可以有多篇id一致的received_articles，这样我们要修改我们的自制类，将HashMap的value替换为一个list即可，如果不太明白可以去看看我的源代码，MultiLinkedMap.java这个类

大模型

• 使用大模型，关键在于prompt，一个好的prompt往往能达到意想不到的效果，同时要提供较为详细充足的上下文环境，exp_6实验提供了一个不错的借鉴

• 在使用的时候，让大模型根据jml先实现个大概，避免一些重复机械的动作，比如：异常识别与抛出，简单方法的实现等

• 然后可以新开一个话题或者换一个模型，一次将一个或者几个方法的jml描述投喂进去，然后让它一行一行分析解释这些jml，然后你就可以对照着它的分析，检查代码的正确性了

• 最后还是要自己走查几遍，多做测试

• 当然，模型的选择也是重要的一环，我自己体验过的：Gemini 2.5 Pro Grok deepseek r1 / v3都很优秀，claude 3.7更是无需多言，只不过用不起😭

Junit 测试

• 需要我们构造数据足够全面，覆盖各种测试场景
• 同时，在检验正确性时候，需要检查ensures assignable pure safe result等种种条件是否被正确实现，需要比较细致全面的检查，也给同学们带来较大的麻烦
• 为了测试不能更改的属性前后是否一致，我选择在生成测试数据时，就生成两份一模一样的，一份调用方法，另一份作为对拍
• （超小声）可以借鉴学长的代码，在此基础上修改以适应自己的架构，应该能省一些事儿🫠

学习体会

• jml确实提供了一个优良的编码指导和架构设计，使得这单元的作业能省不少事儿，一五一十地按照jml的实现应该是不会出错的，只不过可能时间复杂度上不太友好
• 不过一些复杂的项目，使用jml描述可能会把本就复杂的问题更加复杂化，带来理解上的困难，虽然现在已经有一些方法的jml描述我不想看，直接让AI分析了，所以，Jml也有其不足之处
• 善用AI，辅助自己高效地学习与完成作业，比如：可以将看不懂或者很复杂的jml描述让AI分析解释；可以自己的代码给AI让其提出可以优化时间复杂度的方法；可以用AI学习一些知识：并查集、双向BFS等，用好之后，能大大提升自己的效率。
• 但也不能完全依赖AI，缺乏自己的思考与设计，直接不加思考地拷贝粘贴，那样只会适得其反，学无所获