bug fixed in UF 6 test.

liuyubobobo · liuyubobobo · commit 92ac9532cd31 · 2017-06-16T10:22:28.000-07:00
diff --git a/06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/UnionFind5.h b/06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/UnionFind5.h
@@ -9,7 +9,7 @@
 
 using namespace std;
 
-// 我们的第五版Union-Find
+// 我们的第五版Union-Find, 其中路径压缩使用迭代的方式
 namespace UF5{
 
     class UnionFind{
@@ -52,11 +52,6 @@ namespace UF5{
                 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 (C++)/Optional-01-Same-Cases-Test-for-UF/UnionFind6.h b/06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/UnionFind6.h
@@ -10,7 +10,7 @@
 using namespace std;
 
 // 我们的第六版Union-Find, 路径压缩使用递归的方式
-namespace UF5{
+namespace UF6{
 
     class UnionFind{
 
diff --git a/06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/UnionFindTestHelper.h b/06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/UnionFindTestHelper.h
@@ -12,6 +12,7 @@
 #include "UnionFind3.h"
 #include "UnionFind4.h"
 #include "UnionFind5.h"
+#include "UnionFind6.h"
 
 using namespace std;
 
@@ -138,6 +139,30 @@ namespace UnionFindTestHelper{
         cout<<"UF5, "<<2*n<<" ops, "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
     }
 
+    // 测试第六版本的并查集, 测试元素个数为n
+    void testUF6( int n ){
+
+        srand( time(NULL) );
+        UF6::UnionFind uf = UF6::UnionFind(n);
+
+        time_t startTime = clock();
+
+        for( int i = 0 ; i < n ; i ++ ){
+            int a = rand()%n;
+            int b = rand()%n;
+            uf.unionElements(a,b);
+        }
+        for(int i = 0 ; i < n ; i ++ ){
+            int a = rand()%n;
+            int b = rand()%n;
+            uf.isConnected(a,b);
+        }
+        time_t endTime = clock();
+
+        cout<<"UF6, "<<2*n<<" ops, "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
+    }
+
+
     // 使用相同的测试数据测试UF的执行效率
     template<typename UF>
     void testUF(const string &ufName, UF &uf, const vector<pair<int,int>> &unionTest, const vector<pair<int,int>> &connectTest){
diff --git a/06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/main.cpp b/06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/main.cpp
@@ -4,7 +4,7 @@
 
 using namespace std;
 
-// 对比UF1, UF2, UF3, UF4和UF5的时间性能
+// 对比UF1, UF2, UF3, UF4, UF5和UF6的时间性能
 // 在这里, 我们对于不同的UnionFind的实现, 使用相同的测试用例, 让测试结果更加准确
 int main() {
 
@@ -29,7 +29,7 @@ int main() {
         connectTest.push_back(make_pair(a,b));
     }
 
-    // 测试我们的UF1 ~ UF5
+    // 测试我们的UF1 ~ UF6
 
     // 100万数据对于UF1和UF2来说太慢了, 不再测试
 //    UF1::UnionFind uf1 = UF1::UnionFind(n);
@@ -47,7 +47,7 @@ int main() {
     UF5::UnionFind uf5 = UF5::UnionFind(n);
     UnionFindTestHelper::testUF("UF5", uf5, unionTest, connectTest);
 
-    UF5::UnionFind uf6 = UF5::UnionFind(n);
+    UF6::UnionFind uf6 = UF6::UnionFind(n);
     UnionFindTestHelper::testUF("UF6", uf6, unionTest, connectTest);
 
     return 0;
