解释我从Orderby的性能测试中获得的以下结果

Question

我已经阅读了其他有关Linq订购功能复杂性的帖子，所以我想知道为什么我进行了以下测试

using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
public class Program
{
    public static void Main()
    {
        double[] avgs = new double[100];
        int tests_per_size = 1000; 
        Random rnd = new Random();
        Stopwatch stpw = new Stopwatch();
        for(int i = 1; i <= avgs.Length; ++i)
        {
            double sum = 0;
            int[] arr = new int[i];
            for(int j = 0; j < tests_per_size; ++j)
            {
                for(int k = 0; k < arr.Length; ++k)
                    arr[k] = rnd.Next(Int32.MinValue, Int32.MaxValue);
                stpw.Start();
                var slist = arr.OrderBy(x => x).ToList();   
                stpw.Stop();
                sum += stpw.ElapsedTicks;
            }
            avgs[i-1] = sum / (double)tests_per_size;
        }
        foreach(var t in avgs)
            Console.WriteLine(t);
    }
}

给了我以下结果

15076,327
17261,652
19528,579
21993,155
24674,83
26927,163
29332,665
32018,45
35143,727
38955,111
43188,589
47605,542
52243,952
57166,918
63454,059
70261,749
75997,727
82249,885
88953,873
96958,163
104520,145
112432,1
120746,806
129694,464
138588,981
148007,988
157616,249
167493,94
177748,543
188904,677
200761,557
212235,986
225877,753
239173,783
252288,474
265901,092
279629,762
294529,835
309429,827
326944,916
343254,802
361306,427
378797,508
395831,364
413546,694
431166,319
449165,652
467562,618
487180,928
505969,021
525013,641
544555,831
564859,752
585357,237
606849,766
628464,581
651009,432
673865,517
697340,663
720709,903
744837,668
769024,863
793921,415
819441,534
845185,441
873421,004
901587,713
928140,083
955403,824
983023,284
1011295,028
1040868,504
1070366,748
1100416,455
1131158,53
1162260,852
1193641,253
1225165,58
1257410,12
1289450,658
1322668,533
1358718,074
1400162,62
1440996,876
1483102,815
1531781,127
1581157,377
1627831,867
1673969,553
1713026,287
1750012,667
1787497,946
1825893,268
1864184,643
1902912,621
1942420,978
1982395,399
2023052,109
2063803,114
2106027,85

请注意，每10个数字大约增加一倍。

Answer 1

好吧，一方面，您永远不会 Restart进行秒表，因此您看到的时间是累积的。如果将Start()调用更改为Restart()，您将获得一些疗养值。

要提出的另一个重要点是，您仅测试最高100尺寸的阵列，这还不足以清楚地看到该算法的渐近行为。

最后，请注意，您不仅要测试OrderBy()：还在测试ToList()。效果不会很大，但是良好的测试应该隔离您真正感兴趣的部分。