上次我們分析了Array.Sort方法的實現(xiàn)方式，并了解到類庫會為一些特例而使用高性能的排序方式——int數(shù)組便是這樣一例，因此從測試結(jié)果上來看其性能特別高。不過從數(shù)據(jù)上看，即便是在普通的情況下，Array.Sort的性能也比LINQ排序要高。不過也有朋友從測試中得出的結(jié)論正好相反，這又是為什么呢？那么現(xiàn)在，我們再來分析一下LINQ排序的實現(xiàn)方式吧，希望這樣可以了解到兩者性能差別的秘密。

只可惜，LINQ排序的代碼在System.Core.dll程序集中，微軟沒有發(fā)布這部分源代碼，我們只得使用.NET Reflector來一探究竟了。

LINQ排序接口的定義、使用及擴(kuò)展

所謂LINQ排序，便是使用定義在System.Linq.Enumerable類中的幾個擴(kuò)展方法，它們是：

public static IOrderedEnumerable OrderBy(    this IEnumerable source, Func keySelector);public static IOrderedEnumerable OrderBy(    this IEnumerable source, Func keySelector, IComparer comparer);public static IOrderedEnumerable OrderByDescending(    this IEnumerable source, Func keySelector);public static IOrderedEnumerable OrderByDescending(    this IEnumerable source, Func keySelector, IComparer comparer);

為了使用時的方便，我往往會補(bǔ)充一些額外的接口，例如：

public static IOrderedEnumerable OrderBy(    this IEnumerable source, Func keySelector, bool decending){    return decending ?        source.OrderByDescending(keySelector) :        source.OrderBy(keySelector);}

這樣在使用時，便可以使用一個布爾值來表示排序的方向（升序或是降序）而不需要從兩個方法之間“手動”選擇一個。此外，構(gòu)造一個IComparer類型也實在有些麻煩，于是我按照Array.Sort的做法重新繼續(xù)擴(kuò)展了一個使用委托對象作為“比較器”的接口：

public static IOrderedEnumerable OrderBy(    this IEnumerable source, Func keySelector, Comparison compare, bool decending){    return decending ?        source.OrderByDescending(keySelector, new FunctorComparer(compare)) :        source.OrderBy(keySelector, new FunctorComparer(compare));}

至于FunctorComparer類的實現(xiàn)，由于過于簡單就省略了吧，貼出來也只是占用地方而已。有了這個接口，在排序的時候我們就可以這樣使用了：

employee.OrderBy(p => p.Manager, (m1, m2) => ... /* 比較邏輯 */, false);

不過，無論是哪個接口、重載還是擴(kuò)展，它的（除this外）的第一個參數(shù)便是keySelector，它的含義便是選擇（select）出排序的“依據(jù)”。這個參數(shù)不可省略（除非您提供擴(kuò)展），因此即便是int數(shù)組這樣的類型，需要排序時也必須指定“自己”為排序依據(jù)：

intArray.OrderBy(i => i);

這也是LINQ排序和Array.Sort的本質(zhì)區(qū)別之一。

OrderedEnumerable的實現(xiàn)

無論是哪個接口，最終創(chuàng)建的都是OrderedEnumerable類型，例如：

public static IOrderedEnumerable OrderBy(    this IEnumerable source, Func keySelector){    return new OrderedEnumerable(source, keySelector, null, false);}

OrderedEnumerable的含義是“根據(jù)TKey排序TElement序列的結(jié)果”，它的構(gòu)造函數(shù)僅僅是保留傳入的參數(shù)：

