深入探索 LINQ

GroupBy的原碼探索

前面一章提到了我們提到了GroupBy的使用方式，LINQ方法提供給我們很多的選擇，讓我們可以在合適的情境下使用這些方法，我們已經會轉動輪子了，現在來看看輪子是怎麼製造出來的吧。

原始碼分析

GroupBy總共有8個公開方法，實作如下面程式碼所示:

#region GroupedEnumerable<TSource, TKey>

public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) =>
    new GroupedEnumerable<TSource, TKey>(source, keySelector, null);

public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer) =>
    new GroupedEnumerable<TSource, TKey>(source, keySelector, comparer);

#endregion GroupedEnumerable<TSource, TKey>

#region GroupedEnumerable<TSource, TKey, TElement>

public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector) =>
    new GroupedEnumerable<TSource, TKey, TElement>(source, keySelector, elementSelector, null);

public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer) =>
    new GroupedEnumerable<TSource, TKey, TElement>(source, keySelector, elementSelector, comparer);

#endregion GroupedEnumerable<TSource, TKey, TElement>

#region GroupedResultEnumerable<TSource, TKey, TResult>

public static IEnumerable<TResult> GroupBy<TSource, TKey, TResult>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TKey, IEnumerable<TSource>, TResult> resultSelector) =>
    new GroupedResultEnumerable<TSource, TKey, TResult>(source, keySelector, resultSelector, null);

public static IEnumerable<TResult> GroupBy<TSource, TKey, TResult>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TKey, IEnumerable<TSource>, TResult> resultSelector, IEqualityComparer<TKey> comparer) =>
    new GroupedResultEnumerable<TSource, TKey, TResult>(source, keySelector, resultSelector, comparer);

#endregion GroupedResultEnumerable<TSource, TKey, TResult>

#region GroupedResultEnumerable<TSource, TKey, TElement, TResult>

public static IEnumerable<TResult> GroupBy<TSource, TKey, TElement, TResult>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, Func<TKey,IEnumerable<TElement>, TResult> resultSelector) =>
    new GroupedResultEnumerable<TSource, TKey, TElement, TResult>(source, keySelector, elementSelector, resultSelector, null);

public static IEnumerable<TResult> GroupBy<TSource, TKey, TElement, TResult>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, Func<TKey,IEnumerable<TElement>, TResult> resultSelector, IEqualityComparer<TKey> comparer) =>
    new GroupedResultEnumerable<TSource, TKey, TElement, TResult>(source, keySelector, elementSelector, resultSelector, comparer);

#endregion GroupedResultEnumerable<TSource, TKey, TElement, TResult>

我已經有用#region做了一些整理，它們其實只是分別new出四個不同但是相似的類別，列在下面的是它們的名字及建構子的參數:

  • GroupedEnumerable<TSource, TKey>
    1. IEnumerable<TSource> source: 欲做分組的資料來源
    2. Func<TSource, TKey> keySelector: 分組的鍵值
    3. IEqualityComparer<TKey> comparer: 比較鍵值是否相同的等值比較器
  • GroupedEnumerable<TSource, TKey, TElement>
    1. IEnumerable<TSource> source: 欲做分組的資料來源
    2. Func<TSource, TKey> keySelector: 分組的鍵值
    3. Func<TSource, TElement> elementSelector: 每個元素的輸出資料
    4. IEqualityComparer<TKey> comparer: 比較鍵值是否相同的等值比較器
  • GroupedResultEnumerable<TSource, TKey, TResult>
    1. IEnumerable<TSource> source: 欲做分組的資料來源
    2. Func<TSource, TKey> keySelector: 分組的鍵值
    3. Func<TKey, IEnumerable<TSource>, TResult> resultSelector: 每個組別的輸出資料
    4. IEqualityComparer<TKey> comparer: 比較鍵值是否相同的等值比較器
  • GroupedResultEnumerable<TSource, TKey, TElement, TResult>
    1. IEnumerable<TSource> source: 欲做分組的資料來源
    2. Func<TSource, TKey> keySelector: 分組的鍵值
    3. Func<TSource, TElement> elementSelector: 每個元素的輸出給resultSelector的資料
    4. Func<TKey, IEnumerable<TElement>, TResult> resultSelector: 每個組別的輸出資料
    5. IEqualityComparer<TKey> comparer: 比較鍵值是否相同的等值比較器

這裡我盡量清楚的表示每個方法的差異:

  • 斜體字代表上面一組有的參數，
  • 粗體字表示這個類別多的參數

看了這麼多的類別，看的都眼花撩亂了，但是其實它們都是很相似的類別，因此我們就挑一個最複雜的GroupedResultEnumerable<TSource, TKey, TElement, TResult>來看吧。

GroupedResultEnumerable<TSource, TKey, TElement, TResult>

此類別目標如下:

將資料來源(source)用比較器(comparer)將鍵值(keySelector)分組，再將分組的每個元素用elementSelector取得資料丟到resultSelector中輸出結果。

知道這個類別要做什麼之後，我們先從建構子看起，實作如下:

