In 91

前言

前面兩篇分別介紹了 Where() 與 Select() ，這篇則是要介紹 OrderBy() 與 ThenBy() ，這幾個東西看起來最像 SQL 上會用到的語法，但切記一點，這邊介紹的是 LINQ to Objects, 不是 LINQ to SQL or Entity Framework，這些 LINQ API 與 SQL 一點關係都沒有，真要講，是跟 foreach 與 delegate 有比較強烈的關係。

而 OrderBy() 與 ThenBy() 要一起介紹是因為兩者息息相關，另外也會牽扯到一些看起來很抽象的東西，例如：IComparer<T>,  IOrderedEnumerable<T>。IComparer<T> 的介紹，請大家可以先參考先前的文章： [Design Pattern]Decorator Pattern with IComparer － 先比這個，再比那個 ，這是 OrderBy() 與 ThenBy() 實作內容的兩大核心之一。

這篇實作的部份，OrderBy() 與 ThenBy() 一起說明，會比較清楚。

什麼是 OrderBy

OrderBy 就是排序，而排序就是比大小。舉個實際上的例子，假如我們有一群人如下：

當希望用 Name 進行排序時，期望得到的結果如下：

沒有 LINQ 時怎麼做

上述的例子是針對自訂的 entity, 這邊為了方便說明沒有 LINQ 時怎麼作排序，先用單純的 int[] 來說明，如下圖所示：

排序會牽扯到的就是排序演算法，上面的例子是最好懂但效能相當不好的氣泡排序法的實作。不管是什麼樣的排序演算法，都會用到的就是所謂的比較大小，這邊我們把比較大小的職責，委託給 IComparer<T> 來進行比較大小。

讀者可以自行挑選 performance 比較好的演算法，例如 Quick Sort 來實作上面這段功能，但仍然需要用到比較大小的功能。

有 LINQ 時，只要這麼做

這樣的需求，如果使用 LINQ 的 OrderBy() ，其實只要簡單的一行：source.OrderBy(employee => employee.Name); 如下圖所示：

如果需要排序其他欄位，甚至其他 projection 後的結果，也只要修改參數，也就是 delegate 的 lambda 內容即可。

OrderBy() 的 Signature

直接來看 OrderBy() 有哪兩個多載的 signature ，如下圖所示：

為什麼會多一個 IComparer<T> 的多載呢？很簡單，舉個例子，如下圖所示，大家覺得誰比較正呢？

所謂正的定義每個人都有所不同，因此，我們透過 IComparer<T> 來進行比較。

如果今天我們要比較的是自訂的 entity, 使用了第一個 signature, .NET framework 會拋出 exception, 如下圖所示：

原因很簡單，.NET 不知道怎麼比較 Department 這個東西，不知道怎麼比較大小，自然無法進行排序。除非 DepartmentInfo 本身有實作 ICompareable<Department> ，代表自身就能比較大小，否則就需要傳入 IComparer<in Department> 方能比較。

請讀者參考先前的文章： [Design Pattern]Decorator Pattern with IComparer － 先比這個，再比那個 。 了解 IComparer<T> 的意義與實作方式時，我們來看一下，這個例子可以怎麼作，如下圖所示：

上面例子定義了一個 DepartmentComparer 的類別，比較兩個 Departmen的方式則是透過 ID 來比較大小。下圖的說明代表了，如果 x 的 ID 比較小，代表結果小於0，也就代表 x < y 。

解釋完 IComparer<T> 的參數後，回到 OrderBy() 的 signature ，讀者應該留意到回傳的型別是未曾看過的 IOrderedEnumerable<T> ，如下圖所示：

接下來要來解釋 IOrderedEnumerable<T> 是什麼，以及用來作什麼。

IOrderedEnumerable<T>

什麼是 IOrderedEnumerable<T> ? 先來看一下在 MSDN 上的說明，如下圖所示：

IOrderedEnumerable<T> 擴充自 IEnumerable<T> ，也就是 IOrderedEnumerable<T> 是 IEnumerable<T> 的一種 (is-A 的關係)，也就是 IOrderedEnumerable<T> 可以使用針對 IEnumerable<T> 的擴充方法。

而 IOrderedEnumerable<T> 用來幹嘛呢？這個 interface 只有一個方法： CreateOrderedEnumerable() ，如下圖所示：

留意到兩個東西，第一個是參數，要傳入 IComparer<TKey> 。

第二個則是回傳的型別為 IOrderedEnumerable<TElement> 。

