业务对象列表的通用多字段/属性排序
4.89/5 (11投票s)
本文介绍了一种简单灵活的方法，使用多个属性或字段对强类型业务对象列表进行排序。
引言
以下文章介绍了一种通用解决方案，它在功能上模拟 SQL 的 ORDER BY 子句，但在内存中操作强类型列表。所提出的解决方案可用于使用任意数量的属性或字段，按升序或降序对强类型业务对象列表进行排序。该解决方案是通用的，因为对您的类或业务对象代码不需要进行重大更改即可对您自己的自定义类型列表进行排序。排序例程使用 Marc Gravell 的 HyperPropertyDescriptor 进行快速属性值检索。
背景
我目前正在开发一个 Web 项目，旨在帮助一个大型组织跟踪会员信息、发布模糊可搜索的在线目录、打印邮件标签、管理学生试听的在线音乐片段以及规划和安排活动。
用于存储我们数据的后端数据库由大约 40 个表组成。由于我们最终将在完成后将此项目移交给一位经验可能不足的程序员，因此我们的目标之一是保持数据访问简单并最大程度地减少程序员在 SQL/表级别的无谓操作。考虑到这一点，我们决定采用多层数据访问方法。几个月后，一个相当优雅的数据抽象层 (DAL) 已经建成并运行良好，充当数据库表和内存中业务对象之间的中间件。
拥有数据抽象层的诸多好处之一是能够在内存中缓存查询结果，从而显著减少数据库往返次数和整体数据库负载。然而，由于显而易见的原因，列表（人员、位置等）必须在不同的网页上和不同的用户返回不同的排序顺序。例如，一个用户可能希望按姓氏、名字排序，而另一个用户希望按 ID 排序。如果程序员每次想要按不同字段集排序时都必须重新发出带有更改的 ORDER BY 子句的新 SQL 查询，则这些排序要求很容易抵消使用缓存数据的任何好处。另一种避免增加数据库流量并允许内存中排序的方法是为每个业务对象类型添加属性比较例程。
我对这两种选择都不满意，所以（既不想重写业务对象，也不想修改现有类定义），我决定实现一个通用解决方案，在内存列表上模拟 SQL 的 ORDER BY 子句。具体来说，我需要一个能够按任意数量的属性或字段，以任意顺序对任何强类型业务对象列表进行排序的解决方案。
在我继续之前，我想向 Marc Gravell 对他关于 HyperPropertyDescriptors 的文章表示感谢。没有他的代码，属性值的检索将会极其缓慢，本文中使用的反射将不是快速排序大型列表的合理方法。所以，谢谢你，Marc！
Using the Code
该解决方案封装在 我们公司 的命名空间：BinaryNorthwest 中。在该命名空间内，名为 Sorting 的 static 类允许轻松快速地访问排序功能。以下是一些使用示例
示例 1：按属性名进行就地排序
// Sort a list of People by last name
List<People> rgPeople = RetrieveListOfAllPeople();
// Sort the list by the values in the "LastName" property of the "People" class
SortInPlace<People>(rgPeople, new SortPropOrFieldAndDirection("LastName"));
示例 2：使用多个属性的值进行排序
// Sort a list of people by Birth date (descending), then SSN (ascending)
// Note: the sort will automatically compare dates by examining
// the "BirthDate" property type
List<SortPropOrFieldAndDirection> sortCriteria =
new List<SortPropOrFieldAndDirection>();
// Set up the sort criteria
sortCriteria.Add(new SortPropOrFieldAndDirection("BirthDate", true));
sortCriteria.Add(new SortPropOrFieldAndDirection("SSN", false));
// Perform the multi-property sort
List<People> sortedPeopleList = Sorting.MultiSort<People>(rgPeople, sortCriteria);
示例 3：强制对字符串属性进行数字排序（手动排序类型覆盖）
// Force a string field that contains numbers (AuditionRanking)
// to sort using number-comparison criteria
// (Example: 10 comes after 9 using numeric comparison,
// but "10" comes before "9" using string comparison)
SortInPlace<People>(rgPeople, new SortPropOrFieldAndDirection
("AuditionRanking", SortType.eInteger));
它是如何工作的？
对类型为 T 的对象列表（List<T>，其中 T 是具有多个字段和/或属性的类）进行排序的一种简单方法是使用 Sort(IComparer<T> comparer) 方法。此方法接受一个类型为 IComparer<T> 的参数。此委托的任务是对列表中任意两个项目的感兴趣字段或属性执行比较并返回比较结果。委托函数 (int IComparer<T>.Compare(T x, T y)) 传递两个参数，两者都是类 T 的实例（T x，T y），并负责执行比较并返回 -1（如果 x < y）、0（如果 x == y）或 1（如果 x > y）。
SortPropOrFieldAndDirection 类负责获取属性（或字段）名称和排序方向，并构建一个适当地实现 IComparer<T> 的类。生成的 IComparer<T> 派生类检索并比较指定属性名称（或字段名称）的属性值。
为了获得合适的 IComparer<T>，MultiSort 使用公共类 SortPropOrFieldAndDirection 来指定排序顺序和方向，并提供合适的 CompareProperties 或 CompareFields 类实例（CompareProperties 和 CompareFields 都实现 IComparer<T>）。
/// <summary>
/// Retrieves an IComparer of type T, depending on whether the instance
/// of this class (or a derived class) references a property or field
/// </summary>
public IComparer<T> GetComparer<T>() where T : class
{
if (NameIsPropertyName)
{
CompareProperties<T> comp = new CompareProperties<T>
(sPropertyOrFieldName, fSortDescending, sortType);
comp.pi = pi;
comp.Initialize();
return comp;
}
else
{
CompareFields<T> comp = new CompareFields<T>
(sPropertyOrFieldName, fSortDescending, sortType);
comp.fi = fi;
comp.Initialize();
return comp;
}
}
注意：SortPropertyAndDirection 和 SortFieldAndDirection 派生自 SortPropOrFieldAndDirection，可以用于代码清晰度（区分基于字段值和基于属性值的排序标准）。
CompareFields 和 CompareProperties 都实现 IComparer<T>，它们各自的 Initialize() 方法负责设置属性和/或字段比较逻辑。以下是 CompareProperties<T>.Initialize() 的实现
/// <summary>
/// Sets up cached PropertyInfo and determines the best delegate to use
/// to compare values retrieved from that property.
/// </summary>
public void Initialize()
{
if (fFoundProperty == false)
{
// Only look up the Property TypeDescriptor once (the first time)
fFoundProperty = true;
if (pi == null)
{
// Find the TypeDescriptor for the property (and confirm it exists)
// Use this format to take advantage of HyperPropertyDescriptors
// (Marc Gravell)
PropertyDescriptorCollection props = TypeDescriptor.GetProperties(typeof(T));
property = props[sPropertyName];
pi = typeof(T).GetProperty(sPropertyName);
if (pi == null)
{
throw new Exception("Property name " + sPropertyName +
" not found while trying to compare objects of type " +
typeof(T).Name);
}
}
typ = pi.PropertyType;
// Set up the property comparison delegate to use based on the type of
// values we will be comparing
if (sortType == SortType.eUsePropertyOrFieldType)
{
// If we are using the reflected property type, we know that
// no type conversion is needed prior to comparison.
// Use fast direct-cast comparison routines
sortType = Sorting.GetSortTypeEnumForType(typ);
if (typ == typeof(string))
{
if (stringComparisonToUse == StringComparison.Ordinal)
DoCompare = StringCompareOrdinal;
else
DoCompare = StringCompare;
}
else if (typ == typeof(int) && !fSortDescending) DoCompare = CompareInt;
else if (typ == typeof(int)) DoCompare = CompareIntDesc;
else if (typ == typeof(DateTime)) DoCompare = CompareDates;
else if (typ == typeof(long)) DoCompare = CompareTypeSensitive<long>;
else if (typ == typeof(double)) DoCompare = CompareTypeSensitive<double>;
else if (typ == typeof(float)) DoCompare = CompareTypeSensitive<float>;
else if (typ == typeof(short)) DoCompare = CompareTypeSensitive<short>;
else if (typ == typeof(byte)) DoCompare = CompareTypeSensitive<byte>>;
else if (typ == typeof(bool)) DoCompare = CompareTypeSensitive<bool>>;
else DoCompare = CompareUsingToString;
}
else
{
// We are comparing using a user-specified type.
// A type conversion may be necessary
// and we may run into invalid cast exceptions -
// use more robust comparison routines
if (sortType == SortType.eString) DoCompare = CompareUsingToString;
else if (sortType == SortType.eByte) DoCompare = CompareUsingToByte;
else if (sortType == SortType.eDateTime) DoCompare = CompareUsingToDate;
else if (sortType == SortType.eInteger) DoCompare = CompareUsingToInt;
else if (sortType == SortType.eLong) DoCompare = CompareUsingToInt64;
else if (sortType ==
SortType.eDoubleOrFloat) DoCompare = CompareUsingToDouble;
else DoCompare = CompareUsingToString;
}
}
}
每个属性比较委托都相当紧凑，包含类似于以下代码的代码（以下代码比较两个整数）
public int CompareInt(T x, T y)
{
int oX = (int)property.GetValue(x);
int oY = (int)property.GetValue(y);
return (oX < oY) ? -1 : ((oX == oY) ? 0 : 1);
}
总结：使用单个字段/属性进行排序
步骤 #1：创建 SortPropOrFieldAndDirection
SortPropertyAndDirection sortBy = new SortPropertyAndDirection("AssignedTo");
步骤 #2：指定排序条件并希望进行就地单属性排序后，只需调用 Sorting.SortInPlace 方法
Sorting.SortInPlace<WorkItem>(AllWorkItems, sortBy);
在底层，SortInPlace 方法执行以下操作
- 为名为
AssignedTo的属性检索合适的CompareProperties<T>（实现IComparer<T>） - 调用
CompareProperties<T>.Initialize()来查找并缓存将用于从AssignedTo属性检索属性值的TypeDescriptor - 调用 .NET
Sort(IComparer<T>)方法，使用我们自己的标准执行排序
这些步骤由以下代码执行
// Retrieve an IComparer that contains logic for sorting
// this specific business object
// type by the specified criteria
IComparer<T> compare = sortBy.GetComparer<T>();
// lock the list for thread safety and then call
// the .NET Sort(IComparer<T>) method
lock (ListToBeSorted)
{
ListToBeSorted.Sort(compare);
}
“ORDER-BY”式排序（多属性排序）
简而言之，多属性排序首先使用主要排序标准对列表进行排序，然后使用次要标准对每个已排序的子列表进行排序，然后使用三级标准对每个已排序的子子列表进行排序，依此类推。请看以下代码
// Sort a list of people by Birth date (descending), then SSN (ascending)
// Note: the sort will automatically compare dates by examining the
// "BirthDate" property type
List<SortPropOrFieldAndDirection> sortCriteria = new List<SortPropOrFieldAndDirection>();
// Set up the sort criteria
sortCriteria.Add(new SortPropOrFieldAndDirection("BirthDate", true));
sortCriteria.Add(new SortPropOrFieldAndDirection("SSN", false));
// Perform the multi-property sort
List<People> sortedPeopleList = Sorting.MultiSort<People>(rgPeople, sortCriteria);
上述代码类似于在 T-SQL 语句的末尾添加 ORDER BY BirthDate DESC, SSN；结果（已排序）列表包含所有按 BirthDate 降序排序的条目。如果有两个（或更多）人拥有相同的生日，则这两个（或更多）人将按 SSN 排序。
我们已经讨论了 SortPropOrFieldAndDirection<T> 类；它在 MultiSort 中具有相同的目的：返回 IComparer<T> 的适用实现。MultiSort 方法本身执行如下
- 检索第一个指定条件的合适
IComparer<T>并对整个列表进行排序（按BirthDate降序）。 - 将已排序的列表分解为子列表，以便每个子列表中的对象对我们刚刚排序的属性具有相同的属性值。（在上面的示例中，每个子列表将包含所有共享相同
BirthDate的人）。 - 使用下一个排序条件（
SSN）对每个子列表进行排序。 - 如果存在更多排序条件，则返回到步骤 #2，为每个已排序的子列表创建更小的子列表。
- 将所有子列表组合成一个最终的（现在）完全排序的列表。
这不是最节省内存的解决方案，将列表分解为子列表的过程也没有达到最佳优化。然而，添加这些优化会显著增加代码的复杂性，而在正常使用条件下（对 20,000-50,000 个对象列表按 2-3 个属性进行排序）只会提供极小的性能增益。简而言之，代码目前已经相当快了。
废话不多说，多重排序的代码如下
/// <Summary>
/// Sorts a given list using multiple sort (comparison) criteria, similar
/// to an SQL "ORDER BY" clause
/// Example: Specifying the sort/comparison criteria
/// (1) "State" and (2) "Zipcode" using a list of
/// address entries will result in a sorted list containing
/// address entries FIRST sorted by state
/// (starting with the A* states - Alabama, Alaska, etc).
/// Then, the address entries
/// associated with each respective state will be further sorted
/// according to Zipcode.
/// </Summary>
/// <Typeparam name="T">The type of elements in the list to sort<Typeparam>
/// <param name="ListToBeSorted">The original list.
/// A new, sorted list will be returned.</param>
/// <param name="rgSortBy">A list of ordered criteria specifying
/// how the list should be sorted.</param>
/// <Returns>A new list containing all elements of ListToBeSorted,
/// sorted by the criteria specified in rgSortBy.
/// </Returns>
public static List<T> MultiSort<T>(List<T> ListToBeSorted,
List<SortPropOrFieldAndDirection> rgSortBy) where T : class
{
List<T> results;
// For thread safety, make a copy of the list up front.
// Note that you still need to
// lock the same instance of the list when/if it is modified
// by other threads.
lock (ListToBeSorted)
{
results = new List<T>(ListToBeSorted);
}
if (rgSortBy.Count == 1)
{
// if only sorting a single time,
// just call the basic in-place sorting on our copied "results" list
SortInPlace<T>(results, rgSortBy[0]);
return results;
}
try
{
List<List<T>> rgCopies = new List<List<T>>(1);
rgCopies.Add(results);
int sortByCount = rgSortBy.Count;
// For each criterion in the list of comparison criteria,
// one or more lists must be sorted.
// Each time a list is sorted, one or more sublists may be created.
// Each sublist contains items that were deemed
// to be "equivalent" according to the comparison criterion.
// Example: After sorting addresses entries by state
// you may have multiple sublists, each containing all of
// the address entries associated with a given state.
// Note: this is not the most efficient method
// (especially in terms of memory!), but it
// is sufficient in most scenarios and is easier to understand
// than many other methods of sorting a list using multiple criteria.
for (int i = 0; i < sortByCount; i++)
{
SortPropOrFieldAndDirection sortBy = rgSortBy[i];
if (string.IsNullOrEmpty(sortBy.sPropertyOrFieldName))
throw new Exception("MultiSort parameter rgSortBy was passed
an empty field name in rgSortBy [" + i.ToString() + "]");
// Retrieve an IComparer that contains logic for sorting
// this specific business object
// type by the specified criteria
IComparer<T> compare = sortBy.GetComparer<T>();
// Sort each sublist using the created IComparer<T>
foreach (List<T> lst in rgCopies) { lst.Sort(compare); }
if (i < sortByCount - 1)
{
// Create new sublists by searching for the
// sorted-by value boundaries/changes
// Our "best guess" (i.e. shot in the dark)
// is that we will create at least 8 sublists
// from the original list. NOT terribly efficient,
// but often sufficient.
// Some advanced methods involve tracking
// duplicate values DURING the sort itself
List<List<T>> rgNewCopies = new List<List<T>>(rgCopies.Count * 8);
for (int n = 0; n < rgCopies.Count; n++)
{
List<T> rgList = rgCopies[n];
// Be conservative and set the initial sublist capacity
// to a small number, but still honor the original
// list's item count. (Example: If you are sorting a list
// of "Address information" by Zipcode and the
// list has 32,000 entries, then initialize
// each sublist (each of which store all Address
// information entries with the same Zipcode)
// with a capacity of 1000. 32,000 / 32 = 1000
List<T> rgSublist = new List<T>(rgList.Count / 32);
// Compare items to the item that preceeded it
// to determine where the "value boundaries"
// are located. If you will be sorting frequently and
// do not have CPU cycles to burn :),
// a smarter boundary-finding algorithm should be used.
// (e.g. determine boundary locations
// when comparing elements during the sort routine).
// Another alternative is to take advantage of the fact
// that the list is sorted and to
// use a O(LogN) binary search rather than the
// (currently) linear O(N) search.
for (int j = 0; j < rgList.Count; j++)
{
T item = rgList[j];
if (j > 0)
{
// Compare the item to the preceding item
// using the same comparison criterion
// used during the sort
T itemprev = rgList[j - 1];
if (compare.Compare(item, itemprev) == 0)
{
// The item had the same property or
// field value as the preceding item.
// Add it on to the same sublist.
rgSublist.Add(item);
}
else
{
// The item did NOT have the same property
// or field value as the preceding item.
// "Close up" the previous sublist and
// start a new one.
rgNewCopies.Add(rgSublist);
rgSublist = new List<T>(rgList.Count / 32);
rgSublist.Add(item);
}
}
else
{
// The first item has no predecessor -
// just add the item to the first sublist
rgSublist.Add(item);
}
} // END: for (int j = 0; j < rgList.Count; j++) ...
// Add the last created sublist to our
// "master list of sublists" :P
// It may be that this list has 0 elements in some cases,
// but this is not a problem
rgNewCopies.Add(rgSublist);
} // END: for (int n = 0; n < rgCopies.Count; n++) ...
// Move to the next "level" of sublists in
// preparation for further sorting using the next
// sort/comparison criterion
rgCopies = rgNewCopies;
}
} // END: for (int i = 0; i < sortByCount; i++) ...
// reconstruct all resorted sub-sub-sub-sub-sublists into a single,
// final (flat) results list
results.Clear();
foreach (List<T> rgList in rgCopies) { results.AddRange(rgList); }
return results;
}
catch (Exception ex)
{
throw new Exception
("Exception in MultiSort while sorting a list of " + typeof(T).Name, ex);
}
}
使用反射会很慢吗？
使用常规反射（PropertyInfo.GetValue()）通常相当慢，因此不适合比较成千上万个值。请看以下代码
public int CompareInt(T x, T y)
{
int oX = (int)property.GetValue(x);
int oY = (int)property.GetValue(y);
return (oX < oY) ? -1 : ((oX == oY) ? 0 : 1);
}
此代码可能会被调用数千甚至数十万次，以比较两个对象的属性值。为了缓解性能瓶颈，我使用了 Marc Gravell 的 HyperPropertyDescriptor 项目，发布在 CodeProject 此处。简而言之，它通过动态生成代码来访问类的属性，从而实现极其轻量级和快速的属性检索。由于 MultiSortLib 使用 TypeDescriptor 而不是 PropertyInfo 来检索属性值，因此只需将 [TypeDescriptionProvider(typeof(Hyper.ComponentModel.HyperTypeDescriptionProvider))] 附加到您的类定义上，即可通过反射实现极快的属性值查找。
下图显示了使用字段（FieldInfo.GetValue）或属性（PropertyDescriptor.GetValue）检索值，按单个字段或属性，或按三个字段或属性进行排序时，不同长度列表的排序时间。
正如预期的那样，按单个字段或属性排序比按多个字段或属性排序更快。上图还显示，通过 Marc 的 HyperPropertyDescriptor 检索属性值比通过 FieldInfo.GetValue() 检索字段值快得多；使用三个标准对 65,536 个项目列表进行排序，通过 FieldInfo.GetValue() 检索值耗时略超过 2000 毫秒。使用相同的三个标准对相同的 65,536 个项目进行排序，通过 PropertyDescriptor.GetValue() 检索值耗时不到 280 毫秒。
随附的代码还包含一个简单的演示项目。演示项目生成 64 到 100,000 个虚构的“工作项”，并带有虚拟属性值。要检索排序时间信息，请单击列标题或使用右侧的多重排序组合框进行排序。排序项目列表所经过的毫秒数显示在右下角。您还可以选择（通过单选按钮）按检索字段值或属性值进行排序——如果您对相对性能感兴趣，这很有用。
关注点
这个解决方案设计和实现起来相当容易，但在我意识到通过 PropertyInfo.GetValue() 检索值时属性访问有多慢之前，我花了一些时间使用探查器。再次感谢 Marc Gravell 对 HyperTypeDescriptor 的实现。如果您想了解 PropertyInfo.GetValue() 有多慢，只需从 WorkItem 类定义中删除 TypeDescriptionProvider 属性即可。
历史
08/28/07 - 应要求，对演示项目进行了一些补充
- 已定义并添加到每个
WorkItem属性的自定义属性，用于指定与该属性关联的字段名。例如
[PropertyFieldName("sAssignedTo")] public string AssignedTo { get { ... } set { ... } }
WorkItem类的属性不再是硬编码的，现在使用反射进行发现
// Add property names via reflection PropertyInfo[] rgProperties = typeof(WorkItem).GetProperties(); for (int i = 0; i < rgProperties.Length; i++) { string sPropertyName = rgProperties[i].Name; AllPropertyNames.Add(new WorkItemPropertyName(sPropertyName)); }
- 已添加一种更快的方法来比较
Enum字符串表示形式（比使用它们的ToString()方法比较enum快大约 10 倍）。现在，按enum属性TaskBoredom排序要快得多。代码如下
// Added to class CompareProperties<T> private static Dictionary<int, string> FastEnumLookup; /// Faster than comparing enums using .ToString() /// (the Enum.ToString() method appears to be fairly expensive) public int FastCompareEnumsAsc(T x, T y) { int oX = (int)property.GetValue(x); int oY = (int)property.GetValue(y); string s1, s2; // Look in our dictionary/hashtable for the enum value's string // representation if (!FastEnumLookup.TryGetValue(oX, out s1)) { // If this is the first time we have encountered the value, // add it to the dictionary/hashtable Enum eX = (Enum)property.GetValue(x); s1 = eX.ToString(); FastEnumLookup.Add(oX, s1); } if (!FastEnumLookup.TryGetValue(oY, out s2)) { Enum eY = (Enum)property.GetValue(y); s2 = eY.ToString(); FastEnumLookup.Add(oY, s2); } // Perform regular string comparison return s1.CompareTo(s2); }
欢迎任何评论/建议——我很乐意增强并发布未来的版本到 CodeProject。
-- Owen Emlen (owen@binarynorthwest.com)，BrainTechLLC 成员，BinaryNorthwest 合伙人