c++ - 为什么在 Windows 和 Mac OS 中运行 UnionFind 时会存在大量运行时差异？

Question

最近上了Data Structure的类(class)，了解到QuickUnion在连接两个元素时的性能优于QuickFind。但是当我在 GCC，Windows 10 而不是 Mac OS X，老师的机器上测试相同的代码时，我得到了完全不同的运行时结果，但不知道为什么。这是 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];
            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;
}

老师测试QuickUnion可以比QuickFind节省一半的时间，但是我在Windows 10 x64上测试的时候两者的运行结果几乎是一样的。不知道是我操作失误还是操作系统不同导致的。

Answer 1

首先，你写道:

I learned about that the performance of QuickUnion is better than QuickFind when connecting two elements. But when I testing the same code...

但是，您的测试程序不仅测试 union 性能，还测试 union 加查找。

---

其次，这里是QuckUnion和QuickFind的N个元素的增长顺序:

QuickFind:

• find: O(1)
• union: O(N)

QuickUnion:

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

对于您的测试程序，QuickUnion 并不总是比 QuickFind 快。

• 如果您做的find 比union 多得多，QuickFind 就会很高效。
• QuickUnion 可以如果你做更多的union而不是find会更有效率。

---

最后，QuickUnion 数据结构在 tall 树上的表现不佳。

在您的测试程序中，树的高度将取决于 rand() 函数的结果。这就解释了为什么您的结果因一个系统而异。您应该在不使用 rand() 的情况下重写您的测试程序，以使其可重现。