一起谈.NET技术,数组排序方法的性能比较(3):LINQ排序实现分析

时间:2022-04-30 20:11:09

上次我们分析了Array.Sort方法的实现方式,并了解到类库会为一些特例而使用高性能的排序方式——int数组便是这样一例,因此从测试结果上来看其性能特别高。不过从数据上看,即便是在普通的情况下,Array.Sort的性能也比LINQ排序要高。不过也有朋友从测试中得出的结论正好相反,这又是为什么呢?那么现在,我们再来分析一下LINQ排序的实现方式吧,希望这样可以了解到两者性能差别的秘密。

只可惜,LINQ排序的代码在System.Core.dll程序集中,微软没有发布这部分源代码,我们只得使用.NET Reflector来一探究竟了。

LINQ排序接口的定义、使用及扩展

所谓LINQ排序,便是使用定义在System.Linq.Enumerable类中的几个扩展方法,它们是:

public static IOrderedEnumerable OrderBy(
    this IEnumerable source, Func keySelector);
public static IOrderedEnumerable OrderBy(
    this IEnumerable source, Func keySelector, IComparer comparer);
public static IOrderedEnumerable OrderByDescending(
    this IEnumerable source, Func keySelector);
public static IOrderedEnumerable OrderByDescending(
    this IEnumerable source, Func keySelector, IComparer comparer);

为了使用时的方便,我往往会补充一些额外的接口,例如:

public static IOrderedEnumerable OrderBy(
    this IEnumerable source, Func keySelector, bool decending)
{
    return decending ?
        source.OrderByDescending(keySelector) :
        source.OrderBy(keySelector);
}

这样在使用时,便可以使用一个布尔值来表示排序的方向(升序或是降序)而不需要从两个方法之间“手动”选择一个。此外,构造一个IComparer类型也实在有些麻烦,于是我按照Array.Sort的做法重新继续扩展了一个使用委托对象作为“比较器”的接口:

public static IOrderedEnumerable OrderBy(
    this IEnumerable source, Func keySelector, Comparison compare, bool decending)
{
    return decending ?
        source.OrderByDescending(keySelector, new FunctorComparer(compare)) :
        source.OrderBy(keySelector, new FunctorComparer(compare));
}

至于FunctorComparer类的实现,由于过于简单就省略了吧,贴出来也只是占用地方而已。有了这个接口,在排序的时候我们就可以这样使用了:

employee.OrderBy(p => p.Manager, (m1, m2) => ... /* 比较逻辑 */, false);

不过,无论是哪个接口、重载还是扩展,它的(除this外)的第一个参数便是keySelector,它的含义便是选择(select)出排序的“依据”。这个参数不可省略(除非您提供扩展),因此即便是int数组这样的类型,需要排序时也必须指定“自己”为排序依据:

intArray.OrderBy(i => i);

这也是LINQ排序和Array.Sort的本质区别之一。

OrderedEnumerable的实现

无论是哪个接口,最终创建的都是OrderedEnumerable类型,例如:

public static IOrderedEnumerable OrderBy(
    this IEnumerable source, Func keySelector)
{
    return new OrderedEnumerable(source, keySelector, null, false);
}

OrderedEnumerable的含义是“根据TKey排序TElement序列的结果”,它的构造函数仅仅是保留传入的参数:

internal OrderedEnumerable(
    IEnumerable source, Func keySelector, IComparer comparer, bool descending)
{
    // 省略参数校验
    base.source = source;
    this.parent = null;
    this.keySelector = keySelector;
    this.comparer = (comparer != null) ? comparer : ((IComparer) Comparer.Default);
    this.descending = descending;
}

可见,如果您没有提供比较器,类库会自动选用Comparer.Default进行比较。这个类会尽可能地寻找可用的比较方式,在“万不得已”的情况下只得跑出异常。如果您对它的实现感兴趣可以自行阅读代码——甚至无需使用.NET Reflector。

事实上,在OrderedEnumerable中并没有提供排序等关键性功能,它只是override了基类的GetEnumerableSorter方法,用于提供一个“排序器”。它的基类是OrderdEnumerable,其含义是“排序TElement序列的结果”,它并不涉及到“排序方式”,而只是提供了一个抽象方法用于获得一个“排序器”——没错,这就是它的子类,如OrderedEnumerable的职责了(还记得TKey的含义吗:“根据TKey进行排序”)。

不过,事实上除了OrderdEnumerable以外也没有其他子类了,由于这些都是internal类型,因此我认为这样有些“过渡设计”。根据我们昨天“人肉反编译”的结果,可以得到OrderedEnumerable的完整实现:

internal abstract class OrderedEnumerable : IEnumerable...
{
    internal IEnumerable source;
    internal abstract EnumerableSorter GetEnumerableSorter(EnumerableSorter next);
    public IEnumerator GetEnumerator()
    {
        var buffer = new Buffer(this.source);
        if (buffer.count <= 0) yield break;
        var sorter = this.GetEnumerableSorter(null);
        var map = sorter.Sort(buffer.items, buffer.count);
        for (var i = 0; i < buffer.count; i++)
        {
            yield return buffer.items[map[i]];
        }
    }
    ...
}

与我们平时接触到的排序算法不同,EnumerableSorter的Sort方法并不改变原数组,它只是生成根据buffer.items数组生成一个排序之后的“下标序列”——即map数组。当外部需要输出排序后的序列时,OrderedEnumerable才会根据map中的下标顺序,依次输出buffer.items数组中的元素。

