1.5.25 #
解答 #
略微修改 1.5.22 的代码即可。 我电脑上的结果：
Quick-Find
N:1600
平均用时（毫秒）：4
N:6400
平均用时（毫秒）：67 比值：16.75
N:25600
平均用时（毫秒）：1268 比值：18.9253731343284
N:102400
平均用时（毫秒）：20554 比值：16.2097791798107
Quick-Union
N:1600
平均用时（毫秒）：5 比值：0.000243261652233142
N:6400
平均用时（毫秒）：66 比值：13.2
N:25600
平均用时（毫秒）：1067 比值：16.1666666666667
N:102400
平均用时（毫秒）：18637 比值：17.4667291471415
Weighted Quick-Union
N:1600
平均用时（毫秒）：0 比值：0
N:6400
平均用时（毫秒）：2
N:25600
平均用时（毫秒）：12 比值：6
N:102400
平均用时（毫秒）：64 比值：5.33333333333333
代码 #
var n = 40;
var t = 4;
// quick-find
Console.WriteLine("Quick-Find");
long last = 0;
long now;
for (var i = 0; i < t; i++, n *= 2)
{
Console.WriteLine("N:" + n * n);
var connections = RandomGrid.GetConnections(n);
var quickFind = new QuickFindUf(n * n);
now = RunTest(quickFind, connections);
if (last == 0)
{
Console.WriteLine("平均用时（毫秒）：" + now);
last = now;
}
else
{
Console.WriteLine("平均用时（毫秒）：" + now + "\t比值：" + (double)now / last);
last = now;
}
}
// quick-union
Console.WriteLine("Quick-Union");
n = 40;
for (var i = 0; i < t; i++, n *= 2)
{
Console.WriteLine("N:" + n * n);
var connections = RandomGrid.GetConnections(n);
var quickFind = new QuickUnionUf(n * n);
now = RunTest(quickFind, connections);
if (last == 0)
{
Console.WriteLine("平均用时（毫秒）：" + now);
last = now;
}
else
{
Console.WriteLine("平均用时（毫秒）：" + now + "\t比值：" + (double)now / last);
last = now;
}
}
// 加权 quick-union
Console.WriteLine("Weighted Quick-Union");
n = 40;
for (var i = 0; i < t; i++, n *= 2)
{
Console.WriteLine("N:" + n * n);
var connections = RandomGrid.GetConnections(n);
var quickFind = new WeightedQuickUnionUf(n * n);
now = RunTest(quickFind, connections);
if (last == 0)
{
Console.WriteLine("平均用时（毫秒）：" + now);
last = now;
}
else
{
Console.WriteLine("平均用时（毫秒）：" + now + "\t比值：" + (double)now / last);
last = now;
}
}
// 进行若干次随机试验，输出平均 union 次数，返回平均耗时。
static long RunTest(Uf uf, Connection[] connections)
{
var timer = new Stopwatch();
long repeatTime = 3;
timer.Start();
for (var i = 0; i < repeatTime; i++)
{
ErdosRenyi.Count(uf, connections);
}
timer.Stop();
return timer.ElapsedMilliseconds / repeatTime;
}