數組排序方法的性能比較（1）：注意事項及試驗

2019-11-17 03:50:43

字體：大中小

來源：轉載

供稿：網友

昨天有朋友寫了一篇文章，其中比較了List<T>的Sort方法與LINQ中排序方法的性能，而最終得到的結果是“LINQ排序方法性能高于List<T>.Sort方法”。這個結果不禁讓我很疑惑。因為List<T>.Sort方法是改變容器內部元素的順序，而LINQ排序后得到的是一個新的序列。假如兩個排序方法的算法完全一致，LINQ排序也比對方多出元素復制的開銷，為什么性能反而會高？如果LINQ排序的算法/實現更為優秀，那為什么.NET Fx不將List<T>.Sort也一并優化一下呢？于是今天我也對這個問題進行了簡單的試驗。

注意事項
在后面的評論中有人說，List<T>.Sort是“內部排序”，而LINQ排序是“外部排序”。但是根據外部排序的定義，這個說法是不正確的?！巴獠颗判颉笔侵冈谂判蚰繕艘幠Ｌ?，導致主存相對太?。ㄈ鐑却妫┒粔蚍牛坏貌焕猛獠看鎯Γㄈ缬脖P）做一些“過渡”的排序方式。因此，LINQ排序雖然生成了新的序列，但還是內部排序。事實上，從定義中我們也可以很容易推斷出，如果數據規模相同，外部排序的性能一般總是比內部排序要差——不過事實上我們不太好做這樣的比較，因為如果是能夠進行內部排序的情況下，誰會利用麻煩的外部排序呢？

那篇文章中得到的結果是不對的，那么問題究竟出在什么地方呢？在我看來，問題主要出在以下兩點。

首先，原文作者使用了 asp.net作為測試環境。值得注意的是，ASP.NET執行.NET代碼的時候，使用的是IIS進程中托管的CLR，它的配置和直接運行.NET應用程序時不同（不同的CLR托管方式配置很可能不一樣——例如SQL Server里托管的CLR）。例如，ASP.NET中每個線程的調用棧為250K，而直接運行.NET應用程序時這個大小為1M。根據我的經驗（也就是說我無法確切地“證明”這個說法），在ASP.NET中執行此類性能測試得到的結果可能很不穩定。因此，一般我建議使用一個最普通的Console應用程序來進行性能測試。

其次，也是更重要的原因，便是原作者只測試了一次排序的性能。這是性能測試中的大忌諱，因為這么做的話誤差實在太大。例如，會不會在進行某一個方法的測試時，忽然系統起了一個后臺進程進行維護，動用了一部分CPU和內存資源，從而導致測試消耗的時間很冤枉地增加。而且，.NET程序是有一個“預熱”過程的，這導致代碼在第一次執行時需要有一個生成本機代碼的過程（俗稱“預熱”）。這個過程和代碼的執行效率是無關的，因為它無論如何只會產生一次消耗，而代碼是會被執行無數次的。因此，在進行測試的時候，一定要將測試目標反復執行N次，至少要讓執行耗時到達“秒”級別，這樣的結果才有一定參考價值。如果執行時間太少的話測試也可能不準確——要知道“計時器”也是有開銷，也是有誤差的，我們要得到盡量準確的結果。

最后，我強烈建議使用CodeTimer進行計時，因為在它的Initialize方法中會將當前進程及線程的優先級設置到最高，以此減少其他無關因素所造成的干擾。如果可以的話，其實也應該盡量關閉系統中其他應用程序或服務，并且最好可以斷開網絡（也是一個道理）。當然Release編譯也是一定需要的。而且，如果您一定需要使用ASP.NET進行性能測試的話，也千萬記得要在web.config中將<compilation />節點的debug屬性設為false——考慮到原作者忽略了之前犯了很明顯的忌諱，我強烈懷疑這點也沒有滿足。:)

因此，我認為那篇文章中的測試結果是不準確的，參考價值很低。

重新測試
既然如此，我們來重新進行一次試驗吧。不過我現在來比較的是Array.Sort<T>方法與LINQ排序的性能。這么做的主要原因是，由于我們要執行多次排序操作，因此每次都應該使用亂序的序列。但是，每次生成新的序列也會帶來開銷，如果使用List<T>的話，填充元素的開銷會很大，但如果是普通數組的話，就可以用性能很高的Array.Copy方法了：

