Generics Algorithms
A few weeks ago, Anders walked into the C# design meeting and said, "I think I have
a way to get generic algorithms to work with our current support", and then proceeded
to outline a scheme on the whiteboard. I dutifully copied it into our design notes
(after being away from the design process for a couple of years, keeping the notes
up to date is my big contribution).
Today, I was home taking care of my sick daughter, so I spent some time playing around
with his idea.
The basic idea is to create a generic class that defines the operations that can be
performed on a data type, and then create specialized implementations. Something like:
public abstract class Calculator<T>
{
public abstract T Add(T a, T b);
}
and then derive a specific class from it:
namespace Int32
{
public class Calculator: Calculator<int>
{
public override int Add(int a, int b)
{
return a + b;
}
}
}
We'll be using Int32.Calculator to perform operations on ints. We could extend thte
calculator class to perform more operations, and create implementations to deal with
different types. So that's the first part of the scheme. It's somewhat reminiscent
of template specializations in C++, but it's not
We can now define a library to use it:
class AlgorithmLibrary<T> where T: new()
{
Calculator<T> calculator;
public AlgorithmLibrary(Calculator<T> calculator)
{
this.calculator = calculator;
}
public T Sum(List<T> items)
{
T sum = new T();
for (int i = 0; i < items.Count; i++)
{
sum = calculator.Add(sum,
items[i]);
}
return sum;
}
}
This class encapsulates algorithms inside of it. When we want to use it, we can write:
AlgorithmLibrary library = new AlgorithmLibrary<int>(new Int32.Calculator());
I should perhaps explain how this works. When we construct library with int as the
type argument, that means that constructor is looking for a Calculator<int>
rather than a Calculator<T>, which is convenient, since that's the class we
passed into it.
Ultimately, we end up with a version of Sum that uses the int calculator to do its
operations.
That gives us a workable scheme, though it is a bit ugly because we have to create
the calculator and pass it in. The neat way that Anders came up to get around this
is to use a pattern-based approach, and use reflection. We first look for the calculator
class off of the type, and if we don't find it, we look in the standard place. This
means that you can have the AlgorithmLibrary constructor find the right calculator
for us.
This all worked out fairly well. I'd show you the whole code, but I'm not quite happy
with it, and I'm not sure it would run on the PDC bits, so you'll probably have to
wait for a while. Here's a sample of using it:
List<double> ld = new List<double>();
ld.Add(1.5);
ld.Add(333333.3333);
ld.Add(2882.888);
ld.Add(222);
AlgorithmLibrary<double> cd = new AlgorithmLibrary<double>();
Console.WriteLine("Sum is {0}", cd.Sum(ld));
Console.WriteLine("Mean is {0}", cd.Mean(ld));
Console.WriteLine("SD is {0}", cd.StandardDeviation(ld));
One concern with this approach is performance. I did a few quick benchmarks, and for
lists, this approach takes about 50% longer than coding it by hand. For arrays, it's
about twice as slow. I think the major problem is the virtual function, but there
may be a way to make that faster.
