|
Which category in your performance table above does the following code fall under?
List< Person > people = new List< Person >();
people.Sort(new Comparison< Person >(Person x, Person y)
{
return x.FirstName.CompareTo(y.FirstName);
});
-Bill
|
|
|
|
|
Hi Bill
The code in your message would go under the category "hard-coded".
Kind regards,
Johannes Hansen
frontAvenue A/S
|
|
|
|
|
How can I make this work with a list of Structs instead of a list of classes? It throws an AccessViolation when I use it with structs.
|
|
|
|
|
Looks like (first glance) that you'll get an exception if you try to access the properties of a struct, but playing with the fields is fine. I'll see if I can fix the properties, but i nthe meantime just use the field.
struct Foo
{
private string works;
public string throws
{
get { return works; }
}
}
|
|
|
|
|
Nope, fields only failed to throw, but they didn't really work either.
I've made the changes and my ZIP file. Get it here.
|
|
|
|
|
Hi,
This is great article.
But I think there's more simple way which will handle all the cases (including Enums and Nullable types). Simply a call to the Compare method of Comparer<T>.Default must be emitted. And no checks will be performed for nullables, enums, value types etc.
Am I right ?
P.S. Frankly saying I haven't checked the speed of this approach, but I think it must not dramatically impact the performance.
Regards,
Robert Hovhannisyan.
-- modified at 8:41 Friday 7th April, 2006
|
|
|
|
|
Hi Robert.
First of all thank you for the feedback!
Actually what you're suggesting isn't solving the same problem as DynamicComparer is solving. DynamicComparer is capable of sorting on several fields within the same type where Comparer<t> is using IComparable to call the Compare function on T. Of course you could implement the Compare function to compare several fields but it would be static and you would have to recompile to change the set of fields you do the comparison on, DynamicComparer doesn't have this problem. The performance of the DynamicComparer is probably even a little faster *theoretically* than ordinary compiled comparers since we are able to optimize the comparison better than the .NET compiler is able to.
Kind regards,
Johannes Hansen
frontAvenue A/S
|
|
|
|
|
Hi Johannes,
I think I didn't exactly explained the idea. I am suggesting to emit a call to Compare method of Comparer<T>.Default in CreateDynamicCompareMethod function.
Regards,
Robert Hovhannisyan.
|
|
|
|
|
Hi Robert,
Sure that would probably work... I'll have to try it out first. But, we'll loose the chance to optimize the IL manually. However, I think your suggestion seem like a very good tradeoff since the IL optimization only increases the performance theoretically. Thanks for the suggestion!
Kind regards,
Johannes Hansen
frontAvenue A/S
|
|
|
|
|
Hi again, Johannes !
Just to clarify. I think the confusion was in T used in DynamicComparer<T> and Comparer<T>.Default.
As you understand, idea is to emit a call to Compare method of Comparer<T>.Default for each SortProperty in the sort expression, where T is the PropertyType of the corresponding property with name SortProperty.Name, and not the type parameter T of DynamicComparer<T>.
Regards,
Robert Hovhannisyan.
|
|
|
|
|
Hi,
This is great stuff.
I am running into a problem when trying to sort a list of objects by a property that returns an Enum. I was wondering if you have any thoughts on how this could be done?
Keep up the good work.
-Rich
|
|
|
|
|
If you can post or email me a test case, I'll make it pass
|
|
|
|
|
Thanks Marc. Just sent a test case.
|
|
|
|
|
i Marc,
Thanks for the quick response. This could really get me out of a jam.
I modified the person class and added an Enum for called "Sex."
I versioned the test program (EnumProgram) and loaded up two people and set the "Sex" property for each. You'll see the error when you attempt to sort on "Sex."
Modified Person.cs
------------------
using System;
namespace DynamicComparerSample
{
///
/// Added this enum for test purposes
///
public enum Sex
{
Female,Male
}
public class Person: IComparable<person>
{
private Sex sex;
public Sex Sex
{
get { return sex; }
set { sex = value; }
}
private string firstName;
public string FirstName
{
get { return firstName; }
set { firstName = value; }
}
private string lastName;
public string LastName
{
get { return lastName; }
set { lastName = value; }
}
private double age;
public double Age
{
get { return age; }
set { age = value; }
}
public Person(string firstName, string lastName, double age)
{
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public Person(string firstName, string lastName, double age, Sex sex)
{
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
this.sex = sex;
}
public int CompareTo(Person other)
{
if (other == null)
return 1;
int diff = this.lastName.CompareTo(other.lastName);
if (diff == 0)
diff = this.firstName.CompareTo(other.firstName);
if (diff == 0)
diff = this.age.CompareTo(other.age);
return diff;
}
}
}
Modified Programs.cs
--------------------
using System;
using System.Collections.Generic;
using System.Text;
using DynamicComparer;
using System.Reflection;
using System.Diagnostics;
namespace DynamicComparerSample
{
class Program
{
static readonly string[] firstnames = { "Matt", "James", "David", "Homer", "Bart", "Maggie", "Marge", "Lisa", "Monty", "Barney", "Frank", "Phillip" };
static readonly string[] lastnames = { "Groening", "Brooks", "Cohen", "Simpson", "Burns", "Gumble", "Grimes", "Fry" };
static void Main(string[] args)
{
bool exit = false;
while (!exit)
{
Console.CursorVisible = false;
Console.Write("\n\n\n[T]est, [B]enchmark, or E[x]it?");
ConsoleKey option = new ConsoleKey();
while (option != ConsoleKey.T && option != ConsoleKey.B && option != ConsoleKey.X)
option = Console.ReadKey(true).Key;
Console.CursorVisible = true;
Console.WriteLine();
switch (option)
{
case ConsoleKey.T:
TestIt();
break;
case ConsoleKey.B:
BenchIt();
break;
case ConsoleKey.X:
exit = true;
break;
}
}
}
private static void TestIt()
{
Random rnd = new Random();
Console.Clear();
// Make the collection.
List<person> persons = new List<person>(2);
//Just populate the list with two people using new constuctor to add sex
persons.Add(new Person("Homer","Simpson",40,Sex.Male));
persons.Add(new Person("Wilma","Flinstone",80,Sex.Female));
Console.WriteLine("The following properties are available for sorting:");
foreach (PropertyInfo pi in typeof(Person).GetProperties())
{
if (!typeof(IComparable).IsAssignableFrom(pi.PropertyType))
continue;
Console.WriteLine("{0} ({1})", pi.Name, pi.PropertyType.FullName);
}
// Define which properties should be sorted on (must be IComparable).
// Note: You could either make your own SortProperty array and pass that in or you could make an sql-like "order by" string and pass that to the method.
Console.Write("\nPlease enter an \"order by\" clauses (case-sensitive): ");
string orderBy = Console.ReadLine();
try
{
// Create the comparer for Person types and define the sort fields.
DynamicComparer<person> comparer = new DynamicComparer<person>(orderBy);
// Print the unsorted list.
Console.WriteLine("\nUnsorted:");
foreach (Person p in persons)
Console.WriteLine("{0,-7} {1,-8} | {2,2} years old", p.FirstName, p.LastName, p.Age, p.Sex);
// Sort the list.
try
{
// Note: you could also call the sort method like: Sort(comparer) but calling it with Sort(comparer.Compare) is faster.
persons.Sort(comparer.Compare);
}
catch (Exception ex)
{
Console.WriteLine("\n{0}", ex.ToString());
}
// Print the sorted list.
Console.WriteLine("\nSorted:");
foreach (Person p in persons)
Console.WriteLine("{0,-7} {1,-8} | {2,2} years old", p.FirstName, p.LastName, p.Age, p.Sex);
}
catch (Exception ex)
{
Console.WriteLine("\n{0}", ex.ToString());
}
}
private static void BenchIt()
{
Random rnd = new Random(12345); // repeatable seed...
List<person> unsortedPersons = new List<person>(500000);
for (int i = 0; i < unsortedPersons.Capacity; i++)
unsortedPersons.Add(new Person(firstnames[rnd.Next(firstnames.Length)], lastnames[rnd.Next(lastnames.Length)], rnd.NextDouble() * 100d));
BenchOne(unsortedPersons, "Dynamic with field age: ", new DynamicComparer<person>("age"));
BenchOne(unsortedPersons, "Dynamic with property Age: ", new DynamicComparer<person>("Age"));
BenchOne(unsortedPersons, "Dynamic with field lastName: ", new DynamicComparer<person>("lastName"));
BenchOne(unsortedPersons, "Dynamic with property LastName: ", new DynamicComparer<person>("LastName"));
BenchOne(unsortedPersons, "Dynamic with field lastName,firstName,age: ", new DynamicComparer<person>("lastName,firstName,age"));
BenchOne(unsortedPersons, "Dynamic with property LastName,FirstName,Age: ", new DynamicComparer<person>("LastName,FirstName,Age"));
BenchOne(unsortedPersons, "Dynamic object level: ", new DynamicComparer<person>(string.Empty));
BenchOne(unsortedPersons, "Builtin: ", null);
}
private static void BenchOne(List<person> unsortedPersons, string what, DynamicComparer<person> comparer)
{
List<person> sortedPersons = new List<person>(unsortedPersons.Count);
foreach (Person p in unsortedPersons)
sortedPersons.Add(p);
GC.Collect(GC.MaxGeneration);
GC.WaitForPendingFinalizers();
GC.Collect(GC.MaxGeneration);
GC.WaitForPendingFinalizers();
Stopwatch watch = new Stopwatch();
if (comparer != null)
{
watch.Start();
sortedPersons.Sort(comparer);
watch.Stop();
}
else
{
watch.Start();
sortedPersons.Sort();
watch.Stop();
}
Console.WriteLine(what + watch.Elapsed);
}
}
}
|
|
|
|
|
Okay... looks like Enum values need to be boxed first... I've updated the code and posted a new version here. I'll update my Utilities library too.
For information, the new CreateDynamicCompareMethod looks like this:
private DynamicMethod CreateDynamicCompareMethod(SortProperty[] sortProperties)
{
DynamicMethod dm = new DynamicMethod("DynamicCompare"
, MethodAttributes.Static | MethodAttributes.Public, CallingConventions.Standard,
typeof(int), new Type[] { typeof(T), typeof(T) }, typeof(T), false);
dm.InitLocals = false;
#region Generate IL for dynamic method
Dictionary<Type, LocalBuilder> localVariables = new Dictionary<Type, LocalBuilder>();
ILGenerator ilGen = dm.GetILGenerator();
if (sortProperties.Length > 0)
{
Label lbl = ilGen.DefineLabel();
int numberLeft = sortProperties.Length;
foreach (SortProperty property in sortProperties)
{
Type valueType = property.ValueType;
ilGen.Emit(OpCodes.Ldarg_0);
if (property.Get != null)
{
ilGen.EmitCall(OpCodes.Callvirt, property.Get, null);
}
else
{
ilGen.Emit(OpCodes.Ldfld, property.Field);
}
if (valueType.IsEnum)
{
ilGen.Emit(OpCodes.Box, valueType);
}
else if (valueType.IsValueType && !property.IsNullable)
{
LocalBuilder localBuilder;
if (!localVariables.TryGetValue(valueType, out localBuilder))
{
localBuilder = ilGen.DeclareLocal(valueType);
localVariables.Add(valueType, localBuilder);
}
int localIndex = localBuilder.LocalIndex;
ilGen.Emit(OpCodes.Stloc, localIndex);
ilGen.Emit(OpCodes.Ldloca_S, localIndex);
}
ilGen.Emit(OpCodes.Ldarg_1);
if (property.Get != null)
{
ilGen.EmitCall(OpCodes.Callvirt, property.Get, null);
}
else
{
ilGen.Emit(OpCodes.Ldfld, property.Field);
}
if (valueType.IsEnum)
{
ilGen.Emit(OpCodes.Box, valueType);
}
if (property.IsNullable)
{
MethodInfo elementCompare = typeof(Nullable).GetMethod("Compare");
elementCompare = elementCompare.MakeGenericMethod(valueType.GetGenericArguments()[0]);
ilGen.EmitCall(OpCodes.Call, elementCompare, null);
}
else
{
MethodInfo elementCompare = valueType.GetMethod("CompareTo", new Type[] { valueType });
ilGen.EmitCall(OpCodes.Callvirt, elementCompare, null);
}
if (property.Descending)
ilGen.Emit(OpCodes.Neg);
if (--numberLeft > 0)
{
ilGen.Emit(OpCodes.Dup);
ilGen.Emit(OpCodes.Brtrue_S, lbl);
ilGen.Emit(OpCodes.Pop);
}
}
ilGen.MarkLabel(lbl);
}
else
{
ilGen.Emit(OpCodes.Ldarg_0);
ilGen.Emit(OpCodes.Ldarg_1);
MethodInfo instanceCompare = typeof(T).GetMethod("CompareTo", new Type[] { typeof(T) });
ilGen.EmitCall(OpCodes.Callvirt, instanceCompare, null);
}
ilGen.Emit(OpCodes.Ret);
#endregion
return dm;
}
|
|
|
|
|
Marc,
Your the man!. Works like a champ!
Thanks,
Rich
|
|
|
|
|
First, thanks for a great article and piece of code. I've been looking for something just like this.
In some of my projects, specifically in my Object Relational layer, I have what I am going to call an object chain. For example, if I had many locales per content item, I may have a property on my content object called Locale, which is of type ContentLocale. That object of course has it's own properties. By way of example:
content.Locale.Name
I was wondering if there is any way to modify your code so I could do something like:
List<Content> items = GetContentItems();<br />
items.Sort(new DynamicComparer<Content>("Locale.Name"));
|
|
|
|
|
I've got that ability in my AccessorCache library... give me a couple of days and I'll port that over to my DynamicSorter version. I will also post a couple other useful things (DynamicFilter and DynamicAccessor).
Monitor my blog as I may forget to head over here for a couple days.
|
|
|
|
|
This sounds great! I'm sorry for not being more active at the moment but work is taking up too much of my time. Good thing Marc has gotten involved in the project. Can't wait to see the portation.
Kind regards,
Johannes Hansen
frontAvenue A/S
|
|
|
|
|
I had a look at that library of utilities over at your blog... some nice useful stuff in there. I am very keen to see your DynamicFilter & DynamicAccessor so pls post when you get a chance. Many thanks for opening this to the community.
|
|
|
|
|
I've had some reports that the files couldn't be downloaded. I'm sorry about that... I blew an Apache server upgrade. Everything is back up, you can download from here.
http://musingmarc.blogspot.com
|
|
|
|
|
the follow class will do exactly what u want, even with the example you suggested:
/*------------------------------------------------------------------------
This class is adapted from:
* http://www.rosscode.com/blog/index.php?title=generic_multiple_sorting_for_typed_colle&more=1&c=1&tb=1&pb=1
* and http://www.codeplex.com/NSFxSamples/SourceControl/FileView.aspx?itemId=212083&changeSetId=16449
(thanx Joel)
Created: 2008.04.10
Author: Matthew Kocaj
------------------------------------------------------------------------*/
using System;
using System.Collections.Generic;
using System.Reflection;
public enum OrderDirection
{
Ascending,
Descending
}
/// <summary>
/// used to sort generic collections.
/// will accept n number of columns where
/// those columns are in any n number
/// of composite classes for each item
/// </summary>
/// <typeparam name="T"></typeparam>
public class EntityComparer<T> : IComparer<T>
{
private List<OrderItem> _orderItems = new List<OrderItem>();
#region Constructors
public EntityComparer() { }
public EntityComparer(List<OrderItem> orderItems)
{
this._orderItems = orderItems;
}
public EntityComparer(string sortColumn, OrderDirection orderDirection)
{
this._orderItems.Add(new OrderItem(sortColumn, orderDirection));
}
/// <summary>
/// used for sort expressions in the form "Column1 DESC, Column2 ASC, ..."
/// </summary>
/// <param name="sortExpression"></param>
public EntityComparer(string sortExpression)
{
if (sortExpression != String.Empty)
{
string[] fields = sortExpression.Split(',');
foreach (string field in fields)
{
string[] parts = field.Trim().Split(' ');
if (parts[1] == "ASC")
this._orderItems.Add(new OrderItem(parts[0], OrderDirection.Ascending));
if (parts[1] == "DESC")
this._orderItems.Add(new OrderItem(parts[0], OrderDirection.Descending));
}
}
}
#endregion
public List<OrderItem> OrderItems
{
get { return this._orderItems; }
set { this._orderItems = value; }
}
#region IComparer<T> Members
public int Compare(T x, T y)
{
if (this._orderItems.Count == 0)
return 0;
else
return this.CheckSort(0, x, y);
}
#endregion
/// <summary>
/// Recursive function to do sorting for multiple columns
/// </summary>
/// <param name="sortIndex">The current index of the column we're sorting at</param>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
private int CheckSort(int sortIndex, T x, T y)
{
int returnValue = 0;
if (this._orderItems.Count - 1 >= sortIndex)
{
if (x.GetType().ToString() == y.GetType().ToString())
{
string[] propertyList = this._orderItems[sortIndex].SortColumn.Split('.');
object currentObject1 = x;
object currentObject2 = y;
for (int i = 0; i < propertyList.Length; i++)
{
PropertyInfo property = currentObject1.GetType().GetProperty(propertyList.GetValue(i).ToString());
if (property != null && property.CanRead)
{
currentObject1 = this.GetPropertyValue(property, currentObject1);
currentObject2 = this.GetPropertyValue(property, currentObject2);
}
}
if (currentObject1 != null && currentObject2 != null)
{
// Assume all property types used are
// Comparable
IComparable value1 = (IComparable)currentObject1;
IComparable value2 = (IComparable)currentObject2;
returnValue = value1.CompareTo(value2);
}
// apply Descending differences
if (this._orderItems[sortIndex].OrderDirection == OrderDirection.Descending)
returnValue = returnValue * -1;
}
// call again for multiple columns
if (returnValue == 0)
returnValue = this.CheckSort(sortIndex + 1, x, y);
}
return returnValue;
}
/// <summary>
/// Get Property value
/// </summary>
/// <param name="property">Property</param>
/// <param name="entity">Entity</param>
/// <returns>Value</returns>
private object GetPropertyValue(PropertyInfo property, object entity)
{
return property.GetValue(entity, null);
}
public class OrderItem
{
private string _sortColumn = String.Empty;
private OrderDirection _orderDirection = 0;
public OrderItem(string sortColumn, OrderDirection orderDirection)
{
this._sortColumn = sortColumn;
this._orderDirection = orderDirection;
}
public string SortColumn
{
get { return this._sortColumn; }
}
public OrderDirection OrderDirection
{
get { return this._orderDirection; }
}
}
}
|
|
|
|
|
Cool project!
I've added support for Fields (not just properties), private member access, support for an empty sort causing it to wrap the object's default IComparer or IComparer<T> CompareTo method, and sped up the generated IL by eliminating the local variable for the return value of the CompareTo method. More details and download link here[^].
Marc
-- modified at 15:05 Wednesday 15th February, 2006
I see there is a newer version to fix Nullable<> types. I'll make the needed changes and repost soon.
-- modified at 15:29 Wednesday 15th February, 2006
Updated with Nullable changes.
-- modified at 14:29 Wednesday 1st March, 2006
Added fixes for Enum comparisons (thanks Rich!)
|
|
|
|
|
I've integrated the Nullable changes from message below (not tested, I don't use them much).
Marc
|
|
|
|
|
Thanks for the really good contributions by XIUnin & Marc. Keep it up!
Kind regards,
Johannes Hansen
frontAvenue A/S
|
|
|
|
|