OO第三单元总结

2022/6/1 23:23:20

本文主要是介绍OO第三单元总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

测试方法

  这一单元课程组鼓励我们使用JUnit进行测试,但是在简单的使用之后,我发现JUnit比较适合自己构造一些边界数据来测试自己的程序是否满足自己的逻辑。他的优点很明显,某个方法如果没有按照自己的预期设想完成相应的功能我们都可以通过测试发现。但是他的缺点也同样明显:如果我对JML的理解有误或者无法构建出足够强的数据,很有可能时测不出来正确数据的。因此,这一单元我采取的测试方法是一方面根据评测机随机生成数据和同学对拍,另一方面构造一些针对性较强的数据进行边界测试。

  在构造时,主要跟据方法的JML描述来对各个public normal_behavior以及public exceptional_behavior构造数据,尤其是构造边界数据来判断是否可以正确的进入相应的逻辑内。

图模型的构建和维护

  对于图的存储,我新建立了Side和Graph的类,内部含有节点(人)以及权值(value)等有关的属性。具体而言,在MyNetWork类里面,Graph使用HashMap储存,由于一些指令的查询需要的是连通图,所以每一个graph代表一个连通图存储在HashMap中。

  在这种背景下,addPerson相当于新增了一个只有一个节点的图,这时需要新建Graph类并存在容器内:

    

  addRelation:我们判断添加关系的双方是否处在同一个连通图中,在没有处于同一个连通图中的时候就将两个person所在的连通图合并。

  至于架构,只需根据课程组的安排实现相应接口。

    

性能问题与解决方法

  在这三次作业中,主要的性能问题相关的指令主要有:计算年龄的均值和方差、计算组内的价值和、两个person是否相连的isCircle指令、包含某个person的连通图对应的最小生成树的价值和、两个person之间的最短路径等。主要的性能问题需要从两个方面来入手:保存数据的容器、查询命令的实现方法或算法。

 容器选择:

  1. HashMap 和 HashSet:这两种容器在查询有关信息时的时间复杂度较低,所以对于大部分的关系以及value等信息,使用这两种容器存储
  2. LinkedList:由于插入的信息要求有序,而且插入的时候是从头部插入,所以我使用了LinkList。
  3. PriorityQueue:此容器是从助教们的博客中挖掘得到,主要用于堆优化的最短路径算法以及堆优化的最小生成树算法。

 算法实现

  1. 通过维护内部属性实现降低时间复杂度的目的:例如对于年龄的均值和方差,在MyGroup内部增加两个属性ageSum和ageSqrsum,用来分别表示年龄的总和以及年龄的平方和。
  2. 使用并查集:由于我们的点或者图是一个一个合并到一起的,所以我们可以使用并查集。同时使用路径压缩可以让时间复杂度进一步降低。
  3. 堆优化的Kruskal算法:用来求对应连通图的最小生成树。使用PriorityQueue可以优化复杂度。
  4. 堆优化的dijsktra算法:用来求最短路径。使用PriorityQueue可以优化复杂度。

扩展NetWork

  新建三个类实现Person接口,以此来管理Advertiser、Producer以及Customer。新建两个类实现Message接口,以此来管理SendProductMessage以及PurchaseMessage的有关信息。

  在这种情形下,NetWork需要新设立以下的方法:生产商生产出产品(addProductMessage),生产商发送产品信息广告给Advertiser(sendAdvertisement),顾客购买产品即(purchaseProduct),顾客查询Advertiser的广告信息确定是否有自己需要的产品(getAdvertisement)。同时为了查询有关产品的销售额以及销售路径,需要新建立查询方法。

  以下是部分操作的JML描述:

 生产出产品: 

/*@ public normal_behavior
  @ requires !(\exists int i; 0 <= i && i < messages.length; messages[i].equals(message)));
  @ assignable messages, countOfProducts;
  @ ensures messages.length == \old(messages.length) + 1;
  @ ensures (\forall int i; 0 <= i && i < \old(messages.length);
  @          (\exists int j; 0 <= j && j < messages.length; messages[j].equals(\old(messages[i]))));
  @ ensures (\exists int i; 0 <= i && i < messages.length; messages[i].equals(message));
  @ ensures countOfProducts.get(products) == \old(countOfProducts.get(products)) + 1;
  @ also
  @ public exceptional_behavior
  @ signals (EqualMessageIdException e) (\exists int i; 0 <= i && i < messages.length;
  @                                     messages[i].equals(message));
  @*/
public void addProductMessage(Product product);

发送信息广告商:
/*@ public normal_behavior
  @ requires containsMessage(id) && countOfProducts.get(product) != 0;
  @ assignable messages, countOfProducts, advertise.advertiserProduct;
  @ ensures !containsMessage(id) && messages.length == \old(messages.length) - 1 &&
  @         (\forall int i; 0 <= i && i < \old(messages.length) && \old(messages[i].getId()) != id;
  @         (\exists int j; 0 <= j && j < messages.length; messages[j].equals(\old(messages[i]))));
  @ ensures advertise.advertiserProduct.contains(products)
  @ ensures (\forall int i; 0 <= i && i < \old(advertise.advertiserProduct.size());
                (\exits int j; 0 <= j && j < advertise.advertiserProduct.size();
                old\(advertise.advertiserProduct.get(i)) == advertise.advertiserProduct.get(j)));
  @ also
  @ public exceptional_behavior
  @ signals (MessageIdNotFoundException e) !containsMessage(id);
  @ signals (ProductNotFoundException e) countOfProducts.get(product) == 0;
 */
 public void sendAdvertisement(Product product, Advertiser advertise)
顾客获取自己广告并根据偏好得出请求:
/*@ public normal_behavior
  @ requires containsMessage(id) && countOfProducts.get(product) != 0 && advertise.advertiserProduct.contains(preference);
  @ assignable nothing;
  @ ensures \result == preference
  @ also
  @ public normal_behavior
  @ requires containsMessage(id) && countOfProducts.get(product) != 0 && !advertise.advertiserProduct.contains(preference);
  @ assignable nothing;
  @ ensures \result == null
  @ also
  @ public exceptional_behavior
  @ signals (MessageIdNotFoundException e) !containsMessage(id);
  @ signals (ProductNotFoundException e) countOfProducts.get(product) == 0;
 */
 public Product getAdvertisement(Product preference, Advertiser advertise)

心得体会

  在这一单元通过学习课程组提供的官方架构让我真正感悟到了一个好架构为我们带来的拓展的便利性。之前尽管学习过一些多态等有关知识,但是实际上在前两个单元虽然我进行过有关架构的设计,但是结果只能说对我差强人意,对他人就是完全看不懂了。在这一单元的学习中,我发现了接口是一个好东西,在团队合作开发中我想面向接口编程中或许也是一个实用的好方法。之后在一些可能出现的种类繁多的对象时,我或许可以借助接口留下对之后要求的扩展性。

  同时,这一单元也让我积攒了一个经验:在错误理解了JML之后修改代码时,一定要确认是否全部将错误的实现修改。第三次作业中由于最开始我将部分的方法输入认为就已经时emoji的Id了,所偶一在删除信息以及抛出异常时发生了错误。本来自测时已经发现,但是还是在删除信息的时候忘记改了。在互测时被刀,这真是一个惨痛的教训啊。

  不得不说,这一单元的思考难度下降了不少,但是在架构方面,我还是要认真的学习啊。



这篇关于OO第三单元总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程