Dynamite: 使用表达式实现高性能动态排序

Henrik Jonsson

4.89/5 (18投票s)

2008年9月25日

CPOL

9分钟阅读

89722

1020

使用 System.Linq.Expression 类开发，通过类 SQL 语法，可以轻松实现对大多数类型序列的高性能动态排序。

下载 Dynamite 库 (包含演示) - 35.7 KB

引言

在过去的几周里，我一直在探索 System.Linq.Expression 命名空间 (在 .NET 3.5 中新增)，以了解如何动态构建代码。结果是一个小型实用库，可用于对各种常见集合结构 (如数组、列表、DataTable 和枚举) 进行动态排序。在此上下文中，动态排序意味着排序顺序可以在运行时使用带有逗号分隔的字段或属性名称的字符串表达式来指定 (与 SQL 的 ORDER BY 语法相同)。得益于扩展方法，这可以非常轻松地实现，如下面的代码片段所示。

Person[] persons;
// ...
persons.Sort("Name.Length, BirthDate DESC");

IEnumerable<Person> sortedPersons = 
  persons.OrderBy("Sex ASCENDING , Name DESCENDING ");

动态排序在排序由用户指定或存储在配置文件中的情况下非常有用。文章 "Generic List Sort Function" 最初启发了我研究排序，并寻找更快捷的方法。也有其他人提出了其他解决方案 (请参阅参考文献部分)。以下列表总结了本文提出的解决方案的特点：

易于使用：现有扩展方法 Sort 和 OrderBy 的新重载。
高性能，这得益于动态编译的比较表达式。
支持 数组、List<T>、IEnumerable<T>、IQueryable<T> 和 DataSet.s
支持所有 公共字段 和属性，包括 Nullable 类型。
支持 引用类型 (class) 和 值类型 (struct) 的属性/字段。
支持 嵌套属性表达式，例如 Mother.Name.Length，并能正确处理 null 值。
不区分大小写的 字符串比较。
开放式设计：可以构建多字段 Comparison<T> 委托、IComparer<T> 和非泛型 IComparer，以用于其他比较和排序场景。

背景

表达式

System.Linq.Expression 命名空间中的类可用于通过表达式树中的基本元素动态构建函数 (lambda 表达式)，这些表达式树可以被使用者解释和翻译 (例如，在 LINQ to SQL 中)，或者编译成可执行的函数委托，以高性能执行。如果我们知道在编译时需要哪个委托，我们可以让编译器像这样构建表达式树：

Expression<Comparison<String>> comparisonExpr = 
   (String s1,String s2) => String.Compare(s1,s2);

这等同于显式创建表达式：

// Create ParameterExpression representing the parameters of the lambda 
// function to create
ParameterExpression s1 = Expression.Parameter(typeof(String), "s1");
ParameterExpression s2 = Expression.Parameter(typeof(String), "s2");

// Build the body of lambda expression.
Expression body = Expression.Call(typeof(String), "Compare", new Type[] {},
                                  s1, s2);

// Finally, create the expression that represents the lambda function.
LambdaExpression comparisonExpr = 
      Expression.Lambda(typeof(Comparison<String>), body, s1, s2);

虽然后者代码片段更冗长，但它允许我们根据需要替换表达式树中的组件。在本文介绍的 Dynamite 库中，这被用于引入对排序表达式中指定的属性的调用。随后，Expression 被编译成一个 Comparison<String> 委托，该委托可用于各种现有的排序方法。

// Compiles the expression to an executable delegate
Comparison<String> comparison = 
   (Comparison<String>)comparisonExpr.Compile();

// Invokes the created delegate to compare two strings
int res = comparison("Hello", "World"); // res = -1

使用代码

要在您的解决方案中启用动态排序，只需将 Dynamite 项目 (或其中构建的 Dynamite.dll) 添加为引用，并导入 Dynamite.Extensions 命名空间。这将立即使您可以访问任何数组或 List<T> 实例的 Sort 方法的新重载版本。所有这些扩展方法都接受一个类型为 String 的 sortExpression 参数。sortExpression 的语法与 SQL 的 ORDER BY 子句相同，即属性/字段名称的逗号分隔列表。可以通过在字段名称后添加 DESC 或 DESCENDING 关键字来指定降序。

using Dynamite.Extensions;
...
List<Person> persons = new List<Person>();
...
persons.Sort("BirthDate DESC, Name");

正如第一个示例所示，Sort 也适用于数组。值得注意的是，这些 Sort 方法执行的是不稳定排序，这意味着如果对同一序列重复排序，具有相同排序键的项之间的顺序不会被保留。相比之下，下面显示的 OrderBy 执行的是稳定排序，其中具有相同排序键的项之间的现有顺序会被保留。

LINQ 风格的排序

Dynamite.Extensions.ComparerExtensions 类还为 LINQ 的 OrderBy 函数提供了扩展方法重载，该方法可应用于实现 IEnumerable<T> 接口的任何序列，包括数组和泛型 List<T>。