回傳型別其實就是自己這個 interface 的型別，也就是這個 IOrderedEnumerable<TElement>.CreateOrderedEnumerable<TKey>() 擁有 fluent interface 的特性，可以不斷串接下去。

講了這麼多， IOrderedEnumerable<TElement> 究竟是用來幹嘛的？

從方法名稱 CreateOrderedEnumerable 字面上的意義就是產生一個排序過的序列，因此要傳入 IComparer<T> ，才能進行排序。

而什麼樣的物件才能呼叫這個方法？IOrderedEnumerable<T> 的物件才能呼叫 CreateOrderedEnumerable() ，也就是要已經排序過的序列，才可以再呼叫這個方法。

那麼回傳的結果呢？回傳的結果，其意義為：原本的 IOrderedEnumerable<T> 代表已經排序過了，再加上新的 comparer 下去排序的結果。

聽起來好像還是很抽象，沒關係，等等帶到實作的部份，各位讀者就會比較清楚。到這邊各位讀者只要了解：IOrderedEnumerable<T> 的目的，就是用來產生（其實稱為記住會更 make sense）多個 comparer 排序後的結果。

ThenBy()

假設有一群 Employees ，我們的需求是：

希望可以先按照其 FirstName 排序，再用 LastName 排序，如下圖所示：

這時如果先 OrderBy(e=>e.FirstName) ，接著再 OrderBy(e=>e.LastName) 出來的結果會如上圖右邊的結果嗎？答案是 No 。

實際的結果如下：

這就是網頁上的 grid 或 table ，在第一欄按下排序，接著再第二欄按下排序，最後的結果其實只有針對第二欄排序而已。

那麼我們要怎麼先排 FirstName, 再排 LastName, 甚至再排其他欄位呢？這時就要使用到 ThenBy() 。

簡單的說：用 ThenBy() 才能記住原本排序的值，然後再排其他欄位。

注意：「用 ThenBy() 才能記住原本排序的值，然後再排其他欄位。」這句話是大家用來說明多重排序常用的說法，但事實上這樣的說法很容易誤導 developer 的思維，事實上多重排序的本質是：排序就是物件比較大小，而排序演算法就是兩兩物件比大小，而比較大小的方式定義在 IComparer 裡面。因此，多重排序事實上是：兩兩物件比較大小，先比這個，比不出來，再比下一個。

ThenBy() 的 Signature

ThenBy() 在 MSDN 上的 signature 如下圖所示：

要留意的是，ThenBy() 這個方法是針對 IOrderedEnumerable<T> 進行擴充，也就是 IEnumerable<T> 能不能呼叫 ThenBy() ? 答案是不行的。那 IOrderedEnumerable<T> 可不可以呼叫 OrderBy() ? 答案是可以的。

接著這邊列出 OrderBy() 與 ThenBy() 的 signature, 讀者比較容易發現其關係。

下圖是這兩個擴充方法所擴充的型別不同，OrderBy() 是針對 IEnumerable<T> ，也就是只要是序列，就可以呼叫 OrderBy() 進行排序。而 ThenBy() 是針對 IOrderedEnumerable<T> ，也就是已經排序過的序列，基本上也就是 OrderBy() 的結果，方能呼叫 ThenBy() ，也就是針對已經排序過的序列，再加入一個新的 comparer 排序。（再提醒一次，基本上 ThenBy() 的動作，就是把之前的 comparer 記起來，再加入這一次想要增加的 comparer 進去比較）

至於，當我們需要透過多個 comparer 來比較兩個物件的大小時該怎麼做，再多嘴一次，請參考前面的文章：[Design Pattern]Decorator Pattern with IComparer － 先比這個，再比那個

接著用最簡單的氣泡排序法來說明剛剛的例子，實際上是怎麼進行多重排序的。

多重排序（OrderBy + ThenBy）的執行經過

氣泡排序法的演算法如下圖所示：

這個的 this._comparer 型別為 IComparer<T> ，但在多重排序時，其 instance 基本上就是前面文章所提到的 ComboComparer，程式碼如下所示：

    /// <summary>
    /// 自己組合兩個comparer, 透過decorator來無限組合n個comparer。
    /// 當外面使用IComparer(T).Compare()時，則會依序比較，直到所有comparer比完為止。
    /// </summary>
    /// <typeparam name="TSource">The type of the source.</typeparam>
    public class ComboComparer<TSource> : IComparer<TSource>
    {
        private IComparer<TSource> _untilNowComparer;
        private IComparer<TSource> _thisTimeComparer;        

        /// <summary>
        /// 先比之前的comparer, 比不出來的話，再比這一次的comparer
        /// </summary>
        /// <param name="x">The x.</param>
        /// <param name="y">The y.</param>
        /// <returns></returns>
        public int Compare(TSource x, TSource y)
        {
            var untilNowComparerResult = this._untilNowComparer.Compare(x, y);
            if (untilNowComparerResult != 0)
            {
                return untilNowComparerResult;
            }

            return this._thisTimeComparer.Compare(x, y);
        }

        public ComboComparer(IComparer<TSource> untilNowComparer, IComparer<TSource> thisTimeComparer)
        {
            this._untilNowComparer = untilNowComparer;
            this._thisTimeComparer = thisTimeComparer;
        }
    }

