记一次这三个实验给我的一点感受：有的问题可能不在算法上。
什么意思呢，意思是有的问题不要复杂化了，不必要使用什么高级的数据结构或者算法，从问题的开始找原因。
肯定很多同学没有绕这个弯路，因此我作此文意在分享我的一个经历。
问题的缘起
Lab3实验的一部分是读取SocialNetworkCircle（以下简称社交网络）文件并绘制，但是这个社交网络呢有两个特点，一是添加人物必须是成对出现的，也就是说需要以“添加关系”的形式添加人物，二是关系的起点必须已经在图中，不然这个关系就是非法的，因为第二个人无法计算他的level，即无法计算他应该出现在第几级的圈圈中。
那么问题来了，每次给出一对关系的时候，应该如何计算第二个人在图中的level？在Lab3中，我考虑使用广度优先搜索的策略寻找这个人应该在的level，因此设计了如下的addRelation()代码：
/**
* addRelation() 的第一版.
* add a relation between p1 and p2.
*
* @param p1 person 1 as source of a relation
* @param p2 person 2 as target of a relation
* @param weight weight
* @return true
*/
private boolean addRelation(SocialPerson p1, SocialPerson p2, double weight) {
if (p1 == orbit.getCenterObject()) {
// if p1 is the center person
if (!orbit.containsLevel(1)) orbit.addTrack(1, 1);
orbit.addRelation(p2, weight);
if (orbit.containsObject(p2)) {
int level1 = orbit.getLevelByObject(p2);
orbit.addRelation(p1, p2, weight);
int level2 = calculateLevel(p2.getName());
if (level2 < level1) {
// 从旧的位置里移除，加到新的里
changePosition(p2, new Position(level2, level2, Math.abs((int) (random.nextDouble() * 1767) % 360)));
}
} else {
orbit.addToTrack(p2, 1, 1, Math.abs((int) (random.nextDouble() * 1767) % 360));
nameMap.put(p2.getName(), p2);
}
} else if (orbit.containsObject(p1)) {
if (orbit.containsObject(p2)) {
// p1 and p2 both are in the orbit
int level1 = orbit.getLevelByObject(p2);
orbit.addRelation(p1, p2, weight);
int level2 = calculateLevel(p2.getName());
if (level2 < level1) {
// 从旧的位置里移除，加到新的里
changePosition(p2, new Position(level2, level2, Math.abs((int) (random.nextDouble() * 1767) % 360)));
}
} else {
// p2 is firstly be added
orbit.addRelation(p1, p2, weight);
int level = calculateLevel(p2.getName());
if (!orbit.containsLevel(level)) orbit.addTrack(level, level);
orbit.addToTrack(p2, level, level, random.nextDouble() % 360);
nameMap.put(p2.getName(), p2);
}
}
return true;
}
这段代码逻辑上没有明显问题，但是实际运行起来效率非常低，使用JProfiler分析之后发现，大部分的时间都花在了calculateLevel()方法上，那么当时这个方法的实现方式又是怎样的呢？如下：
/**
* calculate which level should the person with name be in.
*
* @param name the person's name you want to calculate the level
* @return level if succeeded find the level, -1 if name does not exist
*/
public int calculateLevel(String name) {
return orbit.getDistance(orbit.getCenterObject().getName(), name);
}
……所以还要看getDistance()的实现，如下：
public int getDistance(String name1, String name2) {
Set<String> visitedSet = new HashSet<>();
// 用列表模拟队列
LinkedList<Record> queue = new LinkedList<>();
Record r1 = new Record(name1);
queue.addLast(r1); // 队列
// 广度优先搜索
while (!queue.isEmpty()) {
Record sourceRecord = queue.pollFirst();
// 遍历当前出队顶点所有的邻接点
assert sourceRecord != null;
Set<String> visitingRow = this.targets(sourceRecord.getPerson()).keySet();
for (String p : visitingRow) {
// 只有在未访问时才进行访问操作
if (!visitedSet.contains(p)) {
visitedSet.add(p); // 标记已访问
// 因为是第一次访问，所以队列中一定没有这个person，新建一个record对象，并设置距离，然后进队
Record newVisited = new Record(p, sourceRecord.getDistance() + 1);
queue.addLast(newVisited);
if (name2.equals(p)) {
// 这个distance就是我们要找的距离，也就是level
return newVisited.getDistance();
}
}
}
}
return -1;
}
可以将这段代码理解成在邻接表上进行的广度优先搜索，这个搜索方法中间有一个步骤，是获得与某一个节点相连的所有节点，在这段代码中就是调用的targets()方法。
不幸的是，在当时的targets()实现中，存在一个巨大的问题，它需要便利每一对关系，也就是在 $O(n)$ 时间内在能完成，更致命的是，关系在不断变多，这个方法花费的时间更是以肉眼可见的速度上涨，再结合上其他操作，这个getDistance()就成了影响程序性能最致命的因素。因此，计算Medium文件需要耗时约4分钟，Larger半个小时都计算不出来。经过我的不准确的测试，平均5秒钟能计算的关系对数不超过1000。
第一次改进
在Lab4中，我偶然发现了targets()方法是多么辣鸡，所以尝试去改进，于是我修改了曾经存储关系的数据结构，从原来的
private Set<ConcreteRelation<E, E>> relations = new HashSet<>();
修改成了
private Map<String, Map<String, Double>> relationMap = new HashMap<>();
（当然还有一些细节上的改进，在此不去赘述。）
这么一修改，targets()方法仅仅需要使用relationMap.get()方法就可以实现原来的所有功能，此时只需要 $O(1)$ 即可完成。在保证calculateLevel()方法相关的其他结构基本不变时，读取并计算同样的Medium文件只需要1秒左右，读取并计算Larger文件仅需要4秒左右，极大地提高了速度。
当然这么还没完，不然怎么对得起我最开头说到的“问题不在算法上”？
第二次改进
在写Lab5的时候，我左思右想，到底要怎么改进广度优先搜索的速度呢……谁知我再一次英语课上一拍脑袋意识到：为什么非要广度优先去计算level？？？
下面为了方便表述，作几个简单的说法上的统一：社交网络中的关系由source（起点）、target（终点）、weight（权重）组成
上面已经提到了，文件什么情况下存在不合法的关系，所以我们要利用文件的合法性啊！它每一行的关系都是预先设计好了的，也就是说每一行的关系都必须保证一点：第一个人已经在图中。所以这个图是一点一点延伸起来的，所以！我们压根不需要用什么广度优先去计算level！只需要用关系起点在图中的level就够了！
举个例子：
SocialTie ::= <TommyWong, LisaWong, 0.98>
SocialTie ::= <TommyWong, TomWong, 0.2>
SocialTie ::= <TomWong, FrankLee, 0.71>
SocialTie ::= <FrankLee, DavidChen, 0.02>
SocialTie ::= <TommyWong, DavidChen, 0.342>
对于这样的几对关系，因为TommyWong是中心人物，在社交网络中，他的level是0，所以在添加LisaWong时，可以立即知道她的level是1，TomWong同样；
我们看第三条关系，添加FrankLee时，因为已经知道TomWong的level是1，所以FrankLee的level必定是2，只需要在关系起点的level上+1就够了。
同理，在添加第4条关系的时候，可以知道DavidChen的level是3，但是添加第5条关系的时候，发现DavidChen的level应该是1，小于之前的3，所以需要进行修改。
经过这么一个思路下来，计算每一个level都只需要在 $O(1)$ 的时间内完成，修改后的addRelation()如下：
/**
* add a relation between p1 and p2.
*
* @param p1 person 1 as source of a relation
* @param p2 person 2 as target of a relation
* @param weight weight
* @return true
* @throws ObjectNotExistException throws when p1 or p2 is not in the orbit
*/
public boolean addRelation(final SocialPerson p1,
final SocialPerson p2,
final double weight)
throws ObjectNotExistException {
if (p1 == orbit.getCenterObject()) {
// p1 is center
if (!orbit.containsLevel(1)) { // make sure level 1 is in the orbit
try {
orbit.addTrack(1, 1);
} catch (TrackDidExistException e) {
e.printStackTrace();
log.info("已存在" + 1 + "号轨道");
}
}
if (orbit.containsObject(p2)) {
// p1是中心，p2已存在
int level1 = orbit.getLevelByObject(p2);
orbit.addRelationWithCenter(p2, weight);
if (level1 != 1) {
// 从旧的位置里移除，加到新的里
changePosition(p2, new Position(1, 1, Math.abs((random.nextInt() * 1767) % 360)));
}
} else {
// p1是中心，p2不存在
try {
// 先添加p2这个人
orbit.addToTrack(p2,
1,
1,
Math.abs((random.nextInt() * 1767) % 360));
nameMap.put(p2.getName(), p2);
} catch (NoSuchLevelOfTrackException e) {
e.printStackTrace();
log.error("仍然尝试向不存在的轨道添加物体");
assert false;
}
}
// add relation with center
// 现在p2一定存在
orbit.addRelationWithCenter(p2, weight);
} else if (orbit.containsObject(p1)) {
// 轨道里有p1
if (orbit.containsObject(p2)) {
// p1 and p2 both are in the orbit
int level1 = orbit.getLevelByObject(p2);
orbit.addRelation(p1, p2, weight);
int level2 = orbit.getLevelByObject(p1) + 1;
if (level2 < level1) {
// 从旧的位置里移除，加到新的里
changePosition(p2,
new Position(level2,
level2,
Math.abs((random.nextInt() * 1767) % 360)));
}
} else {
// p2 is firstly be added
try {
int level2 = orbit.getLevelByObject(p1) + 1;
if (!orbit.containsLevel(level2)) {
orbit.addTrack(level2, level2);
}
orbit.addToTrack(p2, level2, 1, 1);
nameMap.put(p2.getName(), p2);
orbit.addRelation(p1, p2, weight);
} catch (NoSuchLevelOfTrackException e) {
log.info("Dealing with NoSuchLevelOfTrackException...");
if (!orbit.containsLevel(1)) {
log.info("Auto add level 1");
try {
orbit.addTrack(1, 1);
log.info("Successfully auto added track 1");
} catch (TrackDidExistException ignored) {
}
}
} catch (TrackDidExistException ignored) {
}
}
} else {
// 轨道里没p1
throw new PersonNotExistException("名称为" + p1.getName() + "的人物不存在，因其作为起点，所以不能添加关系");
}
return true;
}
(这段代码还包含了Lab5中添加的异常机制)
所以最后的效果如何呢，计算Medium的速度已经超级超级快了（忘记具体多少了），计算Larger需要约0.1秒，计算Lab5提供的超大文件仅需要1秒！
评论区