2019春季学期软件构造Lab5

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

Git 文件名大小写不敏感

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

修改git设置:

1
git config core.ignorecase false

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

文本读取以及解析效率

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
@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(m2),这tm得跑到哪年。。
继续审计Graph的源码,发现checkRepsources以及targets复杂度均很高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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存储边集合,重写EdgeequalshashCode方法。
  2. 注释所有的checkRep
  3. 重构加边操作
  4. 删除防御性拷贝
  5. 用部分空间换取时间效率,如常用的targets操作,考虑用HashMap存储需要的相关信息。

2019春季学期软件构造Lab5
https://250.ac.cn/2019/05/30/2019春季学期软件构造Lab5/
Author
惊蛰
Posted on
May 30, 2019
Licensed under