public GroupedResultEnumerable(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, Func<TKey, IEnumerable<TElement>, TResult> resultSelector, IEqualityComparer<TKey> comparer)
{
    _source = source ?? throw Error.ArgumentNull(nameof(source));
    _keySelector = keySelector ?? throw Error.ArgumentNull(nameof(keySelector));
    _elementSelector = elementSelector ?? throw Error.ArgumentNull(nameof(elementSelector));
    _comparer = comparer;
    _resultSelector = resultSelector ?? throw Error.ArgumentNull(nameof(resultSelector));
}
  • 判斷傳入參數(source、keySelector、elementSelector、resultSelector)是否為空，空的話拋出ArgumentNull例外

建構子就是單純的檢查參數是否合法，接著我們要來看什麼方法相信大家應該猜到了，沒錯，就是當你看到Enumerable時就會想到的GetEnumerator():

public IEnumerator<TResult> GetEnumerator()
{
    Lookup<TKey, TElement> lookup = Lookup<TKey, TElement>.Create(_source, _keySelector, _elementSelector, _comparer);
    return lookup.ApplyResultSelector(_resultSelector).GetEnumerator();
}

在GetEnumerator()中我們可以看到它去Create了一個Lookup的實體，看來得把GroupedResultEnumerable先擺在一邊了，我們先來看看Lookup到底做了什麼吧。

Lookup<TKey, TElement>

首先來看剛剛GroupedResultEnumerable叫用的Create方法:

internal static Lookup<TKey, TElement> Create<TSource>(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Func<TSource, TElement> elementSelector, IEqualityComparer<TKey> comparer)
{
    Debug.Assert(source != null);
    Debug.Assert(keySelector != null);
    Debug.Assert(elementSelector != null);

    Lookup<TKey, TElement> lookup = new Lookup<TKey, TElement>(comparer);
    foreach (TSource item in source)
    {
        lookup.GetGrouping(keySelector(item), create: true).Add(elementSelector(item));
    }

    return lookup;
}

這個Create方法有幾個看點:

  1. 新建了一個Lookup的實體
    • 如果沒有設定comparer的話，用預設(Default)的比較器
    • 新建存放Grouping的陣列，預設大小為7
private Lookup(IEqualityComparer<TKey> comparer)
{
    _comparer = comparer ?? EqualityComparer<TKey>.Default;
    _groupings = new Grouping<TKey, TElement>[7];
}
  1. 對source集合中每一個元素做兩個階段的處理
    1. 取得此元素所在的組別
    2. 將此元素的資料加到上一階段取得的組別中
  2. 傳回已分好組的lookup

上述這幾個步驟最重要的就是第二步了，我們來看一下第二步的兩個階段到底做了什麼，先來看GetGrouping是如何取得此元素所在的組別的。

在看這段程式碼前我們先回想一下GroupBy回傳的是什麼? 是一個Grouping的集合，每個Grouping內有一個鍵值及其對應的元素組合，在GetGrouping中就是要找出目前巡覽到的元素鍵值所在的Grouping。

知道了GetGrouping目的後，我們來看一下他的定義:

internal Grouping<TKey, TElement> GetGrouping(TKey key, bool create)

GetGrouping這裡我們分兩個部份說，可以看到GetGrouping有兩個參數，第二個參數的create是在Lookup<TKey, TElement>.Create()時才會設為true，這也就是說GetGrouping本身有兩個執行邏輯:

  1. 兩種執行邏輯都會先取得傳入鍵值的HashCode
    1. 叫用InternalGetHashCode()取得鍵值HashCode
    2. 叫用客製的比較器(_comparer)做取得HashCode的處理(如果客製比較器沒有設定是使用Default比較器)
private int InternalGetHashCode(TKey key)
{
    // Handle comparer implementations that throw when passed null
    return (key == null) ? 0 : _comparer.GetHashCode(key) & 0x7FFFFFFF; // 1.ii
}
...
internal Grouping<TKey, TElement> GetGrouping(TKey key, bool create)
{
    int hashCode = InternalGetHashCode(key);    // 1.i
    ...
}
  1. create==false: 取得目前_groupings中相同鍵值的grouping回傳，如果在_groupings中找不到相同鍵值的grouping就回傳null
    1. 比對是否已有相同鍵值的grouping存在
    2. 比對方式: 先比對hashCode，hashCode相同再用Equals比對
    3. 有相同鍵值的grouping則回傳此grouping
    4. 沒有的話則傳回null
internal Grouping<TKey, TElement> GetGrouping(TKey key, bool create)
{
    ...
    for (Grouping<TKey, TElement> g = _groupings[hashCode % _groupings.Length]; g != null; g = g._hashNext) // 2.i
    {
        if (g._hashCode == hashCode && _comparer.Equals(g._key, key))   // 2.ii
        {
            // 2.iii
            return g;
        }
    }
    ...
    return null;    // 2.iv
}
  1. create==true: 在新增模式下如果第二步沒有找到相應的grouping的話，則新增一個
    1. 判斷是否為新增模式
    2. 新增此鍵值的Grouping
    3. 加進_groupings中，讓之後的查找找得到
    4. 回傳grouping
