1.5.24

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

根据上题的代码略作修改即可,路径压缩大概可以快 1/3。

N:10000
加权 quick-find 耗时(毫秒):9
带路径压缩的加权 quick-union 耗时(毫秒):6
比值:1.5

N:20000
加权 quick-find 耗时(毫秒):12
带路径压缩的加权 quick-union 耗时(毫秒):8
比值:1.5

N:40000
加权 quick-find 耗时(毫秒):18
带路径压缩的加权 quick-union 耗时(毫秒):12
比值:1.5

N:80000
加权 quick-find 耗时(毫秒):36
带路径压缩的加权 quick-union 耗时(毫秒):30
比值:1.2

N:160000
加权 quick-find 耗时(毫秒):67
带路径压缩的加权 quick-union 耗时(毫秒):41
比值:1.63414634146341

代码

using System;
using UnionFind;
using System.Diagnostics;

namespace _1._5._24
{
    /*
     * 1.5.24
     * 
     * 适用于 Erdös-Renyi 模型的快速算法。
     * 在练习1.5.23 的测试中增加加权 quick-union 算法和使用路径压缩的加权 quick-union 算法。
     * 你能分辨出这两种算法的区别吗?
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int n = 5000;
            for (int t = 0; t < 5; ++t)
            {
                var input = ErdosRenyi.Generate(n);
                var weightedQuickUnionUF = new WeightedQuickUnionUF(n);
                var weightedQuickUnionPathCompressionUF = new WeightedQuickUnionPathCompressionUF(n);

                Console.WriteLine("N:" + n);

                long weightedQuickUnionTime = RunTest(weightedQuickUnionUF, input);
                long weightedQuickUnionPathCompressionTime = RunTest(weightedQuickUnionPathCompressionUF, input);

                Console.WriteLine("加权 quick-find 耗时(毫秒):" + weightedQuickUnionTime);
                Console.WriteLine("带路径压缩的加权 quick-union 耗时(毫秒):" + weightedQuickUnionPathCompressionTime);
                Console.WriteLine("比值:" + (double)weightedQuickUnionTime / weightedQuickUnionPathCompressionTime);
                Console.WriteLine();

                n *= 2;
            }
        }

        /// <summary>
        /// 进行若干次随机试验,输出平均 union 次数,返回平均耗时。
        /// </summary>
        /// <param name="uf">用于测试的并查集。</param>
        /// <param name="connections">用于测试的输入。</param>
        /// <returns>平均耗时。</returns>
        static long RunTest(UF uf, Connection[] connections)
        {
            Stopwatch timer = new Stopwatch();
            int repeatTime = 5;
            timer.Start();
            for (int i = 0; i < repeatTime; ++i)
            {
                ErdosRenyi.Count(uf, connections);
            }
            timer.Stop();

            return timer.ElapsedMilliseconds / repeatTime;
        }
    }
}

另请参阅

UnionFind 库

上一题 下一题