前面一章提到了我們提到了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>
IEnumerable<TSource> source
: 欲做分組的資料來源
Func<TSource, TKey> keySelector
: 分組的鍵值
IEqualityComparer<TKey> comparer
: 比較鍵值是否相同的等值比較器
GroupedEnumerable<TSource, TKey, TElement>
IEnumerable<TSource> source
: 欲做分組的資料來源
Func<TSource, TKey> keySelector
: 分組的鍵值
Func<TSource, TElement> elementSelector
: 每個元素的輸出資料
IEqualityComparer<TKey> comparer
: 比較鍵值是否相同的等值比較器
GroupedResultEnumerable<TSource, TKey, TResult>
IEnumerable<TSource> source
: 欲做分組的資料來源
Func<TSource, TKey> keySelector
: 分組的鍵值
Func<TKey, IEnumerable<TSource>, TResult> resultSelector
: 每個組別的輸出資料
IEqualityComparer<TKey> comparer
: 比較鍵值是否相同的等值比較器
GroupedResultEnumerable<TSource, TKey, TElement, TResult>
IEnumerable<TSource> source
: 欲做分組的資料來源
Func<TSource, TKey> keySelector
: 分組的鍵值
Func<TSource, TElement> elementSelector
: 每個元素的輸出給resultSelector的資料
Func<TKey, IEnumerable<TElement>, TResult> resultSelector
: 每個組別的輸出資料
IEqualityComparer<TKey> comparer
: 比較鍵值是否相同的等值比較器
這裡我盡量清楚的表示每個方法的差異:
看了這麼多的類別,看的都眼花撩亂了,但是其實它們都是很相似的類別,因此我們就挑一個最複雜的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
到底做了什麼吧。
首先來看剛剛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
方法有幾個看點:
Lookup
的實體
comparer
的話,用預設(Default
)的比較器Grouping
的陣列,預設大小為7
private Lookup(IEqualityComparer<TKey> comparer)
{
_comparer = comparer ?? EqualityComparer<TKey>.Default;
_groupings = new Grouping<TKey, TElement>[7];
}
source
集合中每一個元素做兩個階段的處理
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
本身有兩個執行邏輯:
HashCode
InternalGetHashCode()
取得鍵值HashCode
_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
...
}
create==false
: 取得目前_groupings
中相同鍵值的grouping
回傳,如果在_groupings
中找不到相同鍵值的grouping
就回傳null
grouping
存在hashCode
,hashCode
相同再用Equals
比對grouping
則回傳此grouping
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
}
create==true
: 在新增模式下如果第二步沒有找到相應的grouping
的話,則新增一個
Grouping
_groupings
中,讓之後的查找找得到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
處理過後的資料。
[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
實作。
[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的流程:
GroupBy
會去實體化相應的Enumerable
Enumerable
會去叫用Lookup.Create()
取得分組資料
GetGrouping
取得對應鍵值的Grouping
Add
加入Grouping
GroupedEnumerable
的GetEnumerator()
依序叫用各個Grouping
GroupedResultEnumerable
會再叫用ApplyResultSelector
彙整資料