context 端程式碼與預期結果如下：

根據排序演算法的執行過程，這邊把每個步驟的結果呈現出來，各位讀者就會比較好理解實際上是怎麼進行多重排序的。

步驟 0: MinElement 目前為空，排序的結果也為空。

步驟 1: 將第一筆先放入 MinElement 中。

步驟 2: 第二筆 Amy 跟 MinElement 比較大小。

Amy 比 Jerry 小。 MinElement 改為 Id 為 2 的 Amy 。

步驟 3: 第三筆的 Joe 與 MinElement 的 Amy 比。

Joe 比 Amy 大，因此 MinElement 仍為 Amy 。

步驟 4: 同步驟 3 ，第四筆的 Joe 仍比 MinElement 的 Amy 大。

步驟 5: 目前已經巡覽完一次來源序列了，最小的 Element 為 Amy ，因此將 Id 為 2 的 Amy 先加入排序完的結果。並從來源中將 Amy 移除。

步驟 6: 針對來源重新一次步驟 0 ~ 步驟 5 ，這邊用連續的動畫圖示來表達，如下所示：

把第一筆放到 MinElement 中：

Id 為 3 的 Joe 跟 MinElement 的 Jerry 比，Jerry 比較小。

Id 為 4 的 Joe 跟 MinElement 的 Jerry 比， Jerry 仍比較小。

因此，第二輪比較的結果，最小的是 Id 為 1 的 Jerry ，將其加入排序的結果中，並從來源刪除。

接下來是重點了，因為 3 跟 4 比， FirstName 比不出大小，需要再用到 LastName 比較才能知道誰大誰小。

步驟 7: {"Id":3 , "FirstName": Joe, "LastName": Smith} 跟 {"Id":4 , "FirstName": Joe, "LastName": Abel} 比較。

因為 Abel 比 Smith 小，因此第四筆比第三筆小。

第三輪的結果，最小的是 Id 為 4 的那一筆，加入排序的結果中，並從來源中移除。

最後剩下一筆，就是最大的，加入排序的結果中，即完成先排 FirstName, 再排 LastName 的多重排序。

列出這麼長的排序過程，只是要讓各位讀者能夠了解「多重排序」的過程，以這例子來說，並不是先把四筆資料，用 OrderBy() 將 FirstName 排序後，再拿 OrderBy() 完的四筆結果來排 LastName 。

再強調一次，多重排序的比較方式是：兩兩物件比較，第一個 comparer 比不出大小，就再比下一個 comparer ，直到比出大小為止，若所有 comparer 都比不出大小，即為兩個物件大小相等。

OrderBy() 與 ThenBy() 簡單版的實作

先來檢視目前有的東西：

1. ComboComparer 的實作內容，也就是已經能做到用一個 comparer 來達到多重排序的比較大小。
2. 簡單的排序演算法，也就是將序列中多個 element 透過上述的 ComboComparer 來進行多重排序。

因此目前還少的東西：

第一：ComboComparer 是傳入兩個 IComparer<TSource> ，但 OrderBy() 與 ThenBy() 傳入的參數是 IComparer<TKey> ，因此從 OrderBy() 與 ThenBy() 傳入的參數，還需要一個步驟才能轉成 ComboComparer。這步驟也不難，就是透過像 Select() 一樣的 keySelector ，讓呼叫端可以傳入兩個 TSource 的物件，但比較大小是比較其 projection 後的 key 值。

因此，我們需要一個 ProjectKeyToElementComparer 。有了這個 ProjectKeyToElementComparer ，就可以從 OrderBy() 與 ThenBy() 所傳入的 IComparer<TKey> 參數，組成 ComboComparer 。

第二：OrderBy() 與 ThenBy() 串接的橋樑是 IOrderedEnumerable<T> ，因此我們還需要一個實作 IOrderedEnumerable<T> 的 concrete class ，其職責就是要能將該來源序列，與曾經加入的 comparer 記住，以供延遲執行時，透過多重排序的 ComboComparer 進行比較大小。

