OO第三单元总结

OO第三单元总结

一、测试

本单元基于JML进行规格化设计，并且针对实现的代码进行测试。由于每个要实现的功能和方法的规格和作用都已明确给出，所以在具体实现方面着重考虑数据结构和方法复杂度。众所周知，中测就是闹着玩的，真测试还得靠自己。

黑箱、白箱测试

  1. 黑箱测试，着重测试软件的功能需求，是在程序接口上进行的测试。对于每次作业，就是评测机通过大量测试数据力求达到高覆盖性的测试。由于只能看到输入与输出，其内部运行结构我们并不关心，所以是黑箱测试。

  2. 白箱测试，逻辑测试，穷举路径测试。

  • 针对模块中所有的方法路径都需要进行测试
  • 所有逻辑值true和flase都需要进行测试
  • 数据结构的测试
  • 测试数据在合法范围内都需要覆盖测试

比如我们三次作业中都有针对特定方法的OKTest，在验证OKTest的正确性时，对于每一个逻辑值都要测试true和flase，基于此生成的 测试数据就是白盒测试。

  1. 此外单元测试是指对软件中最小的可测试单元的测试，在作业中OKTest就是单元测试；将多个模块耦合进行集成测试，例如作业中类之间方法调用测试；针对性能进行压力测试，在作业中CPU时间要求在15s内；当优化或修改代码后，要进行回归测试保证修改没有带来新的错误。

测试数据构造

  • 通过缩小id范围，增加数据数量来保证每个异常都能被触发
  • 对边界数据的测试，比如测试group的人数
  • 对于涉及到动态维护且复杂度较大的指令，加强测试。比如mr操作可能涉及到并查集的更改，可以先ap500条，然后10000条mr，测试CPU运行时间。

二、架构设计

类图（以第三次作业为例）

classDiagram


class MyPerson{
      -int id
      -String name
      -int age
      -ArrayList<Message> messages
      -HashMap<Integer, Integer> value
      -Integer bestAcqId
      -Integer bestAcq
      -int money
      -int socialValue
      +MyPerson()
      +int getId()
      +String getName()
      +int getAge()
      +boolean equals()
      +boolean isLinked()
      +int queryValue()
      +void setValue()
      +void addSocialValue()
      +int getSocialValue()
      +List<Message> getMessages()
      +List<Message>getReceivedMessages()
      +void clerNotices()
      +void removeAcq()
      +void addMessage()
      +Integer getBestAcqId()
      +int compareTo()
      +void addMoney()
      +int getMoney()
      -void updateBest()
}

class MyNetwork{
      -HashMap<Integer, Person> people
      -HashMap<Integer, Group> groups
      -HashMap<Integer, Message> messages
      -HashMap<Integer, Integer> emojis
      -Graph graph
      +MyNetwork()
      +boolean contains()
      +Person getPerson()
      +void addPerson()
      +void addRelation()
      +void modifyRelation()
      +void modifyGroupRelation()
      +void removeRelation()
      +int queryValue()
      +boolean isCircle()
      +int queryBlockSum()
      +int queryTripleSum()
      +void addGroup()
      +Group getGroup()
      +void addToGroup()
      +int queryGroupValueSum()
      +int queryGroupAgeVar()
      +void delFromGroup()
      +boolean containsMessage()
      +void addMessage()
      +Message getMessage()
      +void sendMessage()
      +int querySocialValue()
      +List<Message> queryReceiveMessages()
      +int queryBestAcquaintance()
      +int queryCoupleSum()
      +void storeEmojiId()
      +boolean containsEmojiId()
      +int queryMoney()
      +int queryPopularity()
      +void deleteColdEmoji()
      +void clearNotices()
      +int queryLeastMoments()
      +int deleteColdEmojiOKTest()
}
class MyMessage{
      -int id
      -int socialValue
      -int type
      -Person person1
      -Person person2
      -Group group
      +MyMessage()
      +int getType()
      +int getSocialValue()
      +int getId()
      +Person getPerson1()
      +Person getPerson2()
      +Group getGroup()
      +boolean equals()
}
class MyGroup{
      -int id
      -int valueSum
      -int ageSum
      -ArrayList<Person> people
      +MyGroup()
      +int getId()
      +void addAllSocialValue()
      +void addAllMoney()
      +boolean equals)()
      +void addPerson()
      +void addValue()
      +boolean hasPerson()
      +int getValueSum()
      +void modifyRelation()
      +int getAgeMean()
      +int getAgeVar()
      +void delPerson()
      +int getSize()
}
class Graph{
      -HashMap<Integer, HashSet<Integer>> uniComponent
      -HashMap<Integer, HashMap<Integer, Integer>> triples
      -HashMap<Integer, HashMap<Integer, Boolean>> isUsefuls
      -int blockSum
      +void addPerson()
      +void addRelation()
      +void modifyRelation()
      +void addTri()
      +void merge()
      +boolean isCircle()
      +int queryTriSum()
      +int queryBlockSum()
      +void removeRel()
      +int queryLeastMoments()
}
class MyEmojiMessage{
      -int emojiId
      +MyEmojiMessage()
}
class MyRedEnvelopeMessage{
      -int money
      +MyRedEnvlopeMessage()
}
MyNetwork --> MyPerson : contains
MyNetwork --> MyMessage : contains
MyNetwork --> MyGroup : contains
MyNetwork --> Graph : contains
MyMessage --> MyEmojiMessage : extends
MyMessage --> MyRedEnvelopeMessage : extends