internal OrderedEnumerable(    IEnumerable source, Func keySelector, IComparer comparer, bool descending){    // 省略參數(shù)校驗    base.source = source;    this.parent = null;    this.keySelector = keySelector;    this.comparer = (comparer != null) ? comparer : ((IComparer) Comparer.Default);    this.descending = descending;}

可見，如果您沒有提供比較器，類庫會自動選用Comparer.Default進(jìn)行比較。這個類會盡可能地尋找可用的比較方式，在“萬不得已”的情況下只得跑出異常。如果您對它的實現(xiàn)感興趣可以自行閱讀代碼——甚至無需使用.NET Reflector。

事實上，在OrderedEnumerable中并沒有提供排序等關(guān)鍵性功能，它只是override了基類的GetEnumerableSorter方法，用于提供一個“排序器”。它的基類是OrderdEnumerable，其含義是“排序TElement序列的結(jié)果”，它并不涉及到“排序方式”，而只是提供了一個抽象方法用于獲得一個“排序器”——沒錯，這就是它的子類，如OrderedEnumerable的職責(zé)了（還記得TKey的含義嗎：“根據(jù)TKey進(jìn)行排序”）。

不過，事實上除了OrderdEnumerable以外也沒有其他子類了，由于這些都是internal類型，因此我認(rèn)為這樣有些“過渡設(shè)計”。根據(jù)我們昨天“人肉反編譯”的結(jié)果，可以得到OrderedEnumerable的完整實現(xiàn)：

internal abstract class OrderedEnumerable : IEnumerable...{    internal IEnumerable source;    internal abstract EnumerableSorter GetEnumerableSorter(EnumerableSorter next);    public IEnumerator GetEnumerator()    {        var buffer = new Buffer(this.source);        if (buffer.count <= 0) yield break;        var sorter = this.GetEnumerableSorter(null);        var map = sorter.Sort(buffer.items, buffer.count);        for (var i = 0; i < buffer.count; i++)        {            yield return buffer.items[map[i]];        }    }    ...}

與我們平時接觸到的排序算法不同，EnumerableSorter的Sort方法并不改變原數(shù)組，它只是生成根據(jù)buffer.items數(shù)組生成一個排序之后的“下標(biāo)序列”——即map數(shù)組。當(dāng)外部需要輸出排序后的序列時，OrderedEnumerable才會根據(jù)map中的下標(biāo)順序，依次輸出buffer.items數(shù)組中的元素。

請注意，到目前為止我們還是沒有接觸到最終的排序?qū)崿F(xiàn)。換句話說，現(xiàn)在我們還是不清楚LINQ排序性能高（或低）的關(guān)鍵。

排序?qū)崿F(xiàn)：EnumerableSorter

LINQ排序的實現(xiàn)關(guān)鍵還是在于EnumerableSorter，我們且看其Sort代碼：

internal abstract class EnumerableSorter{    internal abstract int CompareKeys(int index1, int index2);    internal abstract void ComputeKeys(TElement[] elements, int count);    private void QuickSort(int[] map, int left, int right)    {        ...    }    internal int[] Sort(TElement[] elements, int count)    {        this.ComputeKeys(elements, count);        int[] map = new int[count];        for (int i = 0; i < count; i++)        {            map[i] = i;        }        this.QuickSort(map, 0, count - 1);        return map;    }}

從之前的分析中得知，Sort方法的作用是返回一個排好序的下標(biāo)數(shù)組。它會調(diào)用ComputeKeys抽象方法“事先”進(jìn)行Key（也就是排序依據(jù)）的計算。然后再使用快速排序來排序map數(shù)組。在QuickSort中，它使用CompareKeys方法來獲得“兩個下標(biāo)”所對應(yīng)的元素的先后順序。僅此而已，沒什么特別的。甚至我在這里都不打算分析ComputeKeys和CompareKeys兩個方法的實現(xiàn)，因為他們實在過于直接：前者會把source序列中的元素依次調(diào)用keySelector委托，以此獲得一個與source對應(yīng)的TKey數(shù)組，而后者便是根據(jù)傳入的下標(biāo)來比較TKey數(shù)組中對應(yīng)的兩個元素的大小。

不過，我還是強(qiáng)烈建議您閱讀一下EnumerableSorter及其子類EnumerableSorter的實現(xiàn)，以此了解LINQ to Object是如何優(yōu)雅地支持以下表達(dá)式的：

var sorted = from p in people             orderby p.Age             orderby p.ID descending             select p;