聽起來很複雜，看 code 比較好懂。

複習一下 OrderBy() 的簽章：

ComboComparer 的定義與建構式：

透過 OrderBy() 的參數，我們擁有一個 Func<TSource, TKey> 的 selector, 以及 IComparer<TKey> 的 comparer 。而我們期望能夠得到一個 IComparer<TSource> 的物件，來給 ComboComparer 用。

因此，ProjectKeyToElementComparer 程式碼相當簡單，如下所示：

    /// <summary>
    /// 傳TSource進來，TSource透過keySelector取得key，也就是要比較的值
    /// 透過IComparer(TKey)來比較兩個TSource
    /// 目的是讓不同的IComparer(TKey)，都可以變成相同的IComparer(TSource)
    /// </summary>
    /// <typeparam name="TSource">The type of the source.</typeparam>
    /// <typeparam name="TKey">The type of the key.</typeparam>
    public class ProjectKeyToElementComparer<TSource, TKey> : IComparer<TSource>
    {
        private Func<TSource, TKey> _keySelector;
        private IComparer<TKey> _comparer;

        public ProjectKeyToElementComparer(Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            this._keySelector = keySelector;
            this._comparer = comparer;
        }

        public int Compare(TSource x, TSource y)
        {
            var xKey = this._keySelector(x);
            var yKey = this._keySelector(y);

            var result = this._comparer.Compare(xKey, yKey);
            return result;
        }
    }

ProjectKeyToElementComparer 一言以蔽之：傳入兩個 TSource, 用 key 值去比較大小。

接下來複習一下 IOrderedEnumerable<T> ，其目的為保留原始來源序列，以及保留拿來進行多重排序的 comparer ，簡單的說，就是組成 ComboComparer 的動作。如下所示：

這邊實作 IOrderedEnumerable<T> 的 class 暫且命名為 MyOrderedEnumerable ，其建構式如下所示：

一定要記住這個物件的職則：保留原本的來源序列，把目前為止的 comparer 記起來。因此建構式就只是記住來源序列，以及目前為止的 comparer 。

接下來來看 CreateOrderedEnumerable() 方法內容，這個方法如前面所說，目的就是用來組成多重排序的 ComboComparer ，內容如下所示：

傳入的參數 Func<TSource, TKey> keySelector 與 IComparer<TKey> comparer 讀者有沒覺得很熟悉？沒錯，這就是 OrderBy() 與 ThenBy() 的參數型別。

請原諒我因為時間差問題，做了兩份文件，在這篇文章中出現的 ProjectionComparer 與 ProjectKeyToElementComparer 指的是同一個 class 。

透過上面的 ProjectionComparer （也就是前面提到的 ProjectKeyToElementComparer） 就可以把 keySelector 與 IComparer<TKey> 轉變成實作 IComparer<TSource> 的 ProjectionComparer ，接著就可以把目前為止的 comparer 與這一次 CreateOrderedEnumerable() 所傳入後產生的 ProjectionComparer 組成 ComboComparer 。

最後要回傳的 IOrderedEnumerable<T> 則是 new 一個 MyOrderedEnumerable ，一樣傳入原始的來源序列：this._source ，但這時傳入的 IComparer<T> ，就是結合所有多重排序用的 comparer 所產生的 ComboComparer 。

別忘了，IOrderedEnumeable<T> 擴充自 IEnumerable<T> ，因此 MyOrderedEnumerable 也要實作 GetEnumerator() 的方法內容，而這個方法如前系列文章所提，就是 LINQ 延遲執行的實際內容。因此 GetEnumerator() 內容一點也不難，就是我們的氣泡排序演算法，如下圖所示：

其實這邊用來比較兩個物件大小的 this._untilNowComparer , 就是可以做多重排序的 ComboComparer 。

歸納一下 IOrderedEnumerable<T> 的結論：

1. 保留 source ，並組合多個 comparer：建構式用來保留 source 與傳入截至目前的 comparer。CreateOrderedEnumerable() 用來加入這一次新的 comparer ，組成 ComboComparer 。
2. 實際比較大小，產出結果： GetEnumerator() 中透過可多重排序的 comparer 來實作排序演算法。

實作了這麼多輔助用的 class ，接下來 OrderBy() 與 ThenBy() 的實作，就只是組合上述的 class 來達成多重排序的效果，以及 LINQ to Objects 使用上的便利。

MyOrderBy() 的實作內容

