OrderBy的原碼探索

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

原始碼分析

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

OrderByOrderByDescending都是傳回一個新的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);

回傳的OrderedEnumerable5個參數,後面的三個參數就是這幾個方法的不同之處,我們慢一點在去看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;
}

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

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

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

由上面的程式我們可以觀察到OrderByThenBy的差別就是有沒有傳入之前的SourceOrderedEnumerable,先把這點記起來,現在我們來觀察排序的方式,我們前一章有提到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放在_parentnext,用_parent.GetEnumerableSorter(sorter)取得_parentSorter

所以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、取得KeysComparer完成排序都切得很乾淨,這樣的程式碼看上去真是賞心悅目,而且又學到了很多的技巧,在理解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去相減,所以可以維持原本的排序

結語

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

參考