图模型数据结构

本单元涉及较难实现的部分有最大联通块的数量、三元环的数量、循环路径数量，其中最大联通块的数量动态维护。

并查集实现动态维护最大联通块的数量

此部分我没有使用建树的方法，维护策略如下

graph TB
A1(操作)
A1 --加关系--> B1
A1 --删关系--> C1
subgraph 加关系
B1 --- B2
B1 --- B3
B2 --> B4 
B3 --将所在的两个连通块融合--> B5
B1{判断两人是否已在同一连通块}
B2[在]
B3[不在]
B4[将此关系标记为无用关系]
B5[blockSum--]
end
subgraph 删关系
C1 --- C2
C2 --> C3
C1 --> C4
C4 --> C5
C5 --> C6
C6 --> C7
C7 --> B1
C1{判断此关系类型}
C2[无用关系]
C3[直接删去]
C4[有用关系]
C5[记录此联通块的所有边]
C6[将联通块的所有边变为孤立点]
C7[重新加边]
end

有向图查询三元环数量

将所有关系记为id较小的人指向id大的人的出边，所有三元环都有如下结构：

graph LR
id1 --e12--> id2
id2 --e23--> id3
id1 --e13--> id3
id1((p1))
id2((p2))
id3((p3))

算法如下：

1
2
3
4
5
6
7
8
9
for(Person p1 : people){            //遍历所有人
    for(edge e12 : p1.edges){       //遍历所有出边
        for(edge e23 : p2.edges){
            if(p1.contains(e13)){
               tripleSum++;
            }
        }
    }
}

Dijkstra记录最短路径和次短路径维护循环路径

借鉴评论区大佬的算法，感觉很巧妙，只需要一次Dijkstra就可以得到答案。

三、性能问题

并查集性能

由于我使用HashSet存储一个联通块中的所有人的id，当merge联通块的时候需要操作很多次，远不如建树方便。最初删关系的时候由于直接将所有边（除删去的边）重新加入。在本地对拍的时候，我的运行时间常常是同学的10倍。解决方法：在加关系的时候标记边的类型

  • 两个点已经联通，删去此边没有影响，所以标记为无用边
  • 没有联通，将次边记为有用边

所以只有有用边才需要重新加边操作，无用边可直接删去。优化完运行时间变为建树的两倍

循环路径

第三次作业qlm强测CTLE，主要是mr性能一般，并且Dijkstra没有用优先队列优化。

规格与实现分离

在第一次作业实现过程中，我总是被JML的规格所束缚。但在后续过程中我逐渐认识到，JML只是一个约束条件，在满足规格的条件下，具体实现越简洁越好。比如在MyPerson中JML维护了Persons和Values两个数组分别存放熟人和熟人的亲密度，但其实一个HashMap就够了。所以总结下来，JML就像是规则，在不违背规则的情况下，任何实现方法都是正确的。除此之外，JML就像是项目的维护手册，具体实现千差万别，理解起来很难，但阅读JML能很清晰的理解这部分功能是什么，使用了什么数据结构，以及在后续优化维护中要遵守哪些规则。

在具体实现的过程中，首先将JML翻译为自然语言，然后选择合适的数据结构和算法去实现。

四、OK测试

对于OK测试，我认为是在复杂方法中验证正确性的办法，对于我们作业中的OKTest也只能保证调用方法前后保证约束条件。但是对于invariant和constraint等约束，就会变得相当复杂。而且就第二次、第三次作业的OKTest实现起来并不比测试的方法好实现多少。以至于还要对OKTest再进行测试。但不可否认，OKTest可以保证方法严格符合JML的规格。

对于这方面的建议，我觉得可以真正让OKTest去测试我们实现的方法，每次调用该方法时都会自动进行OKTest，达到自检的效果。

五、体会

本单元中最困难的部分不是根据JML规格去实现方法，而是对于数据结构和算法的选择，所谓1000个读者心中有1000个哈莫雷特。很多时候好不容易实现自己的算法，一跑起来发现好慢，又懒得不想重构，只能小修小改结果杯水车薪。其次对于JML，有些方面它能很精确精准的去约束，但有些时候却比自然语言繁琐很多很多，明明一句话就能讲清楚的事情，却要花上很大篇幅的JML去实现。可能在最新的JML中有更高级更简洁的表达吧。总体上来说通过这三次作业，对于如何根据规格进行实现有了很好的理解，掌握了一些算法。但是毕竟不是站在架构师的角度去想，所以在如何在宏观上去实现规格，进行设计还有很长的路要走。有的时候我们不能只闷头实现，也要抬头去想想如何设计吧。

OO
#OO #总结 #JML
OO第三单元总结
https://etherialize.github.io/2023/05/21/OO第三单元总结/
作者
HZY
发布于
2023年5月21日
许可协议