OO第三单元内容概括是什么？

本文共计1611个文字，预计阅读时间需要7分钟。

OO + 第三单元总结 + 目录 + OO + 第三单元总结 + 规范的阅读与实现心得 + JML的阅读方法 + JML代数 + 测试与JML + 容器的选择 + 算法和性能分析 + 架构分析 + 体会 + 规范的阅读与实现心得JML的阅读方法 + 语法

OO 第三单元总结

目录

• OO 第三单元总结
  • 规格的阅读与实现心得
    • JML的阅读方法
    • JML迭代
  • 测试与JML
  • 容器的选择
  • 算法和性能分析
  • 架构分析
  • 体会感想

规格的阅读与实现心得 JML的阅读方法

1. 语法上， 可以参考课程组的《JML level0手册》， 涵盖了基本的jml关键词和语法，看不明白的话可以多翻翻，类比着就搞懂了

2. 阅读顺序上， 阅读JML可以从一些比较底层的类开始读， 比如Person, Message这种依赖关系比较少的类， 可以先读起来，这样对一个类的功能就可以很快的了解

3. 阅读tips :

   Idea对于JML高亮支持其实很不好（基本没有啊喂）推荐在vscode上装好插件在上面阅读，

还可以对Idea注释调颜色，这样至少看起来清楚一点不会灰糊糊的一团

JML迭代

每次迭代推荐用Idea 鼠标右键的compare with clipboard, 比较一下差异， 同时注意一下一些坑人限制条件比如1111

测试与JML

本单元一开始想试试单元测试的，但咨询了一下学长们，似乎都不太推荐JUNIT, OPENJML等基于JML的测试， 后来经过尝试确实有点麻烦。OpenJml 就是个jml语法检查器（bushi, Junit有点像Verilog的testbench样例还需要自己构造，如果能够有一个可以根据JML直接校验函数的工具就好了

剩下的日子里， 就都在写对拍机了

容器的选择

一些容器和我的选择， 因为一些容器需要O(1)的查询效率， 那么Hashmap是最好的选择

第三次作业中， Message的存储满足的是一个FIFO的规则， 所以用了linkedlist

Exception

private int id; //personId触发了异常 private static int totalExcCnt = 0; private static HashMap<Integer, Integer> excTable = new HashMap<>(); // 触发的personId - 触发的次数

Group

private HashMap<Integer, Person> people = new HashMap<>(); // id - person

Person

private HashMap<Person, Integer> linkage = new HashMap<>(); // 邻居Person - distance private LinkedList<Message> messages = new LinkedList<>(); // Person收到的信息

Network

private HashMap<Integer, Person> people = new HashMap<>(); private HashMap<Integer, Group> groups = new HashMap<>(); private HashMap<Integer, Message> messages = new HashMap<>(); private HashMap<Integer, Integer> emojiHeatMap = new HashMap<>(); // 上述皆为<id, 内容> 的Hashmap, O(1)查找不错的 private HashSet<Edge> edges = new HashSet<>(); // Edge是我自己定义的边类， edges记录了所有的边， kruskal的时候会比较方便 private MyDsu<Person> dsu = new MyDsu<>(); // Dsu是我自己写的优化完全的并查集类， 支持不同模板很好用 算法和性能分析

本单元有一些需要注意算法时间复杂度的点

1. 维护valueSum， ageSum， ageSquareSum

   如果要求ageVar那么为了保证精度与jml一致， 自己推一下就好

   return (timeSum - 2 * ageSum * getAgeMean() + getAgeMean() * getAgeMean() * people.size()) / people.size(); //////////////////////////////////////////////////////////////////// BigInteger part1 = ageSquareSum; BigInteger part2 = (new BigInteger("2")).multiply(ageSum) .multiply(BigInteger.valueOf(getAgeMean())); BigInteger part3 = BigInteger.valueOf(getAgeMean()).multiply(BigInteger.valueOf(getAgeMean())) .multiply(BigInteger.valueOf(people.size())); BigInteger result = (part1.subtract(part2).add(part3)).divide(BigInteger.valueOf(people.size())); return result.intValue();

   需要注意的是：valueSum是将每对关系计算两次，需要在每次加人时valueSum加2 * value。除了在加人删人外，在添加关系时需要遍历所有group维护valueSum。(别忘了哦！)

2. Kruskal算法， 需要提前维护所有的边集， 然后遍历边集找到所有在联通分量的边。这样可以实现O(ElogE)的复杂度， 如果不存储需要用iscircle再查找可能会慢

3. isCircle方法, 要用路径压缩+合并秩优化的并查集， 鉴于网上似乎还没有java版的，我给一个吧嘿嘿

   

import java.util.HashMap; public class MyDsu<T> { private HashMap<T, T> fatherMap = new HashMap<>(); private HashMap<T, Integer> rankMap = new HashMap<>(); public MyDsu() { } public void addElement(T a) { fatherMap.put(a, a); rankMap.put(a, 1); } public T findRoot(T a) { T r = a; while (fatherMap.get(r) != r) { r = fatherMap.get(r); } T i = a; T tmp; while (i != r) { tmp = fatherMap.get(i); fatherMap.put(i, r); i = tmp; } return r; } public void unionSet(T a, T b) { if (a == null || b == null) { return; } T root1 = findRoot(a); T root2 = findRoot(b); if (rankMap.get(root1) == rankMap.get(root2)) { fatherMap.put(root2, root1); //root 1 is fa rankMap.put(root1, rankMap.get(root1) + 1); } else { if (rankMap.get(root1) < rankMap.get(root2)) { fatherMap.put(root1, root2); } else { fatherMap.put(root2, root1); } } } }

4. DeleteColdEmoji

如果是按着jml的逻辑， 先遍历heatmap找到对应待删除的emojiMessage, 那么针对每一个emoji,都要遍历一遍整个messages显然复杂度较大。正常想法就是先遍历messages再遍历heatmap, 那么就可以O(n)解决问题

5. dijkstra算法

   注意可以使用堆优化， 并使用一个内部类node来记录相关节点信息

   public class Dijkstra { public class Node implements Comparable<Node> { private int dis = 0; private int id = 0; public int getDis() { return dis; } public int getId() { return id; } public Node(int id, int dis) { this.dis = dis; this.id = id; } @Override public int compareTo(Node o) { return Integer.compare(this.getDis(), o.getDis()); } } // <id, dis> private HashMap<Integer, Integer> dis = new HashMap<>(); // <id, done> private HashMap<Integer, Boolean> done = new HashMap<>(); // <id, person> private HashMap<Integer, Person> people; private PriorityQueue<Node> queue = new PriorityQueue<>(); public Dijkstra(HashMap<Integer, Person> people) { this.people = people; for (Map.Entry<Integer, Person> personEntry : people.entrySet()) { int id = personEntry.getKey(); dis.put(id, (int) 1e9); done.put(id, false); } } public int run(int fromId, int toId) { //算法本体 } }

架构分析

本单元作业架构很简单的，无需多分析，重要的是阅读jml和采取合适的数据结构和算法来实现。

体会感想

整个单元其实期待还是很高的。但是整个单元学下来， 似乎所有的时间都用在读jml上了， 图论算法也不算难，感谢助教的怜悯，其实希望有个jml直接对接检查代码的说，结果似乎没有，感觉jml的威力瞬间减少了不少。 三次作业难得全满挺不错的，希望下次继续努力！