深入探索 LINQ

OrderBy的原碼探索

前面我們說到LINQ排序方法有四個OrderBy、OrderByDescending、ThenBy及ThenByDescending， OrderBy及OrderByDescending是設定第一個排序條件，而有沒有Descending是差在是不是遞減排序，LINQ的排序方法都會回傳IOrderedEnumerable型別，只有ThenBy及ThenByDescending接在它們後面才可以下複數個查詢條件，本章會聚焦在方法的原始碼說明上，讓我們來看看裡面施了什麼魔法吧。

原始碼分析

  • Source Code: https://github.com/dotnet/corefx/blob/master/src/System.Linq/src/System/Linq/OrderBy.cs

OrderBy及OrderByDescending都是傳回一個新的IOrderedEnumerable的實作，之間的差別只是在傳入的參數不同，我們以OrderBy講解定義:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source, 
    Func<TSource, TKey> keySelector) 
    => new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false, null);

回傳的OrderedEnumerable有5個參數，後面的三個參數就是這幾個方法的不同之處，我們慢一點在去看OrderedEnumerable的建構子，現在我們先再來觀察ThenBy的定義:

public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey>(
    this IOrderedEnumerable<TSource> source, 
    Func<TSource, TKey> keySelector)
{
    if (source == null)
    {
        throw Error.ArgumentNull(nameof(source));
    }

    return source.CreateOrderedEnumerable(keySelector, null, false);
}

由於ThenBy會接在OrderBy後面，使用OrderBy已經建立好的OrderedEnumerable類別叫用CreateOrderedEnumerable()來更新OrderedEnumerable。

接著我們來找找CreateOrderedEnumerable()做了什麼事情，在OrderedEnumerable.cs中找到下面的定義:

IOrderedEnumerable<TElement> IOrderedEnumerable<TElement>.CreateOrderedEnumerable<TKey>(
    Func<TElement, TKey> keySelector, 
    IComparer<TKey> comparer, 
    bool descending) 
    => new OrderedEnumerable<TElement, TKey>(_source, keySelector, comparer, @descending, this);

咦~這不是就是去新建一個新的OrderedEnumerable嗎? 可是仔細看好像有點不太一樣，我們把目光放在最後一個參數，這裡傳入了this，這裡應該藏了什麼秘密，我們來觀察OrderedEnumerable的建構子吧:

internal OrderedEnumerable(
    IEnumerable<TElement> source, 
    Func<TElement, TKey> keySelector, 
    IComparer<TKey> comparer, 
    bool descending, 
    OrderedEnumerable<TElement> parent)
{
    _source = source ?? throw Error.ArgumentNull(nameof(source));
    _parent = parent;
    _keySelector = keySelector ?? throw Error.ArgumentNull(nameof(keySelector));
    _comparer = comparer ?? Comparer<TKey>.Default;
    _descending = descending;
}

這個建構子有下面這些需注意的點:

  • 跟其他方法一樣會去檢查source跟keySelector是否為空，空的話會回傳ArgumentNull的例外
  • 如果沒有設定comparer會使用default的比較器
  • 是否遞減由參數descending決定
  • 紀錄是誰(parent)new了這個OrderedEnumerable

在這邊我們發現了OrderBy及ThenBy的差別就是ThenBy會傳入this當作parent參數，所以ThenBy的動作會被之前的Source所影響，這也是為什麼只有ThenBy接續增加查詢條件才會有用的原因。

由上面的程式我們可以觀察到OrderBy及ThenBy的差別就是有沒有傳入之前的Source進OrderedEnumerable，先把這點記起來，現在我們來觀察排序的方式，我們前一章有提到OrderBy系列的方法也是延遲執行，代表它排序的時間點是在GetEnumerator()之後，我們先來看GetEnumerator()的定義:

public IEnumerator<TElement> GetEnumerator()
{
    Buffer<TElement> buffer = new Buffer<TElement>(_source);
    if (buffer._count > 0)
    {
        int[] map = SortedMap(buffer);
        for (int i = 0; i < buffer._count; i++)
        {
            yield return buffer._items[map[i]];
        }
    }
}
  • 將_source轉為Buffer
  • 叫用SortedMap()排序元素
  • 用yield依序回傳元素

之前介紹的方法的GetEnumerator()都只是單純的判斷是不是要給一個新的實體及設定_state，而OrderBy卻在GetEnumerator()時就執行完成了。

接下來大家應該都很好奇SortedMap()到底做了什麼吧，在介紹SortedMap()之前得先了解Buffer這個類別，它其實是會將_source轉為Array，它有兩個屬性，一個是陣列型態的_items，另一個是元素總數的_count，下面是參數的代碼片段:

/// <summary>
/// The stored items.
/// </summary>
internal readonly TElement[] _items;

/// <summary>
/// The number of stored items.
/// </summary>
internal readonly int _count;

接著我們來看SortedMap()，它會回傳GetEnumerableSorter().Sort(buffer._items, buffer._count)，這邊會需要分GetEnumerableSorter()及Sort()來說明，我們依序來看，先看GetEnumerableSorter():

private EnumerableSorter<TElement> GetEnumerableSorter() => GetEnumerableSorter(null);
...
internal override EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next)
{
    EnumerableSorter<TElement> sorter = new EnumerableSorter<TElement, TKey>(_keySelector, _comparer, _descending, next);
    if (_parent != null)
    {
        sorter = _parent.GetEnumerableSorter(sorter);
    }

    return sorter;
}

