2019春季学期软件构造Lab5

讲一下这回实验遇到的一堆坑吧。

Git 文件名大小写不敏感

由于checksytle，有几个类名不符合定义要求，如AtomStructureGUI，更改成为AtomStructureGui，commit后，build error。
查看错误，发现是文件名仍然是AtomStructureGUI.java。于是乎，一波测试。。发现git对文件名是大小写不敏感的。

修改git设置：

git config core.ignorecase false

然后，在git中删除原文件，重新添加即可。

文本读取以及解析效率

SocialNetworkCircle读取速度巨慢，一开始以为是读文件的锅。于是乎，一波测试。
测试结果告诉我，文件读入所用的时间基本不会对总时间造成影响，切换其他读入方式结果也差不多。。

PS: 不懂java整这么多io的意义何在。

后面以为是正则的问题，但是我总不能 手写字符串匹配吧。。。

今天突然想起来，我用的Lab2中的Graph`来实现轨道系统中关系的存储的。一看代码。。如下：

@Override
public double set(L source, L target, double weight) {
  Edge<L> tmp = null;
  double w = 0;
  if (weight != 0 && (!vertices.contains(source) || !vertices.contains(target))) {
    /*Add edge.*/
    if (!vertices.contains(source)) {
      vertices.add(source);
    }
    if (!vertices.contains(target)) {
      vertices.add(target);
    }
    edges.add(new Edge<L>(source, target, weight));
  } else {
    /*Find old edge.*/
    for (Edge<L> edge : edges) {
      if (edge.getSource().equals(source) && edge.getTarget().equals(target)) {
        w = edge.getWeight();
        tmp = edge;
        break;
      }
    }
    /*Remove edge.*/
    if (tmp != null) {
      edges.remove(tmp);
    }
    /*Change edge*/
    if (weight != 0) {
      edges.add(new Edge<L>(source, target, weight));
    }
  }
  checkRep();
  return w;
}

@Override
public boolean remove(L vertex) {
  if (!vertices.contains(vertex)) {
    return false;
  }
  Iterator<Edge<L>> iterSet = edges.iterator();
  while (iterSet.hasNext()) {
    Edge<L> cur = iterSet.next();
    if (cur.getSource().equals(vertex) || cur.getTarget().equals(vertex)) {
      iterSet.remove();
    }
  }
  vertices.remove(vertex);
  checkRep();
  return true;
}

加边的时间复杂度是O(m)，m为边的总数。那么总加边时间的复杂度就是O(m²)，这tm得跑到哪年。。
继续审计Graph的源码，发现checkRep，sources以及targets复杂度均很高。

private void checkRep() {
  HashMap<Edge<L>, Boolean> recEdges = new HashMap<>();
  for (Edge<L> edge : edges) {
    assert !recEdges.containsKey(edge);
    recEdges.put(edge, true);
    assert vertices.contains(edge.getTarget()) && vertices.contains(edge.getSource());
  }
}

@Override
public Map<L, Double> sources(L target) {
  Map<L, Double> res = new HashMap<>();
  for (Edge<L> edge : edges) {
    if (edge.getTarget().equals(target)) {
      res.put(edge.getSource(), edge.getWeight());
    }
  }
  checkRep();
  return res;
}

@Override
public Map<L, Double> targets(L source) {
  Map<L, Double> res = new HashMap<>();
  for (Edge<L> edge : edges) {
    if (edge.getSource().equals(source)) {
      res.put(edge.getTarget(), edge.getWeight());
    }
  }
  checkRep();
  return res;
}

基本是全是O(m)复杂度的，导致我BFS建轨道系统的时间复杂度变成了O(n*m)的，其中n为点的数目。

解决思路：

1. 使用HashSet存储边集合，重写Edge的equals和hashCode方法。
2. 注释所有的checkRep
3. 重构加边操作
4. 删除防御性拷贝
5. 用部分空间换取时间效率，如常用的targets操作，考虑用HashMap存储需要的相关信息。