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

　　注意事項

　　在后面的評論中有人說，List.Sort是“內部排序”，而LINQ排序是“外部排序”。但是根據(jù)外部排序的定義，這個說法是不正確的。“外部排序”是指在排序目標規(guī)模太大，導致主存相對太?。ㄈ鐑却妫┒粔蚍牛坏貌焕猛獠?a href=/pingce/cunchu/ target=_blank class=infotextkey>存儲（如硬盤）做一些“過渡”的排序方式。因此，LINQ排序雖然生成了新的序列，但還是內部排序。事實上，從定義中我們也可以很容易推斷出，如果數(shù)據(jù)規(guī)模相同，外部排序的性能一般總是比內部排序要差——不過事實上我們不太好做這樣的比較，因為如果是能夠進行內部排序的情況下，誰會利用麻煩的外部排序呢？

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

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

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

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

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

重新測試

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

static T[] CloneArray(T[] source){    var dest = new T[source.Length];    Array.Copy(source, dest, source.Length);    return dest;}

　　從試驗結果上看，數(shù)組的復制操作應該并沒有造成顯著影響。還有便是，經(jīng)過閱讀List.Sort方法的代碼，我們可以發(fā)現(xiàn)它只是將實現(xiàn)簡單地委托給Array.Sort方法，因此我們可以認為它們的性能完全一致。

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

private class Int32Comparer : IComparer<int>{    #region IComparer 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萬個隨機元素的數(shù)組，以此進行排序方法的性能比較。每次比較的時候我們都使用CloneArray方法來生成一個新的數(shù)組。

試驗結果

　　試驗結果如下：

SortWithDefaultComparer        Time Elapsed:   7,662ms        Gen 0:          49        Gen 1:          49        Gen 2:          49SortWithCustomComparer        Time Elapsed:   13,847ms        Gen 0:          49        Gen 1:          49        Gen 2:          49SortWithDelegate        Time Elapsed:   19,625ms        Gen 0:          49        Gen 1:          49        Gen 2:          49SortWithLinq        Time Elapsed:   31,785ms        Gen 0:          99        Gen 1:          99        Gen 2:          99

　　從結果上來，四種做法的性能區(qū)別還是非常明顯的：使用Comparer.Default進行排序的耗時只有LINQ排序的1/4。有趣的是，從GC次數(shù)上來看，LINQ排序也剛好是其他三種的一倍，和“理論值”幾乎完全吻合。

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

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

　　本文代碼：http://gist.github.com/281857

相關文章

1. 數(shù)組排序方法的性能比較（1）：注意事項及試驗
2. 數(shù)組排序方法的性能比較（2）：Array.Sort實現(xiàn)分析
3. 數(shù)組排序方法的性能比較（3）：LINQ排序實現(xiàn)分析

NET技術：數(shù)組排序方法的性能比較（上）：注意事項及試驗，轉載需保留來源！

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。