我很久以前偶然发现了这个问题
并想自己尝试一下。在尝试不同的数组大小时,我得到了一些令人惊讶的结果。
这是测试代码。(C#用微软编译器,其他语言我没测试过)
static void Main(string[] args)
{
var rand = new Random();
Time(rand, true, 1000, 100000);
Time(rand, false, 1000, 100000);
Time(rand, true, 1000000, 100);
Time(rand, false, 1000000, 100);
Console.ReadKey(true);
}
static void Time(Random rand, bool sort, int arraysize, int loopsize)
{
var stopwatch = new Stopwatch();
var array = new int[arraysize];
array = Array.ConvertAll(array, _ => (int)(rand.NextDouble() * int.MaxValue));
if (sort)
Array.Sort(array);
stopwatch.Start();
var count = 0;
for (var j = 0; j < loopsize; j++)
for (var i = 0; i < array.Length; i++)
if (array[i] > int.MaxValue / 2)
count++;
stopwatch.Stop();
Console.WriteLine("{0} ticks, {1}ms, sort {2}, arraysize {3}, loopsize {4}",
stopwatch.ElapsedTicks, stopwatch.ElapsedMilliseconds, sort, arraysize, loopsize);
}
这是输出。
614149 ticks, 262ms, sort True, arraysize 1000, loopsize 100000
630096 ticks, 269ms, sort False, arraysize 1000, loopsize 100000
634562 ticks, 271ms, sort True, arraysize 1000000, loopsize 100
1840846 ticks, 787ms, sort False, arraysize 1000000, loopsize 100
在发布与调试模式下,相对结果时间通常是相同的(调试大约慢两倍)。
对我来说,最后两个结果是有道理的。它遵循我上面链接的问题的逻辑,并且由于我假设是分支预测,排序后的运行速度更快。然而,前两个结果让我感到困惑。为什么它们几乎同时出现?另外,为什么它们没有比最后两个快得多?我认为较小的数组会导致它位于更近的缓存中,因此整个事情运行得更快。(循环大小 * 数组大小 = 前两个和后两个之间的常数,因此内部迭代次数相同)