c++ - Why wide variations of runtime exists when running UnionFind in Windows and Mac OS? -

recently attended courses data structure, learned performance of quickunion better quickfind when connecting 2 elements. when testing same code in gcc, windows 10 instead of mac os x, teacher's machine, got entirely different result of runtime didn't know why. here code of quickfind.

#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];             (int = 0; < 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;              (int = 0; < count; i++)                 if (id[i] == pid)                     id[i] = qid;         }     }; }  #endif //inc_03_quick_union_unionfind1_h 

and 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 = 0 ; < count ; ++ )                 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 

then unionfindtesthelper, class can test 2 kinds of data structure:

#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 = 0 ; < n ; ++ ){             int = rand()%n;             int b = rand()%n;             uf.unionelements(a,b);         }         for(int = 0 ; < n ; ++ ){             int = 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 = 0 ; < n ; ++ ){             int = rand()%n;             int b = rand()%n;             uf.unionelements(a,b);         }         for(int = 0 ; < n ; ++ ){             int = 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   

finally main.cpp:

#include <iostream> #include "unionfindtesthelper.h"  using namespace std;   int main() {      int n = 100000;      unionfindtesthelper::testuf1(n);     unionfindtesthelper::testuf2(n);      return 0; } 

teacher tested quickunion can save 1 half of time quickfind, when tested in windows 10 x64 2 runtime results same. don't know whether make mistakes or difference of operating systems lead to.

first, wrote :

i learned performance of quickunion better quickfind when connecting 2 elements. when testing same code...

but, test program not test union performance union plus find.

---

secondly, here order of growth n elements quckunion , quickfind:

quickfind:

• find: o(1)
• union: o(n)

quickunion:

• find: o(tree's height)
• union: o(tree's height)

quickunion not faster quickfind test program.

• quickfind efficient if doing many more find union.
• quickunion can more efficient if more union find.

---

finaly, performance on quickunion data structure not on tall trees.

in test program, tree's height depend on rand() function results. explains why results vary 1 system another. should rewrite test program without rand() in order make reproducible.