GetEnumerableSorter()會建立一個EnumerableSorter實體，這時如果有使用ThenBy()的話就會有_parent的資料，我們就會將目前的Sorter放在_parent的next，用_parent.GetEnumerableSorter(sorter)取得_parent的Sorter。

所以GetEnumerableSorter()是在取得實體化每個查詢條件的Sorter，並且將第一個(祖先)查詢條件回傳。

接下來解析Sort()，我們上面提到的Buffer的兩個屬性會傳入Sort()中，來看一下Sort()的定義:

internal int[] Sort(TElement[] elements, int count)
{
    int[] map = ComputeMap(elements, count);
    QuickSort(map, 0, count - 1);
    return map;
}

從Sort()這裡只能看到叫用了ComputeMap()取得map陣列，再對陣列做QuickSort()，並看不出它真的做了什麼，所以我們得再往內追，先來看ComputeMap():

private int[] ComputeMap(TElement[] elements, int count)
{
    ComputeKeys(elements, count);
    int[] map = new int[count];
    for (int i = 0; i < map.Length; i++)
    {
        map[i] = i;
    }

    return map;
}

原來map根本就只是初始陣列而已，沒有做任何處理，看來真正做事的是ComputeKeys()，來看一下它吧:

internal override void ComputeKeys(TElement[] elements, int count)
{
    _keys = new TKey[count];
    for (int i = 0; i < count; i++)
    {
        _keys[i] = _keySelector(elements[i]);
    }

    _next?.ComputeKeys(elements, count);
}

終於看到Selector了，這裡是把我們在Selector定的委派方法執行後取得查詢條件，再將條件依目前元素排序放進_keys裡面，後面的查詢條件也會因_next?.ComputeKeys(elements, count)取得它們的Key值。

這裡雖然取得了查詢條件，但是還沒有做排序，所以我們接著就要來解析在Sort()中的QuickSort():

protected override void QuickSort(int[] keys, int lo, int hi) =>
            Array.Sort(keys, lo, hi - lo + 1, Comparer<int>.Create(CompareAnyKeys));

這裡是叫用Array.Sort()做排序，最重要的是比較器的實作，這就是排序的基準:

internal override int CompareAnyKeys(int index1, int index2)
{
    int c = _comparer.Compare(_keys[index1], _keys[index2]);
    if (c == 0)
    {
        if (_next == null)
        {
            return index1 - index2; // ensure stability of sort
        }

        return _next.CompareAnyKeys(index1, index2);
    }

    // -c will result in a negative value for int.MinValue (-int.MinValue == int.MinValue).
    // Flipping keys earlier is more likely to trigger something strange in a comparer,
    // particularly as it comes to the sort being stable.
    return (_descending != (c > 0)) ? 1 : -1;
}
  • 叫用之前設定的比較器做排序
  • 如果目前的排序相同的話，檢查是否有下一個排序條件
  • 有的話則往下一個查詢條件叫用，沒有的話則直接傳回兩個index的相減值，由於剛剛map是按照index排序的，所以一定會是負值，代表它依然會按照原本的順序輸出，所以會是stability of sort
  • 如果有設定_descending，會將comparer的值相反
  • 回傳比較值

到這裡就是整個排序的流程了，可以看到他們將每個步驟都切分，設定Sorter、取得Keys到Comparer完成排序都切得很乾淨，這樣的程式碼看上去真是賞心悅目，而且又學到了很多的技巧，在理解LINQ的過程中又可以增強程式能力，真是太棒了。

測試案例賞析

SourceReverseOfResultNullPassedAsComparer

[Fact]
public void SourceReverseOfResultNullPassedAsComparer()
{
    int?[] source = { 100, 30, 9, 5, 0, -50, -75, null };
    int?[] expected = { null, -75, -50, 0, 5, 9, 30, 100 };

    Assert.Equal(expected, source.OrderBy(e => e, null));
}
  • Comparer傳入null時會使用Default的比較器
  • null的元素會被排在第一個

SameKeysVerifySortStable

[Fact]
public void SameKeysVerifySortStable()
{
    var source = new[]
    {
        new { Name = "Tim", Score = 90 },
        new { Name = "Robert", Score = 90 },
        new { Name = "Prakash", Score = 90 },
        new { Name = "Jim", Score = 90 },
        new { Name = "John", Score = 90 },
        new { Name = "Albert", Score = 90 },
    };
    var expected = new[]
    {
        new { Name = "Tim", Score = 90 },
        new { Name = "Robert", Score = 90 },
        new { Name = "Prakash", Score = 90 },
        new { Name = "Jim", Score = 90 },
        new { Name = "John", Score = 90 },
        new { Name = "Albert", Score = 90 },
    };

    Assert.Equal(expected, source.OrderBy(e => e.Score));
}
  • 測試排序是否為Stable
  • Stable Sort的方式在前面的原碼探索有提到，因為是用原本的index去相減，所以可以維持原本的排序

結語

這裡的排序方法跟前面的方法差別比較大，所以在原始碼分析上花了不少的篇幅，原始碼看得多後面的測試案例看起來就比較平常了，主要都是應證原始碼中分析出來的特性。

參考

← GroupBy的應用 →