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

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

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

所謂LINQ排序，便是使用定義在System.Linq.Enumerable類中的幾個(gè)擴(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);

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

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

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

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類的實(shí)現(xiàn)，由于過(guò)于簡(jiǎn)單就省略了吧，貼出來(lái)也只是占用地方而已。有了這個(gè)接口，在排序的時(shí)候我們就可以這樣使用了：

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

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

intArray.OrderBy(i => i);

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

OrderedEnumerable的實(shí)現(xiàn)

無(wú)論是哪個(gè)接口，最終創(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ù)校驗(yàn)    base.source = source;    this.parent = null;    this.keySelector = keySelector;    this.comparer = (comparer != null) ? comparer : ((IComparer) Comparer.Default);    this.descending = descending;}

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

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

不過(guò)，事實(shí)上除了OrderdEnumerable以外也沒(méi)有其他子類了，由于這些都是internal類型，因此我認(rèn)為這樣有些“過(guò)渡設(shè)計(jì)”。根據(jù)我們昨天“人肉反編譯”的結(jié)果，可以得到OrderedEnumerable的完整實(shí)現(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]];        }    }    ...}

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

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

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

LINQ排序的實(shí)現(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方法的作用是返回一個(gè)排好序的下標(biāo)數(shù)組。它會(huì)調(diào)用ComputeKeys抽象方法“事先”進(jìn)行Key（也就是排序依據(jù)）的計(jì)算。然后再使用快速排序來(lái)排序map數(shù)組。在QuickSort中，它使用CompareKeys方法來(lái)獲得“兩個(gè)下標(biāo)”所對(duì)應(yīng)的元素的先后順序。僅此而已，沒(méi)什么特別的。甚至我在這里都不打算分析ComputeKeys和CompareKeys兩個(gè)方法的實(shí)現(xiàn)，因?yàn)樗麄儗?shí)在過(guò)于直接：前者會(huì)把source序列中的元素依次調(diào)用keySelector委托，以此獲得一個(gè)與source對(duì)應(yīng)的TKey數(shù)組，而后者便是根據(jù)傳入的下標(biāo)來(lái)比較TKey數(shù)組中對(duì)應(yīng)的兩個(gè)元素的大小。

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

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

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

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

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

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

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

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

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

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());

在實(shí)際測(cè)試之前我無(wú)法做出判斷，因?yàn)樗鼈兤鋵?shí)各有千秋：

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

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

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

相關(guān)文章

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

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

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