面向对象第三单元总结

一、针对规格所采取的设计策略

  本单元的所有设计都是围绕给出的规格来展开的,所以读懂规格、正确理解每条规格的意义,是完成设计的第一步。

  1、“翻译”每一条规格

    JML的语法规则我们已经学习过,所以想要看懂JML规格并不是难事,但我们要做的不只是看懂,而是要理解。

    以第一次作业中Network类getPerson方法举例,其中一条规格如下:

      @ ensures (exists int i; 0 <= i && i < people.length; people[i].getId() == id && 
      @         
esult == people[i]);

    如果直接用我们学过的JML语法解释它,会得到:“在people数组的所有元素中,存在某一个元素,它的getId()方法的返回值等于id,则返回true;否则返回false。”这样的表述虽然严谨,但不仅拗口,也难以直观地理解其含义;如果我们将它翻译成:“people数组中存在id属性值为id的对象,则返回true;否则返回false”,则会更加直观;甚至可以再抽象一些,翻译成:“ID信息值为id的人是否在人群中”。这样的理解方式能让我们快速理解每一条规格所存在的意义,再进一步结合其他的规格,理解整体的含义。

  2、规格的整体理解

    在正确理解每一条规格的基础上,如何将规格的含义相互结合,从整体的角度去考虑,是我们下一步要做的事。

    以第一次作业中Network类queryBlockSum方法举例,规格如下:

    /*@ ensures 
esult == 
      @         (sum int i; 0 <= i && i < people.length && 
      @         (forall int j; 0 <= j && j < i; !isCircle(people[i].getId(), people[j].getId()));
      @         1);
      @*/

    如果只看这个方法的规格,我们要实现它必然会用到isCircle函数;但我们可以先读懂isCircle函数的规格,它的含义是:在不报错的情况下,查询两个人在关系网中是否存在一条路径。从queryBlockSum方法的规格中也能看出,它在调用idCircle函数时不会出现报错的情况,由此一来,queryBlockSum方法的实现就能脱离对isCircle方法的依赖,直接理解为查询关系网中连通分量的个数。

二、基于规格的测试方法

  本单元的作业中规格的存在,为我们提供的测试的基础思路。因为我们的目的就是“正确地实现所有的规格”,所以在规格中的代码其实就可以理解为基础的测试代码。对于一些操作简单的方法,我们可以直接参照规格写测试代码;而对于像queryBlockSum这类考验整体架构设计的方法,需要结合整体设计来针对性地设计测试代码。

三、容器的选择和使用经验

  在前几个单元中我们用的最多的容器大多是ArrayList,因为它实现了大多数基于有序数组的各种常用操作,对于已经熟悉C语言数组的我们来说非常容易上手;但在本单元的作业中,我们容易发现以下特点:1、不管是Person、Group还是Message等类型的对象,都有一个唯一标识自己的属性:id;2、需要容器的地方大多数不需要存储各元素之间的顺序关系。基于以上两点,我们可以以id为索引(key值),使用HashMap来存储数据。因为HashMap的查询操作时间复杂度只有O(1),而整个规格中又存在大量基于id的查询操作,所以本单元的作业笔者个人几乎是清一色地使用了HashMap容器。

四、性能问题分析

  第一次的作业中,笔者在互测中发现了其他人的性能问题:主要是在queryBlockSum方法上,由于此方法调用次数非常大,每次都去遍历的话一定会超时。解决办法也挺简单,使用并查集的结构对连通分量的数量进行缓存即可。

  后两次作业我并没有发现比较突出的性能问题。

原文地址:https://www.cnblogs.com/doconicu/p/14838786.html