|
|
上次我們分析了Array.Sort方法的實現方式，并了解到類庫會為一些特例而使用高性能的排序方式——int數組便是這樣一例，因此從測試結果上來看其性能特別高。不過從數據上看，即便是在普通的情況下，Array.Sort的性能也比LINQ排序要高。不過也有朋友從測試中得出的結論正好相反，這又是為什么呢？那么現在，我們再來分析一下LINQ排序的實現方式吧，希望這樣可以了解到兩者性能差別的秘密。
只可惜，LINQ排序的代碼在System.Core.dll程序集中，微軟沒有發布這部分源代碼，我們只得使用.NET Reflector來一探究竟了。
LINQ排序接口的定義、使用及擴展
所謂LINQ排序，便是使用定義在System.Linq.Enumerable類中的幾個擴展方法，它們是：
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);
為了使用時的方便，我往往會補充一些額外的接口，例如：
public static IOrderedEnumerable OrderBy( this IEnumerable source, Func keySelector, bool decending){ return decending ? source.OrderByDescending(keySelector) : source.OrderBy(keySelector);}
這樣在使用時，便可以使用一個布爾值來表示排序的方向（升序或是降序）而不需要從兩個方法之間“手動”選擇一個。此外，構造一個IComparer類型也實在有些麻煩，于是我按照Array.Sort的做法重新繼續擴展了一個使用委托對象作為“比較器”的接口：
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類的實現，由于過于簡單就省略了吧，貼出來也只是占用地方而已。有了這個接口，在排序的時候我們就可以這樣使用了：
employee.OrderBy(p => p.Manager, (m1, m2) => ... /* 比較邏輯 */, false);
不過，無論是哪個接口、重載還是擴展，它的（除this外）的第一個參數便是keySelector，它的含義便是選擇（select）出排序的“依據”。這個參數不可省略（除非您提供擴展），因此即便是int數組這樣的類型，需要排序時也必須指定“自己”為排序依據：
intArray.OrderBy(i => i);
這也是LINQ排序和Array.Sort的本質區別之一。
OrderedEnumerable的實現
無論是哪個接口，最終創建的都是OrderedEnumerable類型，例如：
public static IOrderedEnumerable OrderBy( this IEnumerable source, Func keySelector){ return new OrderedEnumerable(source, keySelector, null, false);}
OrderedEnumerable的含義是“根據TKey排序TElement序列的結果”，它的構造函數僅僅是保留傳入的參數：
internal OrderedEnumerable( IEnumerable source, Func keySelector, IComparer comparer, bool descending){ // 省略參數校驗 base.source = source; this.parent = null; this.keySelector = keySelector; this.comparer = (comparer != null) ? comparer : ((IComparer) Comparer.Default); this.descending = descending;}
可見，如果您沒有提供比較器，類庫會自動選用Comparer.Default進行比較。這個類會盡可能地尋找可用的比較方式，在“萬不得已”的情況下只得跑出異常。如果您對它的實現感興趣可以自行閱讀代碼——甚至無需使用.NET Reflector。
事實上，在OrderedEnumerable中并沒有提供排序等關鍵性功能，它只是override了基類的GetEnumerableSorter方法，用于提供一個“排序器”。它的基類是OrderdEnumerable，其含義是“排序TElement序列的結果”，它并不涉及到“排序方式”，而只是提供了一個抽象方法用于獲得一個“排序器”——沒錯，這就是它的子類，如OrderedEnumerable的職責了（還記得TKey的含義嗎：“根據TKey進行排序”）。
不過，事實上除了OrderdEnumerable以外也沒有其他子類了，由于這些都是internal類型，因此我認為這樣有些“過渡設計”。根據我們昨天“人肉反編譯”的結果，可以得到OrderedEnumerable的完整實現：
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方法并不改變原數組，它只是生成根據buffer.items數組生成一個排序之后的“下標序列”——即map數組。當外部需要輸出排序后的序列時，OrderedEnumerable才會根據map中的下標順序，依次輸出buffer.items數組中的元素。
請注意，到目前為止我們還是沒有接觸到最終的排序實現。換句話說，現在我們還是不清楚LINQ排序性能高（或低）的關鍵。
排序實現：EnumerableSorter
LINQ排序的實現關鍵還是在于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方法的作用是返回一個排好序的下標數組。它會調用ComputeKeys抽象方法“事先”進行Key（也就是排序依據）的計算。然后再使用快速排序來排序map數組。在QuickSort中，它使用CompareKeys方法來獲得“兩個下標”所對應的元素的先后順序。僅此而已，沒什么特別的。甚至我在這里都不打算分析ComputeKeys和CompareKeys兩個方法的實現，因為他們實在過于直接：前者會把source序列中的元素依次調用keySelector委托，以此獲得一個與source對應的TKey數組，而后者便是根據傳入的下標來比較TKey數組中對應的兩個元素的大小。
不過，我還是強烈建議您閱讀一下EnumerableSorter及其子類EnumerableSorter的實現，以此了解LINQ to Object是如何優雅地支持以下表達式的：
var sorted = from p in people orderby p.Age orderby p.ID descending select p;
這個表達式的含義是“將Person序列首先根據Age屬性進行升序排列，如果Age相同則再根據ID降序排”——類庫在實現時使用了類似于“職責鏈模式”的做法，頗為美觀。
LINQ排序與Array.Sort的性能比較
如果您仔細閱讀EnuerableSorter的QuickSort方法，會發現它使用的快速排序算法并不“標準”。快速排序的性能關鍵之一是選擇合適的pivot元素，但是QuickSort方法總是選擇最中間的元素——(left + right) / 2。此外，它也沒有在元素小于一定閾值時使用更高效的插入排序。因此，從理論上來說，QuickSort方法使用的快速排序算法，其性能不如Array.Sort。
不過，根據姜敏兄的測試結果，LINQ排序的性能超過Array.Sort，這又是怎么回事呢？事實上，雖然姜兄的這個測試存在很大的問題（代碼寫錯了），最后得到的結論“性能高低和元素類型有關”的結論也不確切，但是它也的確能體現一些問題。這個問題事實上已經由Ivony...老大解釋過了，不過為了信息完整思維連貫，我在這里再進行詳細說明一下。
從理論上來說，Array.Sort和LINQ排序的時間復雜度是相同的，因此性能“似乎不會有太大不同”，但是從實驗結果上看差距還是十分明顯的。因為從實際上看，Array.Sort對于特殊類型有特殊處理，此外LINQ排序會有復制元素的開銷，因此我之前我認為“找不到LINQ排序的性能有優勢的理由”。可惜這句話已經站不住腳了，我們來觀察一下兩種排序方式在實現上的主要區別：
- Array.Sort：使用IComparer對象比較兩個元素的大小。
- LINQ排序：首先根據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：雖然不需要進行額外的元素復制，但是調用PersonComparer.Compare方法的開銷較大——訪問Age屬性相當于調用get_Age方法（如果沒有內聯的話）。
- LINQ排序：雖然需要進行額外的元素復制，而且需要事先計算出排序用的鍵值（Age屬性），但是在排序時只需直接比較int即可，效率較高。
這其實也就是某些測試中發現LINQ排序性能較高的“秘密”。為什么同樣排序Person序列時，我的測試（http://gist.github.com/282796）表明Array.Sort較快，而其他一些朋友卻得到LINQ排序較快的結果呢？這是因為我的Person類直接使用了公開字段而不是屬性，這樣避免了方法調用的開銷。此外，另一些朋友的PersonComparer在比較兩個int時使用了x.Age.CompareTo方法——這又比直接進行int減法要慢上一些了。
那么，還有影響兩者性能的因素嗎？我們有辦法提高數組排序的性能嗎？畢竟很多時候我們需要直接排序，而不是生成新的序列。下次我們再來討論這些問題吧。
相關文章
NET技術：數組排序方法的性能比較（3）：LINQ排序實現分析，轉載需保留來源！
鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。