// Print names with shortest names first.
foreach( String name in persons.OrderBy("Name.Length, Name").
                                Select(p => p.Name) )
{
    Console.WriteLine(name);
}

上面的示例演示了使用 **嵌套** 字段表达式。Name.Length 指的是 Person 类中 String 类型属性 Name 的 Length 属性。通过动态构建比较方法的方式，null 值也会得到处理。因此，即使 Name 对任何 Person 都是 null，上述代码也不会抛出 NullPointerException。相反，这些 Person 会被排在前面，因为根据定义，null 值被认为小于任何其他值。要使用硬编码的 lambda 函数来实现上述功能，我们需要编写：

// Print names with shortest names first.
foreach( String name in persons.OrderBy(p => p.Name == null ? new int?() : 
            new int?(p.Name.Length)).
           .ThenBy(p => p.Name, StringComparer.CurrentCultureIgnoreCase)
           .Select(p => p.Name)
{
    Console.WriteLine(name);
}

上面可以看到，使用动态排序的 OrderBy 通常会生成更简短、更易读的代码。但是，请记住，当将字段名称指定为字符串字面量时，会失去编译时错误检查。由于解析和编译比较器的开销，性能也会比硬编码排序差 (有关更多详细信息，请参阅下面的 *性能*)。

Queryable 的动态排序

Dynamite 不仅支持实现 IQueryable<T> 接口的数据源的动态排序 (例如，在 LINQ to SQL 中使用)，也支持其他自定义数据提供程序。在这种情况下，用法与 IEnumerable 非常相似，但该库会将字段引用转换为 LambdaExpression，然后由数据提供程序解释。这意味着我们可以这样写：

// Creates a new data context based
// on the common example database Northwind.
Northwnd nw = new Northwnd(@"northwnd.mdf");

foreach (Customer customer in 
         nw.Customers.OrderBy("CompanyName.Length, CompanyName DESC") )
{
    Console.WriteLine(customer.CompanyName);
}

由于 nw.Customers 实现 IQueryable<Customer> 接口，在执行时，这将转换为以下数据库请求：

SELECT ... FROM Customer ORDER BY LEN(CompanyName), CompanyName DESC

尽管在 IQueryable<T> 上使用 OrderBy 与使用普通 IEnumerable<T> 非常相似，但存在一些细微差别，可能会影响结果。首先，为了启用对嵌套属性表达式 (如 Company.Length) 的排序表达式到 SQL 的翻译，不会向动态创建的键选择器添加 null 值检查。相反，如果需要，我们将依赖数据提供程序 (或 DBMS) 来处理。其次，由于标准的 SQL 数据提供程序似乎不支持 OrderBy 的自定义 IComparable<T> 参数，因此不显式指定不区分大小写的字符串比较。字符串的确切排序行为将由数据提供程序 (或 DBMS) 确定。

DataSet 的动态排序

为了支持对强类型和弱类型 DataSet 的动态排序，OrderBy 扩展方法有一个第三个重载版本。这使得可以指定一个包含列名称的排序表达式：

using Dynamic.Data.Extensions;
...
PersonDataSet ds;
...
// Enumerates persons in the Persons table sorted by name and birthdate.
foreach(var row in ds.Persons.AsEnumerable().OrderBy("NAME, BIRTHDATE DESC") )
{
    Console.WriteLine(row.Field<String>("Name"));
}

对于 DataTable，无法使用嵌套说明符，例如 Name.Length。

关注点

在其他情况下使用动态创建的比较器

尽管上面的示例使用了 ComparerExtensions 类中定义的扩展方法，但大部分工作实际上是由 ComparerBuilder<T> 类完成的。这个泛型类定义了多个公共方法，可以根据包含多个嵌套属性或单个属性名称的排序表达式，动态创建 Comparison<T> 委托、IComparable<T> 和非泛型 IComparable 实现。

改进 Windows Presentation Foundation (WPF) 中集合视图的排序

作为不使用扩展方法的用法示例，我将展示一种在 WPF 中执行集合视图动态排序的替代方法。动态排序已经可以通过 SortDescriptions 属性来实现，如下所示：

List<Person> person;
...
ICollectionView personView = CollectionViewSource.GetDefaultView(persons);
personView.SortDescriptions.Add(new SortDescription("Name",
                             ListSortDirection.Ascending));

使用 Dynamite 库，我们可以通过以下代码实现相同的功能：

ListCollectionView personView = 
   (ListCollectionView)CollectionViewSource.GetDefaultView(persons);
             
personView.CustomSort = (System.Collections.IComparer)
   ComparerBuilder<Person>.CreateTypeComparer("Name");

在后一种情况下，我们将 ListCollectionView 类的 CustomSort 属性设置为一个动态创建的类型比较器，该比较器实现了 IComparer 接口。使用此选项可以非常轻松地按多列排序 (而无需处理多个 SortDescription 实例)，并且还支持按嵌套表达式 (如 Name.Length) 进行排序。最后但同样重要的是，使用 ComparerBuilder 可以提高性能，相比于使用 SortDescription。在一个案例中，我将一个包含 100,000 个项目的列表的排序时间从 70 秒缩短到 0.7 秒，即近百倍的改进！

通过避免装箱来提高枚举排序性能

在测试排序性能时，我还发现通过将枚举视为整数 (通常是其底层数值类型) 并进行转换，可以显著提高枚举的排序性能，如下例所示：

// Sort persons by enum typed property AttractedBy
sortedPersons = new List<Person>(persons.OrderBy(p => p.AttractedBy));

// The following gives the same result but performs better  
sortedPersons = new List<Person>(persons.OrderBy(p => (int)p.AttractedBy));

原因可能是枚举只实现了非泛型 IComparable 接口，这需要使用装箱。通过转换为 int (实现了泛型 IComparable<T> 接口)，可以避免装箱。Dynamite 库使用了这一事实，但也可以在其他枚举值排序或比较的情况下使用。

性能

Dynamite 库的开发在很大程度上考虑了性能。

排序表达式被编译成比较函数，一旦编译完成，其速度与编译时生成的代码一样快。这使得排序算法所需的每次比较都比基于反射和为每次比较调用 Invoke 的动态排序策略快得多 (例如 ref [1] 和 [2]) (慢约 40 倍)。
编译后的比较函数会被缓存，以减少在多次调用具有相同排序键时生成和编译表达式树的成本。否则，编译表达式的时间将超过与纯反射相比所节省的时间 (对于短列表 (5-50 个项目) 的排序)。
尽可能使用泛型类和方法，以减少值类型装箱和拆箱的需求。

Expression 与 Emit 的比较

在 .NET 3.5 之前，创建动态代码的唯一方法是使用 System.Reflection.Emit 命名空间中的类，这需要对底层 MSIL 指令有低级知识。Ref [4] 使用此方法动态创建高度优化的排序比较例程。在 Dynamite 库中，我在 ComparerBuilder<T>.CreatePropertyComparisonThroughEmit 方法中包含了我的实现版本。以下是该方法中用于创建字符串类型属性比较的代码片段：

...
DynamicMethod dynMethod = new DynamicMethod("Compare" + propName, typeof(int),
                                            new Type[] { t, t }, t);
ILGenerator ilgen = dynMethod.GetILGenerator();

if (propertyType == typeof(String))
{
    // Call String.Compare(s1,s2,StringComparison.CurrentCultureIgnoreCase)
    ilgen.Emit(OpCodes.Ldarg_0);
    ilgen.EmitCall(OpCodes.Callvirt, propGetMethod, null);
    ilgen.Emit(OpCodes.Ldarg_1);
    ilgen.EmitCall(OpCodes.Callvirt, propGetMethod, null);
    ilgen.Emit(OpCodes.Ldc_I4_1); // 1 = CurrentCultureIgnoreCase
    ilgen.EmitCall(OpCodes.Call, stringCompareMethod, null);
    if (ascending == false)
    {
        ilgen.Emit(OpCodes.Neg);
    }
    ilgen.Emit(OpCodes.Ret);
}
...
return (Comparison<T>)dynMethod.CreateDelegate(typeof(Comparison<T>));

在比较这两种方法的性能时，我得出结论，使用 Emit 动态构建和编译单个动态比较方法的实际时间比使用 Expression 少了近 10 倍。另一方面，使用 Expression 更简单、更安全。此外，由于缓存，扩展的编译时间通常不是问题。更重要的是，在比较大型列表的总排序时间时，我通常没有看到使用 Emit 有任何显著的性能提升。但是，如果需要绝对的最高性能，Emit 在某些情况下可能用于创建比 C# 编译器生成的代码更快的、高度优化的多字段比较例程 (请参阅 ref [4] 中的 DynamicComparer，但请记住 DynamicComparer 不支持嵌套属性)。

使用 Expression 所能做的事情也比使用 Emit 要有限得多。由于 Expression 只支持 lambda 表达式，因此您不能使用局部变量和赋值。在 Dynamite 库中，我通过调用带有参数的子函数来存储中间结果，从而规避了这些限制。

参考文献

Generic List Sort Function - 使用扩展方法和反射进行动态排序。
Generic Multi-Field/Property Sorting for Lists of Business Objects - 使用“加速”反射进行另一种动态排序。
Sorting Collections by Multiple Properties - 使用 MergeSort 和反射进行另一种动态排序。
Dynamic Reflection Library 包含 DynamicComparer，可以使用 Emit 创建运行速度极快的比较器。
LINQ Dynamic Query Library - Microsoft 的强大示例库，可以使用复杂的 C# 或 Visual Basic 语法创建高级的动态 LINQ 排序和筛选查询。

历史

2008年9月25日 - 原文发布。