Ever have trouble finding things?
This is just a quick code snippet to quickly find the nearest item from a generic list. It leverages the .NET BinarySearch function, and it also uses the new Extension methods functionality of .NET 3.5 (Visual Studio 2008).
Here’s the extension in its entirety:
public static class BinarySearchExtension
{
// Computes a distance between the query and a given object.
public delegate double DistanceFunction<T>
// Finds the nearest item to the query item in a sorted list.
public static int BinarySearchNearest<T>
this List
DistanceFunction
int n = list.Count,
i = ~list.BinarySearch(query); /* O(log(n)) */
return
(i < 0) ? ~i : /* query (q) was in the list */
(i < 1) ? 0 : /* q < [0] */
(i == n) ? n - 1 : /* q > [n-1] */
Math.Abs(distFunc(list[i])) < /* [i] < q < [i-1] */
Math.Abs(distFunc(list[i - 1])) ?
i : i - 1; /* return the closest */
}
}
Here’s an example of using it to search a list of dates:
List<DateTime> times = new List<DateTime>();
times.Add(DateTime.Parse(“8/16/2007?));
times.Add(DateTime.Parse(“7/7/2007?));
times.Sort(); /* Must be sorted before BinarySearch */
int i = times.BinarySearchNearest(DateTime.Now,
/* distance: hours between now and t */
t => t.Subtract(DateTime.Now).TotalHours);
DateTime nearest = times[i]; /* nearest is 8/16/2007 */
I have mixed feelings about extensions. They are clean and messy at the same time — clean because you can, with very little code, add new functionality to old classes (even those that you didn’t write). Unfortunately, because the extensions are separated from the classes they concern, it could easily set up a messy dependency situation. For many projects, I think a good practice is to keep all of your extensions localized together in one assembly.
Comments (2)
That nearest match stuff looks pretty handy
In the Python world, we handle dependencies by packaging code into something called an ‘egg’ – the egg contains the information Python needs to locate and download any missing dependencies. It’s kinda cool… is there anything like that in .NET?
I’m not aware of anything which gives that level of scriptable dependency acquisition for the .NET platform. The strong typing of C# makes it more difficult, but not impossible. I’m sure there are tools that help with this kind of thing in true production environments, but I bet the setup overhead casts a big shadow.
In my current startup, I could definitely use more options for dynamically updating references. In Visual Studio, you either include the dependencies in your ‘Solution’ and changes get compiled when you press ‘F5′, or you link to a DLL, which relies on you to separately keep that DLL up to date. A nice middle-ground, where the DLL’s source project is monitored for changes, would be useful.