internal Grouping<TKey, TElement> GetGrouping(TKey key, bool create)
{
    ...
    if (create) // 3.i
    {
        if (_count == _groupings.Length)
        {
            Resize();
        }

        int index = hashCode % _groupings.Length;
        Grouping<TKey, TElement> g = new Grouping<TKey, TElement>();    // 3.ii
        g._key = key;
        g._hashCode = hashCode;
        g._elements = new TElement[1];
        g._hashNext = _groupings[index];
        _groupings[index] = g;  // 3.iii
        if (_lastGrouping == null)
        {
            g._next = g;
        }
        else
        {
            g._next = _lastGrouping._next;
            _lastGrouping._next = g;
        }

        _lastGrouping = g;
        _count++;
        return g;   // 3.iv
    }
    ...
}

這裡我們會發現index的取法是hashCode % _groupings.Length，還記得剛剛_groupings的預設大小是7嗎? 這裡它利用hashCode對陣列長度的餘數來放進對應的位置裡，這樣我就不用new一個很大的陣列來存放各個HashCode的Grouping，也不用說每次都要全部查找才能找到對應的Grouping，是一個解決的好方法。

執行完GetGrouping()後我們得到了一個Grouping的物件，這裡面可能已經有元素，因為之前的元素可能跟目前的元素有相同的鍵值，接下來要把目前的元素加到這個Grouping裡面，所以叫用了Grouping的Add方法。

現在Lookup.Create()的工作完成了，它把每個元素放進了它該待的Grouping中，然後傳回給GroupedResultEnumerable。

還記得上面有說GroupedResultEnumerable是四種Enumerable中最複雜的嗎? 其實介紹到這裡，我們已經把另一個叫GroupedEnumerable的類別要做的事給說完了，因為GroupedEnumerable比GroupedResultEnumerable少了彙整組內資料的處理，所以GroupedEnumerable其實在分完Grouping後就已經完成了，那就在這裡先來看看GetEnumerator()是怎麼處理分組資料的:

public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator()
{
    Grouping<TKey, TElement> g = _lastGrouping;
    if (g != null)
    {
        do
        {
            g = g._next;
            yield return g;
        }
        while (g != _lastGrouping);
    }
}
  • 迴圈將串列中的所有Grouping巡覽
  • 每個Grouping都yield return

這裡很單純地用yield傳回每個Grouping的資料。

接著我們要講講GroupedResultEnumerable彙整組內資料的處理:

public IEnumerator<TResult> GetEnumerator()
{
    // 1. 將元素擺到對應鍵值的Grouping中
    Lookup<TKey, TElement> lookup = Lookup<TKey, TElement>.Create(_source, _keySelector, _elementSelector, _comparer);
    // 2. 彙整組內資料
    return lookup.ApplyResultSelector(_resultSelector).GetEnumerator();
}

從上面的程式碼可以看到彙整的處理是在ApplyResultSelector中發生的，我們來看一下ApplyResultSelector裡面做了什麼:

public IEnumerable<TResult> ApplyResultSelector<TResult>(Func<TKey, IEnumerable<TElement>, TResult> resultSelector)
{
    Grouping<TKey, TElement> g = _lastGrouping;
    if (g != null)
    {
        do
        {
            g = g._next;
            g.Trim();
            yield return resultSelector(g._key, g._elements);
        }
        while (g != _lastGrouping);
    }
}

整個流程跟剛剛講到的GetEnumerator()一樣，只差在回傳的是resultSelector處理過後的資料。

測試案例賞析

Grouping_IList_IsReadOnly

[Fact]
public void Grouping_IList_IsReadOnly()
{
    IEnumerable<IGrouping<bool, int>> oddsEvens = new int[] { 1, 2, 3, 4 }.GroupBy(i => i % 2 == 0);
    foreach (IList<int> grouping in oddsEvens)
    {
        Assert.True(grouping.IsReadOnly);
    }
}

前一章我們在說客製比較器的時候有用基偶數的例子，這裡它是直接用keySelector實作。

AllElementsSameKey

[Fact]
public void AllElementsSameKey()
{
    string[] key = { "Tim", "Tim", "Tim", "Tim" };
    int[] scores = { 60, -10, 40, 100 };
    var source = key.Zip(scores, (k, e) => new Record { Name = k, Score = e });

    AssertGroupingCorrect(key, source, source.GroupBy(e => e.Name, new AnagramEqualityComparer()), new AnagramEqualityComparer());
}

這裡看到一個神奇的東西: Zip，它可以把兩個集合合併成一個，太酷了!!

結語

要結束之前我們來順一下整個GroupBy的流程:

  1. GroupBy會去實體化相應的Enumerable
  2. Enumerable會去叫用Lookup.Create()取得分組資料
    1. 叫用GetGrouping取得對應鍵值的Grouping
    2. 將元素用Add加入Grouping
  3. GroupedEnumerable的GetEnumerator()依序叫用各個Grouping
  4. GroupedResultEnumerable會再叫用ApplyResultSelector彙整資料

參考

dotnet/corefx

← Join的應用 →