這個表達(dá)式的含義是“將Person序列首先根據(jù)Age屬性進(jìn)行升序排列，如果Age相同則再根據(jù)ID降序排”——類庫在實現(xiàn)時使用了類似于“職責(zé)鏈模式”的做法，頗為美觀。

LINQ排序與Array.Sort的性能比較

如果您仔細(xì)閱讀EnuerableSorter的QuickSort方法，會發(fā)現(xiàn)它使用的快速排序算法并不“標(biāo)準(zhǔn)”。快速排序的性能關(guān)鍵之一是選擇合適的pivot元素，但是QuickSort方法總是選擇最中間的元素——(left + right) / 2。此外，它也沒有在元素小于一定閾值時使用更高效的插入排序。因此，從理論上來說，QuickSort方法使用的快速排序算法，其性能不如Array.Sort。

不過，根據(jù)姜敏兄的測試結(jié)果，LINQ排序的性能超過Array.Sort，這又是怎么回事呢？事實上，雖然姜兄的這個測試存在很大的問題（代碼寫錯了），最后得到的結(jié)論“性能高低和元素類型有關(guān)”的結(jié)論也不確切，但是它也的確能體現(xiàn)一些問題。這個問題事實上已經(jīng)由Ivony...老大解釋過了，不過為了信息完整思維連貫，我在這里再進(jìn)行詳細(xì)說明一下。

從理論上來說，Array.Sort和LINQ排序的時間復(fù)雜度是相同的，因此性能“似乎不會有太大不同”，但是從實驗結(jié)果上看差距還是十分明顯的。因為從實際上看，Array.Sort對于特殊類型有特殊處理，此外LINQ排序會有復(fù)制元素的開銷，因此我之前我認(rèn)為“找不到LINQ排序的性能有優(yōu)勢的理由”。可惜這句話已經(jīng)站不住腳了，我們來觀察一下兩種排序方式在實現(xiàn)上的主要區(qū)別：

• Array.Sort：使用IComparer對象比較兩個元素的大小。
• LINQ排序：首先根據(jù)keySelector獲得TKey序列，然后在排序時使用IComparer比較兩個TKey元素的大小。

那么，以此您是否可以判斷出以下兩個排序方法的性能高低？

public class Person{    public int Age { get; set; }}public class PersonComparer : IComparer<Person>{    public int Compare(Person x, Person y)    {        return x.Age - y.Age;    }}

Person[] people = ...var byLinq = people.OrderBy(p => p.Age).ToList();var byArray = Array.Sort(people, new PersonComparer());

在實際測試之前我無法做出判斷，因為它們其實各有千秋：

• Array.Sort：雖然不需要進(jìn)行額外的元素復(fù)制，但是調(diào)用PersonComparer.Compare方法的開銷較大——訪問Age屬性相當(dāng)于調(diào)用get_Age方法（如果沒有內(nèi)聯(lián)的話）。
• LINQ排序：雖然需要進(jìn)行額外的元素復(fù)制，而且需要事先計算出排序用的鍵值（Age屬性），但是在排序時只需直接比較int即可，效率較高。

這其實也就是某些測試中發(fā)現(xiàn)LINQ排序性能較高的“秘密”。為什么同樣排序Person序列時，我的測試（http://gist.github.com/282796）表明Array.Sort較快，而其他一些朋友卻得到LINQ排序較快的結(jié)果呢？這是因為我的Person類直接使用了公開字段而不是屬性，這樣避免了方法調(diào)用的開銷。此外，另一些朋友的PersonComparer在比較兩個int時使用了x.Age.CompareTo方法——這又比直接進(jìn)行int減法要慢上一些了。

那么，還有影響兩者性能的因素嗎？我們有辦法提高數(shù)組排序的性能嗎？畢竟很多時候我們需要直接排序，而不是生成新的序列。下次我們再來討論這些問題吧。

相關(guān)文章

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

NET技術(shù)：數(shù)組排序方法的性能比較（3）：LINQ排序?qū)崿F(xiàn)分析，轉(zhuǎn)載需保留來源！

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