第三单元总结博客

设计策略

~在实现作业需求的过程中，我通过以下几个部分完成对方法的实现。

@一、尝试通过函数名来了解函数行为；

@二、通过jml描述的异常行为完成抛出异常的部分；

@三、通过对函数名的理解实现函数功能；

@四、通过jml语言对自己的实现进行验证和修改。

@五、通过“弱测”来验证函数的基础功能的正确性。

设计测试

~设计测试时并没有针对jml进行测试，只是完成了一个随机生成数据的函数，并没有搭建评测机来对jml的特定场景进行针对测试。

~从强测的结果来看，关于整数除法的取整问题成为了bug的主要原因。

@除数不能为0，在实现过程中容易被忽视，在与求平均值相关的方法中，首先要判断size是否为0。

@在向group发放红包的时候，由于int型除法的机制，必须完全按照jml的规定来写。例如，10个人的group，一个人发送了一个9块钱的红包，由于9/10向下取整为0，相当于这个人根本没发红包。而如果是直接扣除这个人9块钱，再在该group上的每个人的账户上增加平均值的话，就会出现错误。在常人的思维中，这是完全相同的两件事情，毕竟在我们的日常生活中，例如微信红包采用的并不是int类型。但是作为一个程序设计者，在面对确定需求的时候还是应当按照“当地”的规矩办事才好。

容器相关

~HashMap是本次作业的大功臣。由于每个Persoon的id是唯一的，将id设置为key值能够很方便的对数据进行组织和处理；类比Person，message也可以使用相同的方法。

~在容器的使用过程中，有一些地方是需要注意的。

遍历

~foreach遍历是最常用的遍历之一，但是，对于hashmap，如果使用这种方法的对HashMap进行增删改操作就会引发灾难。

~使用迭代器遍历是一个解决这件问题的方法，但是在我的作业中，通过使用一些小技巧（在一个Map进行foreach的遍历时修改其他Map），我并没有使用到迭代器。

~在进行删除操作时，removeif是强力的助手，能够很方便的实现。

~java中的Hashmap提供了许多现成的方法，尤其是在使用idea的时候能够轻松的对这些方法进行应用。

命名

对容器的命名需要进行简单的思考，当然对于变量的命名也是同样的道理。随意的命名会使你在完成程序时写出更多的bug。

图与性能

~图的算法时这次作业的唯一技术性的问题。虽然老师上课笑着对我们说，这一单元的重点是jml而不是算法，但是强测似乎不太同意这一点，遵循着c++老师的一句话，出现性能问题之前不要考虑性能问题，我成功在这次强测中“荣获”0分（虽然上一次也是0分，但是并不是性能的问题）。但没关系啊，下面将对我的图维护进行阐述。

@首先，我在Myperson中设置了一个circle来存储该person所在的连通图中的所有节点。在第10次作业中，我尝试让一个连通图的所有节点共享一个circle。但是在第11次作业中，由于涉及到最短路径的计算，我尝试通过空间换取时间（虽然换性价比不高就是了），每个person维护一个独立的circle，里面存储了该person到所在连通图中所有节点的最短距离。每次进行addRelation操作时，都更新person1和person2的circle中所有成员的circle。这样导致的结果就是，addRelation的复杂度是n方，而寻找最短路径的时间复杂度是1，我自认为这个方法很不错，毕竟在许多地图软件中，用户执行最多的操作就是查询。

@由于addRelation的复杂度太高，在强测中的成绩并不理想。我只能站在前人的肩膀上，使用朴素的Dijkstra算法对我的程序进行优化，这意味着我仍然可像第10次作业那样维护circle。但是朴素的Dijkstra算法也并非优化的极限，事实上，这样优化成功的原因可能只是因为强测数据中的addRelation次数远大于sendInderectMessage的次数而已，在同学的提示下，我了解到可以使用小顶堆对Dijkstra算法进行改造，但是由于我是在无法理解二者结合后的“化学反应”，并没有能够成功实现。

心得体会

~在我看来，正确的jml语言读需求的描述不具有二义性，在程序设计中具有重要的意义。但是，与理解自然语言，理解jml更加困难，而且更显枯燥。所以，在分析需求时，应当先使用自然语言对其进行描述，在通过jml消除其二义性，这样才能够让程序设计变得方便而准确。这次的作业在实现上相对简单，让我能够熟练地运用hashmap对数据进行组织和处理，也让我对图产生了很多思考，有一种温故而知新的感觉。