c++ - 为什么在Windows和Mac OS中运行UnionFind时，运行时会有多种变化？

最近，我参加了有关数据结构的类(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中进行测试时，两个运行时结果几乎相同。我不知道我是否犯错误或操作系统的差异。

最佳答案

首先，您写道:



但是，您的测试程序不仅仅测试并集性能，而且还测试并集查找。

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



在测试程序中，QuickUnion并不总是比QuickFind快。

如果您要执行的find比union多得多，那么

QuickFind效率很高。

如果您执行的union比find多，

QuickUnion 可以使更有效率。

最后，在高树上，QuickUnion数据结构的性能不好。

在测试程序中，树的高度将取决于rand()函数的结果。
这就解释了为什么您的结果在一个系统之间会有所不同。
您应该使用rand()重写测试程序，以使其可重现。

关于c++ - 为什么在Windows和Mac OS中运行UnionFind时，运行时会有多种变化？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43270823/