UF1和UF2的比较

Question

在数据量为10000的时候，UF1的时间是UF2的时间的接近4倍，但是数据量为10000的时候，UF2的时间反而增加了，请问bobo老师这个原因是为什么呢？

        // 查找过程, 查找元素p所对应的集合编号
        int find(int p){
            assert( p>=0 && p<=count );
            return id[p];
        }
        // 查看元素p和元素q是否所属一个集合
        // O(1)复杂度
        bool isConnected(int p,int q){
            return find(p) == find(q);
        }
        // 合并元素p和元素q所属的集合
        // O(n) 复杂度
        void unionSet(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;
            }
        }

        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 unionSet(int p,int q){
            int pRoot = find(p);
            int qRoot = find(q);
            if(pRoot == qRoot)
                return;
            parent[pRoot] = qRoot;
        }

备注：这里我将UF1和UF2的类放在同一个头文件UnionFind中，用不同的命名空间分开，没有像你给的代码一样两个放在不同头文件，后来我尝试将其放在两个头文件，其运行结果和放在一个文件的差不多,应该不是这个原因。

Answer 1

liuyubobobo 2021-07-30 16:14:04

我在我的计算机上得不到 UF2 比 UF1 慢的结论，但是数据量大到一定程度，确实会出现 UF2 的优势变低的情况。我怀疑是因为当数据量达到一定程度，链式存储不断寻址，读取的数据的地址空间跳来跳去，导致的时间消耗增大，而 UF1 O(n) 复杂度的操作在同一地址顺次寻址，时间消耗更低。这不是算法的差异了，而是 CPU 底层优化的差异。

类似我的这篇文章介绍的机制：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247486056&idx=1&sn=bf60187c7c2de2dcc863be33b4a28341&chksm=fd8ca52ecafb2c384524a4b470693ab5f522e323debc9afaf4a2ba27651d5aba1f7d015bd6cd&token=1288480109&lang=zh_CN#rd

感兴趣可以在学习路径压缩以后再比较一下大数据量下，带路径压缩的 UF 和 UF1 的性能关系，应该有改善。

继续加油！：）

• 提问者 Mosea #1

  好的，谢谢老师，刚刚我也看一些其他同学问题，发现也有同学之前遇到和我一样的问题，即使使用的IDE和老师相同，是CLion，尝试了把UnionFind2、UnionFind1、UnionFindTestHelper三个文件全部替换为官方代码，结果仍为数据量比较大的时候，UF2时间更长。

• 提问者 Mosea #2

  bobo老师，我有个想法，UF1和UF2里面的uionelements函数中的if语句是否可以像你的文章 类似我的这篇文章介绍的机制：可以去掉if语句呢？这一样来离真相就更进一步了。

• liuyubobobo 回复 提问者 Mosea #3

  分支条件是构建逻辑必须的一种控制流方式，不是所有的 if 都能被去掉的。我的文章中的 if 之所以能去掉，利用了一个很重要的性质：sum + 0 相当于什么都没有加。我们可以将不满足 if 的结果想办法华为 0。这个方式在 uf 的这个 if 中不适用。

点开查看后面2条评论