• 热门专题

快快乐乐学LINQ系列OrderBy(), ThenBy()简介

作者:In 91  发布日期:2013-10-05 18:40:30
Tag标签:LINQ  OrderBy  ThenBy  
  • 前言
    前面两篇分别介绍了 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() 简单版的实作
    先来检视目前有的东西:

    ComboComparer 的实作内容,也就是已经能做到用一个 comparer 来达到多重排序的比较大小。
    简单的排序算法,也就是将序列中多个 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> 的结论:

    保留 source ,并组合多个 comparer:建构式用来保留 source 与传入截至目前的 comparer。CreateOrderedEnumerable() 用来加入这一次新的 comparer ,组成 ComboComparer 。
    实际比较大小,产出结果: 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);
    }
    

    ThenBy() 就是将已经保存好 source 与截至目前为止的 comparer ,也就是 OrderBy() 或 ThenBy() 结果的 IOrderedEnumerable<T> ,再加入这一次 ThenBy() 要加入的 comparer 去进行多重排序。

    也就是呼叫 IOrderedEnumerable<T> source 的 CreateOrderedEnumerable() 方法,传入这一次 ThenBy() 的参数。

    如此一来,当 foreach 展开 OrderBy().ThenBy() 的结果时,就是 GetEnumerator() 中会使用可以进行多重排序的 comboComparer 进行比较大小来排序。
     

     
    递增与递减排序
    递增与递减,也就是升幂与降序的排序,是取决于 IComparer<T>.Compare() 的实作内容,传入欲比较的两个对象 x 与 y , IComparer<T>.Compare(x,y) ,若回传的结果小于 0, 则代表 x 比较小。

    升幂降序的几种作法:

    将 Compare() 回传结果 * –1 ,即可对调递增递减。
    将传入 Compare(x,y) 改为 Compare(y,x) 也可以改变大小的关系。
     

    结论
    虽然在 LINQ 中只是简单的 OrderBy() 与 ThenBy() ,用起来既简单又直觉,但是这两个方法背后的设计是相当美妙的。我个人认为美妙的点在于:

    IComparer<T> 的设计:超美,只有一个简单的 Comparer() 来比较大小,却提供了「任何比较大小」的抽象行为,当然也包含了多重条件的比较大小。
    IOrderedEnumerable<T> 的设计:超干净的抽象,干净到在 .NET Framework 中找不到有什么 class 实作这个 interface ,字面上的意义就是产出一个排序过序列,但实质目的其实就是保留来源序列,保留截至目前为止所有要拿来比较大小的 comparer 。
    在实作 IOrderedEnumerable<T> 中的 GetEnumerator() 设计「不管比较大小方式实作内容」的排序算法,排序算法只要知道两个对象谁大谁小即可,根本不需要知道这两个对象是怎么比较的。因为那是 IComparer<T> 的职责。
    从 LINQ 学习 C# 与架构设计的艺术,真的是一趟很棒的旅程,希望各位读者也可以尽情享受这段过程。

     

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规