1.5.22

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

解答

平方级别算法在输入加倍后耗时应该增加四倍,线性则是两倍。
下面给出我电脑上的结果,数据量较大时比较明显:

N:16000
quick-find
平均次数:8452
用时:143 比值:4.46875

quick-union
平均次数:7325
用时:202 比值:3.25806451612903

weighted-quick-union
平均次数:6889
用时:1


N:32000
quick-find
平均次数:15747
用时:510 比值:3.56643356643357

quick-union
平均次数:15108
用时:801 比值:3.96534653465347

weighted-quick-union
平均次数:17575
用时:3 比值:3


N:64000
quick-find
平均次数:33116
用时:2069 比值:4.05686274509804

quick-union
平均次数:38608
用时:4635 比值:5.78651685393258

weighted-quick-union
平均次数:34850
用时:6 比值:2

代码

using System;
using System.Diagnostics;
using UnionFind;

namespace _1._5._22
{
    /*
     * 1.5.22
     * 
     * Erdös-Renyi 的倍率实验。
     * 开发一个性能测试用例,
     * 从命令行接受一个 int 值 T 并进行 T 次以下实验:
     * 使用练习 1.5.17 的用例生成随机连接,
     * 和我们的开发用例一样使用 UnionFind 来检查触点的连通性,
     * 不断循环知道所有触点都相互连通。
     * 对于每个 N,打印出 N 值和平均所需的连接数以及前后两次运行时间的比值。
     * 使用你的程序验证正文中的猜想:
     * quick-find 算法和 quick-union 算法的运行时间是平方级别的,
     * 加权 quick-union 算法则接近线性级别。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            long lastTimeQuickFind = 0;
            long lastTimeQuickUnion = 0;
            long lastTimeWeightedQuickUnion = 0;

            long nowTime = 0;
            for (int n = 2000; n < 100000; n *= 2)
            {
                Console.WriteLine("N:" + n);
                QuickFindUF quickFindUF = new QuickFindUF(n);
                QuickUnionUF quickUnionUF = new QuickUnionUF(n);
                WeightedQuickUnionUF weightedQuickUnionUF = new WeightedQuickUnionUF(n);

                // quick-find
                Console.WriteLine("quick-find");
                nowTime = RunTest(quickFindUF);
                if (lastTimeQuickFind == 0)
                {
                    Console.WriteLine("用时:" + nowTime);
                    lastTimeQuickFind = nowTime;
                }
                else
                {
                    Console.WriteLine("用时:" + nowTime + 
                        " 比值:" + (double)nowTime / lastTimeQuickFind);
                    lastTimeQuickFind = nowTime;
                }
                Console.WriteLine();

                // quick-union
                Console.WriteLine("quick-union");
                nowTime = RunTest(quickUnionUF);
                if (lastTimeQuickUnion == 0)
                {
                    Console.WriteLine("用时:" + nowTime);
                    lastTimeQuickUnion = nowTime;
                }
                else
                {
                    Console.WriteLine("用时:" + nowTime + 
                        " 比值:" + (double)nowTime / lastTimeQuickUnion);
                    lastTimeQuickUnion = nowTime;
                }
                Console.WriteLine();

                // weighted-quick-union
                Console.WriteLine("weighted-quick-union");
                nowTime = RunTest(weightedQuickUnionUF);
                if (lastTimeWeightedQuickUnion == 0)
                {
                    Console.WriteLine("用时:" + nowTime);
                    lastTimeWeightedQuickUnion = nowTime;
                }
                else
                {
                    Console.WriteLine("用时:" + nowTime + 
                        " 比值:" + (double)nowTime / lastTimeWeightedQuickUnion);
                    lastTimeWeightedQuickUnion = nowTime;
                }
                Console.WriteLine();

                Console.WriteLine();
            }

        }

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

            return timer.ElapsedMilliseconds / repeatTime;
        }
    }
}

另请参阅

UnionFind 库

上一题 下一题