Sunday, March 15, 2009

Revised IList Extension Methods for Selecting Best Fitting Items from an Unsorted List

Several days ago, I started writing articles about extension methods. One of the articles I wrote was about an IList extension method to select the best fitting item out of an unsorted list in O(n) (linear time). I was working on another article about implementing the quicksort and quickselect algorithms as extension methods.

I got pretty tired of having the same logic implemented in multiple places, but I hadn't yet figured out how to refactor it. Well, I did, so this is an update to those methods that keeps most of the work in one place.

I think it's a pretty cool implementation, it still works correctly, and it's still relatively fast. This implementation is also still side-effect free. That's one reason to use it over a sort/select method. If you need to leave your IList unsorted, then you can't sort and select. Also, if you are selecting from items with a custom IComparer, then even if you don't care about side-effects, you're still better off using this method.

On the other hand, if you don't care about the order of your list and your list type can be sorted with the native TrySZSort, then you're better off using Array.Sort() and selecting the last item in the list. However, if it can't be externed to TrySZSort then the .Net implementation of Array.Sort() uses quicksort which is O(n log n) and the selection is O(1). That's less efficient than the O(n) implementation below.
public static T GetBestFit<T>(this IList<T> list, Comparison<T> comparison)
{
if (list == null || list.Count == 0)
throw new ArgumentException("You cannot get the best fit from an empty list!");

T currentFit = list[0];
for (int i = 1; i < list.Count; i++)
if (comparison(currentFit, list[i]) < 0)
currentFit = list[i];

return currentFit;
}

public static T GetBestFit<T>(this IList<T> list, IComparer<T> comparer)
{
return list.GetBestFit(new Comparison<T>((x, y) => comparer.Compare(x, y)));
}

public static T GetBestFit<T>(this IList<T> list)
where T : IComparable<T>
{
return list.GetBestFit(new Comparison<T>((x, y) => x.CompareTo(y)));
}

public static T GetBestFit<T>(this IList<T> list, Func<T, T, bool> rule)
{
Comparison<T> c = new Comparison<T>((x, y) => (rule(x, y)) ? 1 : -1);
return list.GetBestFit(c);
}

No comments:

Post a Comment