在Windows和Mac OS中运行UnionFind时，为什么运行时存在很大差异？

最近我参加了有关数据结构的课程，我了解到QuickUnion在连接两个元素时的性能比QuickFind好。但是，当我在GCC中测试相同的代码时，Windows 10而不是Mac OS X，老师的机器，我得到了完全不同的运行时结果，但不知道为什么。这里是QuickFind的代码。在Windows和Mac OS中运行UnionFind时，为什么运行时存在很大差异？

#ifndef INC_03_QUICK_UNION_UNIONFIND1_H 
#define INC_03_QUICK_UNION_UNIONFIND1_H 

#include <cassert> 

using namespace std; 


namespace UF1 { 

    class UnionFind { 

    private: 
     int *id; 
     int count; 

    public: 
     UnionFind(int n) { 
      count = n; 
      id = new int[n]; 
      for (int i = 0; i < n; i++) 
       id[i] = i; 
     } 

     ~UnionFind() { 
      delete[] id; 
     } 

     int find(int p) { 
      assert(p >= 0 && p < count); 
      return id[p]; 
     } 

     bool isConnected(int p, int q) { 
      return find(p) == find(q); 
     } 

     void unionElements(int p, int q) { 

      int pID = find(p); 
      int qID = find(q); 

      if (pID == qID) 
       return; 

      for (int i = 0; i < count; i++) 
       if (id[i] == pID) 
        id[i] = qID; 
     } 
    }; 
} 

#endif //INC_03_QUICK_UNION_UNIONFIND1_H

而且QuickUnion：

#ifndef INC_03_QUICK_UNION_UNIONFIND2_H 
#define INC_03_QUICK_UNION_UNIONFIND2_H 

#include <cassert> 

using namespace std; 


namespace UF2{ 

    class UnionFind{ 

    private: 
     int* parent; 
     int count; 

    public: 
     UnionFind(int count){ 
      parent = new int[count]; 
      this->count = count; 
      for(int i = 0 ; i < count ; i ++) 
       parent[i] = i; 
     } 

     ~UnionFind(){ 
      delete[] parent; 
     } 

     int find(int p){ 
      assert(p >= 0 && p < count); 
      while(p != parent[p]) 
       p = parent[p]; 
      return p; 
     } 

     bool isConnected(int p , int q){ 
      return find(p) == find(q); 
     } 

     void unionElements(int p, int q){ 

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

      if(pRoot == qRoot) 
       return; 

      parent[pRoot] = qRoot; 
     } 
    }; 
} 

#endif //INC_03_QUICK_UNION_UNIONFIND2_H

然后UnionFindTestHelper，一类可以帮助测试两种数据结构：

#ifndef INC_03_QUICK_UNION_UNIONFINDTESTHELPER_H 
#define INC_03_QUICK_UNION_UNIONFINDTESTHELPER_H 

#include <iostream> 
#include <ctime> 
#include "UnionFind1.h" 
#include "UnionFind2.h" 

using namespace std; 

namespace UnionFindTestHelper{ 

    void testUF1(int n){ 

     srand(time(NULL)); 
     UF1::UnionFind uf = UF1::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<<"UF1, "<<2*n<<" ops, "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl; 
    } 

    void testUF2(int n){ 

     srand(time(NULL)); 
     UF2::UnionFind uf = UF2::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<<"UF2, "<<2*n<<" ops, "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl; 
    } 
} 

#endif //INC_03_QUICK_UNION_UNIONFINDTESTHELPER_H

最后的main.cpp：

#include <iostream> 
#include "UnionFindTestHelper.h" 

using namespace std; 


int main() { 

    int n = 100000; 

    UnionFindTestHelper::testUF1(n); 
    UnionFindTestHelper::testUF2(n); 

    return 0; 
}

老师测试了Qu ckUnion可以比QuickFind节省一半的时间，但是当我在Windows 10 x64中测试时，两个运行时结果几乎相同。我不知道我是否犯了错误或操作系统的差异导致。

来源

2017-04-07 Saeron

首先，你写道：

我了解到了QuickUnion的性能优于快速查找连接两个元素时。但是，当我测试相同的代码 ...

但是，您的测试程序不只测试联盟性能，但联盟加查找。

其次，成长为N个元素为QuckUnion和快速查找的下面的顺序：

快速查找：

find：O（1）

union：O（N ）

QuickUnion：

find：O（树的高度）

union：O（树的高度）

QuickUnion并不总是比快速查找快与你的测试程序。

如果您做的更多find比union快速查找效率更高。
QuickUnion 可以更有效，如果你做更多union比find。

Finaly，对QuickUnion数据结构中的表现并不在高大的树木好。

在您的测试程序中，树的高度取决于rand()函数的结果。这解释了为什么你的结果因系统而异。为了使其具有重现性，您应该重写您的测试程序而不使用rand()。

来源

2017-04-10 13:37:17

在Windows和Mac OS中运行UnionFind时，为什么运行时存在很大差异？

回答

相关问题