static T[] CloneArray<T>(T[] source)
{
    var dest = new T[source.Length];
    Array.Copy(source, dest, source.Length);
    return dest;
}從試驗結果上看，數組的復制操作應該并沒有造成顯著影響。還有便是，經過閱讀List<T>.Sort方法的代碼，我們可以發現它只是將實現簡單地委托給Array.Sort<T>方法，因此我們可以認為它們的性能完全一致。

Array.Sort<T>方法其實有兩“類”重載，一類是使用IComparer<T>對象進行比較，而另一類則使用了Comparison<T>這個委托對象進行比較。為此，我們構造一個Int32Comparer類來實現IComparer<int>接口：

PRivate class Int32Comparer : IComparer<int>
{
    #region IComparer<int> Members

    public int Compare(int x, int y)
    {
        return x - y;
    }

    #endregion
}于是，兩“類”重載的測試方法分別為：

static void SortWithCustomComparer(int[] array)
{
    Array.Sort(array, new Int32Comparer());
}

static void SortWithDelegate(int[] array)
{
    Array.Sort(array, (x, y) => x - y);
}但是，我在這里還是再補充一個排序“方法”（原因以后再談）。因為int類型是框架知道該如何比較的類型，因此我們其實也可以這么寫：

static void SortWithDefaultComparer(int[] array)
{
    Array.Sort(array, Comparer<int>.Default);
}最后，參加活動的自然還有LINQ排序：

static void SortWithLinq(int[] array)
{
    var sorted =
        (from i in array
         orderby i
         select i).ToList();
}這里我使用的是ToList方法而不是ToArray方法來生成新序列，這是因為ToList的方法性能更高一些，我還是想盡可能將關注點放在“排序”而不是其他方面。

比較代碼如下：

static void Main(string[] args)
{
    var random = new Random(DateTime.Now.Millisecond);
    var array = Enumerable.Repeat(0, 1000 * 500).Select(_ => random.Next()).ToArray();

    CodeTimer.Initialize();

    CodeTimer.Time("SortWithDefaultComparer", 100,
        () => SortWithDefaultComparer(CloneArray(array)));

    CodeTimer.Time("SortWithCustomComparer", 100,
        () => SortWithCustomComparer(CloneArray(array)));

    CodeTimer.Time("SortWithDelegate", 100,
        () => SortWithDelegate(CloneArray(array)));

    CodeTimer.Time("SortWithLinq", 100,
        () => SortWithLinq(CloneArray(array)));

    Console.ReadLine();
}首先，我們生成一個擁有50萬個隨機元素的數組，以此進行排序方法的性能比較。每次比較的時候我們都使用CloneArray方法來生成一個新的數組。

試驗結果
試驗結果如下：

SortWithDefaultComparer
        Time Elapsed:   7,662ms
        Gen 0:          49
        Gen 1:          49
        Gen 2:          49

SortWithCustomComparer
        Time Elapsed:   13,847ms
        Gen 0:          49
        Gen 1:          49
        Gen 2:          49

SortWithDelegate
        Time Elapsed:   19,625ms
        Gen 0:          49
        Gen 1:          49
        Gen 2:          49

SortWithLinq
        Time Elapsed:   31,785ms
        Gen 0:          99
        Gen 1:          99
        Gen 2:          99從結果上來，四種做法的性能區別還是非常明顯的：使用Comparer<int>.Default進行排序的耗時只有LINQ排序的1/4。有趣的是，從GC次數上來看，LINQ排序也剛好是其他三種的一倍，和“理論值”幾乎完全吻合。

經過測試后發現，其實LINQ排序的性能并不會比Array.Sort<T>要高，甚至還有明顯的劣勢。由于排序算法都已經被用到濫了，而且幾乎已經成為了一個“標準”，因此從算法上來看它們不應該會有那么大的差距。所以，我們這里應該可以得出一個比較靠譜的推測：這幾種排序方法的性能差距，完全是由于具體實現上的細節引起的。

至于其中的原因，我們下次再來進行分析——這些方法的實現，尤其是LINQ排序的實現，似乎還是挺有趣的。

上一篇：數組排序方法的性能比較（2）：Array.Sort實現分析

下一篇：數組排序方法的性能比較（3）：LINQ排序實現分析