请注意,到目前为止我们还是没有接触到最终的排序实现。换句话说,现在我们还是不清楚LINQ排序性能高(或低)的关键。

排序实现:EnumerableSorter

LINQ排序的实现关键还是在于EnumerableSorter,我们且看其Sort代码:

internal abstract class EnumerableSorter
{
    internal abstract int CompareKeys(int index1, int index2);
    internal abstract void ComputeKeys(TElement[] elements, int count);
    private void QuickSort(int[] map, int left, int right)
    {
        ...
    }
    internal int[] Sort(TElement[] elements, int count)
    {
        this.ComputeKeys(elements, count);
        int[] map = new int[count];
        for (int i = 0; i < count; i++)
        {
            map[i] = i;
        }
        this.QuickSort(map, 0, count - 1);
        return map;
    }
}

从之前的分析中得知,Sort方法的作用是返回一个排好序的下标数组。它会调用ComputeKeys抽象方法“事先”进行Key(也就是排序依据)的计算。然后再使用快速排序来排序map数组。在QuickSort中,它使用CompareKeys方法来获得“两个下标”所对应的元素的先后顺序。仅此而已,没什么特别的。甚至我在这里都不打算分析ComputeKeys和CompareKeys两个方法的实现,因为他们实在过于直接:前者会把source序列中的元素依次调用keySelector委托,以此获得一个与source对应的TKey数组,而后者便是根据传入的下标来比较TKey数组中对应的两个元素的大小。

不过,我还是强烈建议您阅读一下EnumerableSorter及其子类EnumerableSorter的实现,以此了解LINQ to Object是如何优雅地支持以下表达式的:

var sorted = from p in people
             orderby p.Age
             orderby p.ID descending
             select p;

这个表达式的含义是“将Person序列首先根据Age属性进行升序排列,如果Age相同则再根据ID降序排”——类库在实现时使用了类似于“职责链模式”的做法,颇为美观。

LINQ排序与Array.Sort的性能比较

如果您仔细阅读EnuerableSorter的QuickSort方法,会发现它使用的快速排序算法并不“标准”。快速排序的性能关键之一是选择合适的pivot元素,但是QuickSort方法总是选择最中间的元素——(left + right) / 2。此外,它也没有在元素小于一定阈值时使用更高效的插入排序。因此,从理论上来说,QuickSort方法使用的快速排序算法,其性能不如Array.Sort。

不过,根据姜敏兄的测试结果,LINQ排序的性能超过Array.Sort,这又是怎么回事呢?事实上,虽然姜兄的这个测试存在很大的问题(代码写错了),最后得到的结论“性能高低和元素类型有关”的结论也不确切,但是它也的确能体现一些问题。这个问题事实上已经由Ivony...老大解释过了,不过为了信息完整思维连贯,我在这里再进行详细说明一下。

从理论上来说,Array.Sort和LINQ排序的时间复杂度是相同的,因此性能“似乎不会有太大不同”,但是从实验结果上看差距还是十分明显的。因为从实际上看,Array.Sort对于特殊类型有特殊处理,此外LINQ排序会有复制元素的开销,因此我之前我认为“找不到LINQ排序的性能有优势的理由”。可惜这句话已经站不住脚了,我们来观察一下两种排序方式在实现上的主要区别:

  • Array.Sort:使用IComparer对象比较两个元素的大小。
  • LINQ排序:首先根据keySelector获得TKey序列,然后在排序时使用IComparer比较两个TKey元素的大小。

那么,以此您是否可以判断出以下两个排序方法的性能高低?

public class Person
{
    public int Age { get; set; }
}
public class PersonComparer : IComparer<Person>
{
    public int Compare(Person x, Person y)
    {
        return x.Age - y.Age;
    }
}
Person[] people = ...
var byLinq = people.OrderBy(p => p.Age).ToList();
var byArray = Array.Sort(people, new PersonComparer());

在实际测试之前我无法做出判断,因为它们其实各有千秋:

  • Array.Sort:虽然不需要进行额外的元素复制,但是调用PersonComparer.Compare方法的开销较大——访问Age属性相当于调用get_Age方法(如果没有内联的话)。
  • LINQ排序:虽然需要进行额外的元素复制,而且需要事先计算出排序用的键值(Age属性),但是在排序时只需直接比较int即可,效率较高。

这其实也就是某些测试中发现LINQ排序性能较高的“秘密”。为什么同样排序Person序列时,我的测试(http://gist.github.com/282796)表明Array.Sort较快,而其他一些朋友却得到LINQ排序较快的结果呢?这是因为我的Person类直接使用了公开字段而不是属性,这样避免了方法调用的开销。此外,另一些朋友的PersonComparer在比较两个int时使用了x.Age.CompareTo方法——这又比直接进行int减法要慢上一些了。

那么,还有影响两者性能的因素吗?我们有办法提高数组排序的性能吗?毕竟很多时候我们需要直接排序,而不是生成新的序列。下次我们再来讨论这些问题吧。

相关文章

  1. 数组排序方法的性能比较(1):注意事项及试验
  2. 数组排序方法的性能比较(2):Array.Sort实现分析
  3. 数组排序方法的性能比较(3):LINQ排序实现分析