程式碼如下所示：

        public static IOrderedEnumerable<TSource> MyOrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
        {
            return MyOrderBy(source, keySelector, Comparer<TKey>.Default);
        }        

        /// <summary>
        /// 把這一次OrderBy的comparer加入MyOrderedEnumerable()中存著，以待後續若還有ThenBy()，可以將comparer結合起來
        /// 當外部展開MyOrderBy的結果時，則會呼叫MyOrderedEnumerable的GetEnumrator()，則會執行排序演算法
        /// </summary>
        /// <typeparam name="TSource">The type of the source.</typeparam>
        /// <typeparam name="TKey">The type of the key.</typeparam>
        /// <param name="source">The source.</param>
        /// <param name="keySelector">The key selector.</param>
        /// <param name="comparer">The comparer.</param>
        /// <returns></returns>
        /// <exception cref="System.ArgumentException">source</exception>
        public static IOrderedEnumerable<TSource> MyOrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            if (source == null)
            {
                throw new ArgumentException("source");
            }

            return new MyOrderedEnumerable<TSource>(source, new ProjectKeyToElementComparer<TSource, TKey>(keySelector, comparer));
        }

MyThenBy() 的實作內容

程式碼如下所示：

        public static IOrderedEnumerable<TSource> MyThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector)
        {
            return MyThenBy(source, keySelector, Comparer<TKey>.Default);
        }

        /// <summary>
        /// 從OrderBy()的部份可以看到，現在的source已經是MyOrderedEnumerable的結構了。裡面已經存放著先前的comparer。
        /// 在MyOrderedEnumerable.CreateOrderedEnumerable()方法中，則會再將這一次ThenBy()的Comparer加入。
        /// 讓實際在排序中比較大小時，
        /// </summary>
        /// <typeparam name="TSource">The type of the source.</typeparam>
        /// <typeparam name="TKey">The type of the key.</typeparam>
        /// <param name="source">The source.</param>
        /// <param name="keySelector">The key selector.</param>
        /// <param name="comparer">The comparer.</param>
        /// <returns></returns>
        /// <exception cref="System.ArgumentException">source</exception>
        public static IOrderedEnumerable<TSource> MyThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            if (source == null)
            {
                throw new ArgumentException("source");
            }

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

遞增與遞減排序

遞增與遞減，也就是升冪與降冪的排序，是取決於 IComparer<T>.Compare() 的實作內容，傳入欲比較的兩個物件 x 與 y , IComparer<T>.Compare(x,y) ，若回傳的結果小於 0, 則代表 x 比較小。

升冪降冪的幾種作法：

1. 將 Compare() 回傳結果 * –1 ，即可對調遞增遞減。
2. 將傳入 Compare(x,y) 改為 Compare(y,x) 也可以改變大小的關係。

結論

雖然在 LINQ 中只是簡單的 OrderBy() 與 ThenBy() ，用起來既簡單又直覺，但是這兩個方法背後的設計是相當美妙的。我個人認為美妙的點在於：

1. IComparer<T> 的設計：超美，只有一個簡單的 Comparer() 來比較大小，卻提供了「任何比較大小」的抽象行為，當然也包含了多重條件的比較大小。
2. IOrderedEnumerable<T> 的設計：超乾淨的抽象，乾淨到在 .NET Framework 中找不到有什麼 class 實作這個 interface ，字面上的意義就是產出一個排序過序列，但實質目的其實就是保留來源序列，保留截至目前為止所有要拿來比較大小的 comparer 。
3. 在實作 IOrderedEnumerable<T> 中的 GetEnumerator() 設計「不管比較大小方式實作內容」的排序演算法，排序演算法只要知道兩個物件誰大誰小即可，根本不需要知道這兩個物件是怎麼比較的。因為那是 IComparer<T> 的職責。

從 LINQ 學習 C# 與架構設計的藝術，真的是一趟很棒的旅程，希望各位讀者也可以盡情享受這段過程。

Reference

1. MSDN OrderBy() 說明
2. MSDN ThenBy() 說明
3. MSDN IComparer<T> 說明
4. MSDN IOrderedEnumerable<T> 說明
5. Reimplementing LINQ to Objects: Part 26a – IOrderedEnumerable
6. Reimplementing LINQ to Objects: Part 26b - OrderBy{,Descending}/ThenBy{,Descending}

感謝同事 Shelly 協助設計 training 教材。

Sample Code（含測試專案與測試案例） 下載：TestOrderByAndThenBySample.zip

blog 與課程更新內容，請前往新站位置：http://tdd.best/