add java code to compare different path compression implementation in UF.

liuyubobobo · liuyubobobo · commit 38517bcd2bcd · 2017-06-16T10:29:07.000-07:00
diff --git a/06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/Main.java b/06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/Main.java
@@ -2,12 +2,12 @@
 
 public class Main {
 
-    // 对比UF1, UF2, UF3, UF4和UF5的时间性能
+    // 对比UF1, UF2, UF3, UF4, UF5和UF6的时间性能
     // 在这里, 我们对于不同的UnionFind的实现, 使用相同的测试用例, 让测试结果更加准确
     public static void main(String[] args) {
 
-        // 使用1000000的数据规模
-        int n = 1000000;
+        // 使用5000000的数据规模
+        int n = 5000000;
 
         // 生成unionElements的测试用例
         Pair<Integer, Integer>[] unionTest = new Pair[n];
@@ -25,7 +25,7 @@ public static void main(String[] args) {
             connectTest[i] = new Pair<Integer, Integer>(a, b);
         }
 
-        // 测试我们的UF1 ~ UF5
+        // 测试我们的UF1 ~ UF6
 
         // 100万数据对于UF1和UF2来说太慢了, 不再测试
 //        UnionFind1 uf1 = new UnionFind1(n);
@@ -42,5 +42,8 @@ public static void main(String[] args) {
 
         UnionFind5 uf5 = new UnionFind5(n);
         UnionFindTestHelper.testUF("UF5", uf5, unionTest, connectTest);
+
+        UnionFind6 uf6 = new UnionFind6(n);
+        UnionFindTestHelper.testUF("UF6", uf6, unionTest, connectTest);
     }
 }
diff --git a/06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UnionFind5.java b/06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UnionFind5.java
@@ -1,6 +1,6 @@
 package bobo.algo;
 
-// 我们的第五版Union-Find
+// 我们的第五版Union-Find, 路径压缩使用迭代实现
 public class UnionFind5 implements UF {
 
     // rank[i]表示以i为根的集合所表示的树的层数
@@ -34,11 +34,6 @@ private int find(int p){
             p = parent[p];
         }
         return p;
-
-        // path compression 2, 递归算法
-//            if( p != parent[p] )
-//                parent[p] = find( parent[p] );
-//            return parent[p];
     }
 
     // 查看元素p和元素q是否所属一个集合
diff --git a/06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UnionFind6.java b/06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UnionFind6.java
@@ -0,0 +1,66 @@
+package bobo.algo;
+
+// 我们的第六版Union-Find, 路径压缩使用递归实现
+public class UnionFind6 implements UF {
+
+    // rank[i]表示以i为根的集合所表示的树的层数
+    // 在后续的代码中, 我们并不会维护rank的语意, 也就是rank的值在路径压缩的过程中, 有可能不在是树的层数值
+    // 这也是我们的rank不叫height或者depth的原因, 他只是作为比较的一个标准
+    // 关于这个问题，可以参考问答区：http://coding.imooc.com/learn/questiondetail/7287.html
+    private int[] rank;
+    private int[] parent; // parent[i]表示第i个元素所指向的父节点
+    private int count;    // 数据个数
+
+    // 构造函数
+    public UnionFind6(int count){
+        rank = new int[count];
+        parent = new int[count];
+        this.count = count;
+        // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
+        for( int i = 0 ; i < count ; i ++ ){
+            parent[i] = i;
+            rank[i] = 1;
+        }
+    }
+
+    // 查找过程, 查找元素p所对应的集合编号
+    // O(h)复杂度, h为树的高度
+    private int find(int p){
+        assert( p >= 0 && p < count );
+
+        // path compression 2, 递归算法
+        if( p != parent[p] )
+            parent[p] = find( parent[p] );
+        return parent[p];
+    }
+
+    // 查看元素p和元素q是否所属一个集合
+    // O(h)复杂度, h为树的高度
+    public boolean isConnected( int p , int q ){
+        return find(p) == find(q);
+    }
+
+    // 合并元素p和元素q所属的集合
+    // O(h)复杂度, h为树的高度
+    public void unionElements(int p, int q){
+
+        int pRoot = find(p);
+        int qRoot = find(q);
+
+        if( pRoot == qRoot )
+            return;
+
+        // 根据两个元素所在树的元素个数不同判断合并方向
+        // 将元素个数少的集合合并到元素个数多的集合上
+        if( rank[pRoot] < rank[qRoot] ){
+            parent[pRoot] = qRoot;
+        }
+        else if( rank[qRoot] < rank[pRoot]){
+            parent[qRoot] = pRoot;
+        }
+        else{ // rank[pRoot] == rank[qRoot]
+            parent[pRoot] = qRoot;
+            rank[qRoot] += 1;   // 此时, 我维护rank的值
+        }
+    }
+}
diff --git a/06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UnionFindTestHelper.java b/06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UnionFindTestHelper.java
@@ -130,7 +130,32 @@ public static void testUF5( int n ){
         long endTime = System.currentTimeMillis();
 
         // 打印输出对这2n个操作的耗时
-        System.out.println("UF4, " + 2*n + " ops, " + (endTime-startTime) + "ms");
+        System.out.println("UF5, " + 2*n + " ops, " + (endTime-startTime) + "ms");
+    }
+
+    // 测试第六版本的并查集, 测试元素个数为n, 测试逻辑和之前是完全一样的
+    public static void testUF6( int n ){
+
+        UnionFind6 uf = new UnionFind6(n);
+
+        long startTime = System.currentTimeMillis();
+
+        // 进行n次操作, 每次随机选择两个元素进行合并操作
+        for( int i = 0 ; i < n ; i ++ ){
+            int a = (int)(Math.random()*n);
+            int b = (int)(Math.random()*n);
+            uf.unionElements(a,b);
+        }
+        // 再进行n次操作, 每次随机选择两个元素, 查询他们是否同属一个集合
+        for(int i = 0 ; i < n ; i ++ ){
+            int a = (int)(Math.random()*n);
+            int b = (int)(Math.random()*n);
+            uf.isConnected(a,b);
+        }
+        long endTime = System.currentTimeMillis();
+
+        // 打印输出对这2n个操作的耗时
+        System.out.println("UF6, " + 2*n + " ops, " + (endTime-startTime) + "ms");
     }
 
     // 使用相同的测试数据测试UF的执行效率
