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

2019-11-17 03:50:46

字體：大中小

來源：轉載

供稿：網友

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

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

LINQ排序接口的定義、使用及擴展
所謂LINQ排序，便是使用定義在System.Linq.Enumerable類中的幾個擴展方法，它們是：

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer);

public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);

public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer);為了使用時的方便，我往往會補充一些額外的接口，例如：

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, bool decending)
{
    return decending ?
        source.OrderByDescending(keySelector) :
        source.OrderBy(keySelector);
}這樣在使用時，便可以使用一個布爾值來表示排序的方向（升序或是降序）而不需要從兩個方法之間“手動”選擇一個。此外，構造一個IComparer<TKey>類型也實在有些麻煩，于是我按照Array.Sort<T>的做法重新繼續擴展了一個使用委托對象作為“比較器”的接口：

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Comparison<TKey> compare, bool decending)
{
    return decending ?
        source.OrderByDescending(keySelector, new FunctorComparer<TKey>(compare)) :
        source.OrderBy(keySelector, new FunctorComparer<TKey>(compare));
}至于FunctorComparer類的實現，由于過于簡單就省略了吧，貼出來也只是占用地方而已。有了這個接口，在排序的時候我們就可以這樣使用了：

employee.OrderBy(p => p.Manager, (m1, m2) => ... /* 比較邏輯 */, false);不過，無論是哪個接口、重載還是擴展，它的（除this外）的第一個參數便是keySelector，它的含義便是選擇（select）出排序的“依據”。這個參數不可省略（除非您提供擴展），因此即便是int數組這樣的類型，需要排序時也必須指定“自己”為排序依據：

intArray.OrderBy(i => i);這也是LINQ排序和Array.Sort<T>的本質區別之一。

OrderedEnumerable的實現
無論是哪個接口，最終創建的都是OrderedEnumerable<TElement, TKey>類型，例如：

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
    return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false);
}OrderedEnumerable<TElement, TKey>的含義是“根據TKey排序TElement序列的結果”，它的構造函數僅僅是保留傳入的參數：

internal OrderedEnumerable(
    IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending)
{
    // 省略參數校驗

    base.source = source;
    this.parent = null;
    this.keySelector = keySelector;
    this.comparer = (comparer != null) ? comparer : ((IComparer<TKey>) Comparer<TKey>.Default);
    this.descending = descending;
}可見，如果您沒有提供比較器，類庫會自動選用Comparer<TKey>.Default進行比較。這個類會盡可能地尋找可用的比較方式，在“萬不得已”的情況下只得跑出異常。如果您對它的實現感興趣可以自行閱讀代碼——甚至無需使用.NET Reflector。

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

不過，事實上除了OrderdEnumerable<TElement, TKey>以外也沒有其他子類了，由于這些都是internal類型，因此我認為這樣有些“過渡設計”。根據我們昨天“人肉反編譯”的結果，可以得到OrderedEnumerable<TElement>的完整實現：

internal abstract class OrderedEnumerable<TElement> : IEnumerable<TElement>...
{
    internal IEnumerable<TElement> source;

    internal abstract EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next);

    public IEnumerator<TElement> GetEnumerator()
    {
        var buffer = new Buffer<TElement>(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<TElement>才會根據map中的下標順序，依次輸出buffer.items數組中的元素。

請注意，到目前為止我們還是沒有接觸到最終的排序實現。換句話說，現在我們還是不清楚LINQ排序性能高（或低）的關鍵。

排序實現：EnumerableSorter
LINQ排序的實現關鍵還是在于EnumerableSorter<TElement>，我們且看其Sort代碼：

internal abstract class EnumerableSorter<TElement>
{
    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<TElement>及其子類EnumerableSorter<TElement, TKey>的實現，以此了解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<T>的性能比較
如果您仔細閱讀EnuerableSorter的QuickSort方法，會發現它使用的快速排序算法并不“標準”。快速排序的性能關鍵之一是選擇合適的pivot元素，但是QuickSort方法總是選擇最中間的元素——(left + right) / 2。此外，它也沒有在元素小于一定閾值時使用更高效的插入排序。因此，從理論上來說，QuickSort方法使用的快速排序算法，其性能不如Array.Sort<T>。

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

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

Array.Sort<T>：使用IComparer<T>對象比較兩個元素的大小。
LINQ排序：首先根據keySelector獲得TKey序列，然后在排序時使用IComparer<TKey>比較兩個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<T>：雖然不需要進行額外的元素復制，但是調用PersonComparer.Compare方法的開銷較大——訪問Age屬性相當于調用get_Age方法（如果沒有內聯的話——不過從實際結果看的確被內聯了）。
LINQ排序：雖然需要進行額外的元素復制，而且需要事先計算出排序用的鍵值（Age屬性），但是在排序時只需直接比較int即可，效率較高。
這其實也就是某些測試中發現LINQ排序性能較高的“秘密”。為什么同樣排序Person序列時，我的測試（http://gist.github.com/282796）表明Array.Sort<T>較快，而其他一些朋友卻得到LINQ排序較快的結果呢？這是因為我的Person類直接使用了公開字段而不是屬性，這樣避免了方法調用的開銷（因為有內聯，這點應該不是問題）。此外，另一些朋友的PersonComparer在比較兩個int時使用了x.Age.CompareTo方法——這又比直接進行int減法要慢上一些了。

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

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

下一篇：Visual Studio集成開發環境無法啟動調試