Inside or Outside the loop

今天遇到一个有趣的 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);
    }