~~我来补这学期欠下的坑了~~，比起博客园，里面的文章会更侧重于关于做题的思路，因此有可能直接以最后一次题目来分析了(毕竟迭代开发)，有关面向对象相关的内容，比如类、对象、方法、属性等等或许相对少这一单元来说，这一单元来说，就不说明JML的理解之类了，就是其中一些关键的优化算法，因此和博客园应该是一个子集(?)的关系

基于JML规范语言的社交系统

题目大意

搭建一个模拟社交系统，存在着Person，Group，Network，Message等类,每个类都有着自己的属性和操作，通过JML进行说明

重点优化

基于并查集的qci与qbs

这两个指令，分别是查询两个点是否联通和整张图的连通块个数，如果按照暴力的方法，对两个指令使用DFS或者BFS的话，最差的情况qci的时间复杂度会达到$O(n^2)$, 而qbs的时间复杂度会达到$O(n^3)$，如果qbvs和qci的指令占比高的话，有tle的风险，事实上对于某些DFS或者BFS没有注意砍掉一些搜索分枝的情况下，在互测中确实可以构造出这样的数据使得程序运行超时。于是，我们可以处理并查集的方法进行处理。

并查集，顾名思义，我们将所有关系的点都弄到一个集合里，当两个点要建立联系时，将两个点所处在的集合合并为一个处理。(孤立点的集合可以视为只包含自己的点)。在这次作业中，我采用的是递归找并查集并合并的策略。

具体为，对于每个集合用树形结构进行存储，对于每个点不断向上找其祖先，直到其不存在祖先，对比两个祖先是否相等，若相等则说明这两个点是连通的，不相等说明不连通。合并时，找到祖先并将其中一个树变成另一个树的子树。而这个并查集可以在 addRelation()的时候进行维护。两点已经在一个集合里面就不管了，不再则递归找到其祖先，并进行合并。我所采用的合并策略为将集合中点数少的点连向点数较大的点，这样可以对并查集的层数有一定的限制。其层数决定了其时间复杂度，通过上述方法可以让其时间复杂度再最坏情况下也为$O(logN)$

// UnionSet
public class Community {
    private Community higher;
    private final Person lord;
    private int amount;
  
    Community(Person lord) {
        this.lord = lord;
        this.amount = 1;
        this.higher = null;
    }
  
    public Person getLord() {
        if (this.higher == null) {
            return this.lord;
        } else {
            return this.higher.getLord();
        }
    }
  
    public void setHigher(Community higher) {
        this.higher = higher;
    }
  
    public void setAmount(int amount) {
        this.amount = amount;
    }
  
    public Community getHighest() {
        if (this.higher == null) {
            return this;
        } else {
            return this.higher.getHighest();
        }
    }
  
    public int getAmount() {
        return amount;
    }
  
    @Override
    public boolean equals(Object other) {
        if (other == this) {
            return true;
        }
        if (!(other instanceof Community)) {
            return false;
        }
        Community myCommunity = (Community) other;
        return myCommunity.getLord().equals(this.getLord());
    }
}

而对于后面指令数的增加，利用递归可能会出现爆栈的风险，所以后两次作业我使用了非堆归的方法进行查询和合并。

private Person find(Person person, HashMap<Person, Person> communities) {
    Person temp = person;
    if (!communities.containsKey(temp)) {
        return person;
    }
    while (!communities.get(temp).equals(temp)) {
        temp = communities.get(temp);
    }
    Person updated = person;
    while (!communities.get(updated).equals(updated)) {
        updated = communities.get(updated);
        communities.put(updated, temp);
    }
    return temp;
}

而对于qbs，可以维护一个变量 blockSum，当 addPerson时增加，当 addRelation时，若两点不在一个集合中，blockSum减少，否则不变，这样qbs操作的时间复杂度就变成$O(1)$

// addRelation
if (!c1.equals(c2)) {
    blockCount--;
    // something else
}

// addPerson
people.add(person);
blockCount++;
Community community = new Community(person);
communities.put(person, community);

维护qbvs

