前面我們說到LINQ排序方法有四個OrderBy
、OrderByDescending
、ThenBy
及ThenByDescending
,OrderBy
及OrderByDescending
是設定第一個排序條件,而有沒有Descending
是差在是不是遞減排序,LINQ的排序方法都會回傳IOrderedEnumerable
型別,只有ThenBy
及ThenByDescending
接在它們後面才可以下複數個查詢條件,本章會聚焦在方法的原始碼說明上,讓我們來看看裡面施了什麼魔法吧。
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的過程中又可以增強程式能力,真是太棒了。
[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
的元素會被排在第一個
[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
去相減,所以可以維持原本的排序
這裡的排序方法跟前面的方法差別比較大,所以在原始碼分析上花了不少的篇幅,原始碼看得多後面的測試案例看起來就比較平常了,主要都是應證原始碼中分析出來的特性。