1.5.24 #
解答 #
根据上题的代码略作修改即可，路径压缩大概可以快 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
代码 #
var n = 10000;
for (var t = 0; t < 5; t++)
{
var input = ErdosRenyi.Generate(n);
var weightedQuickUnionUf = new WeightedQuickUnionUf(n);
var weightedQuickUnionPathCompressionUf = new WeightedQuickUnionPathCompressionUf(n);
Console.WriteLine("N:" + n);
var weightedQuickUnionTime = RunTest(weightedQuickUnionUf, input);
var weightedQuickUnionPathCompressionTime = RunTest(weightedQuickUnionPathCompressionUf, input);
Console.WriteLine("加权 quick-find 耗时（毫秒）：" + weightedQuickUnionTime);
Console.WriteLine("带路径压缩的加权 quick-union 耗时（毫秒）：" + weightedQuickUnionPathCompressionTime);
Console.WriteLine("比值：" + (double)weightedQuickUnionTime / weightedQuickUnionPathCompressionTime);
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;
}