如果每次遇到啊一个qbvs就对所有点进行一次遍历，时间复杂度是$O(n^2)$, 显然是存在优化的方法的。注意到当且仅当以下三种情况发生时，Group的Sum of Value才会发现改变

当同一个Group中的两个Person使用了 addRelation操作
当与Group中的一个Person有关系的一个Person也 addToGroup
当与Group中与别的Person存在关系的Person从Group中 delFromGroup

所以我们对于每个Group对象维护一个valueSum属性，记录qbvs的答案，对于每个Person记录一个 allGroups容器，记录他参加的Group，每当 addRelation之后就去遍历 allGroups，如果存在重合就增加 sum,同理，addToGroup时也要做类似的操作。

最小生成树的qlc

最小生成树可以选择Prim或是Kruskal，这里我选择了堆优化的Prim，堆导入优先队列来实现即可。感觉如果是完全图的话，Prim效率应该更优。所谓堆优化，本质也就是用PriorityQueue存着距离，这样就不用每次找最小了。其余就是正常的Prim算法，找最近的点纳入树中，以这个点为中转的点更新距离，直至纳入树的点数达到n个

 public int queryLeastConnection(int id) throws PersonIdNotFoundException {
    if (!people.containsKey(id)) {
        throw new MyPersonIdNotFoundException(id);
    }
    int sum = 0;
    int cnt = 1;
    PriorityQueue<Edge> edges =
            new PriorityQueue<>(Comparator.comparingInt(Edge::getValue));
    HashSet<Person> visited = new HashSet<Person>();
    MyPerson root = (MyPerson) people.get(id);
    // total of the connected dots
    int total = amounts.get(find(root, communities));
    visited.add(root);
    for (Person p : root.getValue().keySet()) {
        edges.add(new Edge(root.queryValue(p), root, p));
    }
    while (cnt < total && edges.size() > 0) {
        Edge e = edges.poll();
        while (e != null && visited.contains(e.getP2())) {
            e = edges.poll();
        }
        if (e == null) {
            break;
        }
        MyPerson person = (MyPerson) (e.getP2());
        visited.add(person);
        sum += e.getValue();
        cnt++;
        for (Person p : person.getValue().keySet()) {
            edges.add(new Edge(person.queryValue(p), person, p));
        }
    }
    return sum;
}

最短路问题

利用堆优化的Dijkstra，Prim和Dijkstra蛮像的，也都是用优先队列进行优化的，就不过多赘述了

public int queryLeastConnection(int id) throws PersonIdNotFoundException {
    if (!people.containsKey(id)) {
        throw new MyPersonIdNotFoundException(id);
    }
    int sum = 0;
    int cnt = 1;
    PriorityQueue<Edge> edges =
            new PriorityQueue<>(Comparator.comparingInt(Edge::getValue));
    HashSet<Person> visited = new HashSet<Person>();
    MyPerson root = (MyPerson) people.get(id);
    // total of the connected dots
    int total = amounts.get(find(root, communities));
    visited.add(root);
    for (Person p : root.getValue().keySet()) {
        edges.add(new Edge(root.queryValue(p), root, p));
    }
    while (cnt < total && edges.size() > 0) {
        Edge e = edges.poll();
        while (e != null && visited.contains(e.getP2())) {
            e = edges.poll();
        }
        if (e == null) {
            break;
        }
        MyPerson person = (MyPerson) (e.getP2());
        visited.add(person);
        sum += e.getValue();
        cnt++;
        for (Person p : person.getValue().keySet()) {
            edges.add(new Edge(person.queryValue(p), person, p));
        }
    }
    return sum;
}

题外

本次练习的重点还是在于自动化测试吧，随机数据生成与找人对拍，可以找到很大的bug，还有就是JUnit的使用，但我还是不太会，如果以后掌握熟练了就填坑。

「OO」 03

基于JML规范语言的社交系统

OO lesson 02

基于JML规范语言的社交系统

题目大意

重点优化

基于并查集的qci与qbs

维护qbvs

最小生成树的qlc

最短路问题

题外

CATALOG