UF2效率非常低

Question

bobo老师，
不知道为什么我的uf2 一直都比uf1慢的多的多，没发现什么问题啊。

public class UnionFind2 {

private int[] parent;
private int count;

public UnionFind2(int count){
    parent = new int[count];
    this.count = count;

    for(int i = 0 ; i <  count ; i ++)
        parent[i] = i;

}

private int find( int p){
    assert p >= 0 && p < count;

    while( p != parent[p])
        p = parent[p];

    return p;
}

public boolean isConnection(int p , int q){
    return find(p) == find(q) ;
}

public void unionElements( int p , int q){

// if( !isConnection( p , q)){
// parent[find(q)] = find§;
// }

    int pRoot = find(p);
    int qRoot = find(q);

    if( pRoot == qRoot)
        return;

    parent[ pRoot ] = qRoot;

}

}

Answer 1

liuyubobobo 2020-04-06 03:32:15

虽然你给出的数据确实比较夸张，但是 UF2 比 UF1 慢也是正常的。链式寻址就会比较慢。从你的 UF1 的时间看，你用的数据量也比较小。数据量越大，算法优化的效果越明显。

不过，课程中介绍的 Point 是，从 UF3 开始，效率肯定会高于 UF1，而且数据量越大，越明显。

如果对自己的实现不放心，可以尝试下载课程的官方代码，在你的环境下运行一下试试看。

继续加油！：）

• 提问者 TrophY #1

  好的明白了，谢谢bobo老师！
  加油加油！