1.5.23 #
解答 #
先用速度最快的 WeightedQuickUnionUF 生成一系列连接，
保存后用这些连接进行测试，生成连接的方法见 1.5.17 的解答。
下面给出我电脑上的结果：
N:2000
quick-find 耗时（毫秒）：4
quick-union 耗时（毫秒）：5
比值：0.8
N:4000
quick-find 耗时（毫秒）：19
quick-union 耗时（毫秒）：24
比值：0.791666666666667
N:8000
quick-find 耗时（毫秒）：57
quick-union 耗时（毫秒）：74
比值：0.77027027027027
N:16000
quick-find 耗时（毫秒）：204
quick-union 耗时（毫秒）：307
比值：0.664495114006515
N:32000
quick-find 耗时（毫秒）：1127
quick-union 耗时（毫秒）：1609
比值：0.700435052827843
代码 #
var n = 2000;
for (var t = 0; t < 5; t++)
{
var input = ErdosRenyi.Generate(n);
var quickFind = new QuickFindUf(n);
var quickUnion = new QuickUnionUf(n);
Console.WriteLine("N:" + n);
var quickFindTime = RunTest(quickFind, input);
var quickUnionTime = RunTest(quickUnion, input);
Console.WriteLine("quick-find 耗时（毫秒）：" + quickFindTime);
Console.WriteLine("quick-union 耗时（毫秒）：" + quickUnionTime);
Console.WriteLine("比值：" + (double)quickFindTime / quickUnionTime);
Console.WriteLine();
n *= 2;
}
// 进行若干次随机试验，输出平均 union 次数，返回平均耗时。
static long RunTest(Uf uf, Connection[] connections)
{
var timer = new Stopwatch();
var repeatTime = 5;
timer.Start();
for (var i = 0; i < repeatTime; i++)
{
ErdosRenyi.Count(uf, connections);
}
timer.Stop();
return timer.ElapsedMilliseconds / repeatTime;
}