OO 第三单元总结

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的威力瞬间减少了不少。 三次作业难得全满挺不错的，希望下次继续努力！

【文章转自韩国站群多ip服务器 http://www.558idc.com/krzq.html处的文章,转载请说明出处】