今天遇到一个有趣的 bug，仅仅移动两行代码的位置，就导致性能有巨大的差异。这种 bug 如果不是亲身经历，估计很难体会到其中的奥妙。由于此种 bug 不会导致错误的结果，所以很难debug。
真是应了古话，上得山多终遇虎。不多写点代码，真的遇不到这种有趣的 bug。
正因为如此，姑写文以记之。
Bug：在 for loop 中 initialize object
下面代码中，for loop 80000+, initialize 一个 bfs 需要同等多次的 for loop.
Note： 谨记能够放在 Loop 外面的代码，尽量放在外面，否则耗费资源，both time and resources.
public int ancestor(int v, int w) {
int ant = -1;
int len = Integer.MAX_VALUE;
//下面两行代码被放到了 for loop 中
BreadthFirstDirectedPaths bfsV = new BreadthFirstDirectedPaths(G, v);
BreadthFirstDirectedPaths bfsW = new BreadthFirstDirectedPaths(G, w);
for(int i = 0; i < G.V(); i++) {
//BreadthFirstDirectedPaths bfsV = new BreadthFirstDirectedPaths(G, v);
BreadthFirstDirectedPaths bfsW = new BreadthFirstDirectedPaths(G, w);
//
if (bfsV.hasPathTo(i) && bfsW.hasPathTo(i)) {
int distV = bfsV.distTo(i);
int distW = bfsW.distTo(i);
int sum = distV + distW;
if(sum < len) {
len = sum;
ant = i;
}
}
}
return ant;
}
Initialize a BreadthFirstDirectedPaths
public BreadthFirstDirectedPaths(Digraph G, int s) {
marked = new boolean[G.V()];
distTo = new int[G.V()];
edgeTo = new int[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = INFINITY;
validateVertex(s);
bfs(G, s);
}
