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.

 

Comments (15)

  1. Olivier says:

    You can avoid virtual with:
    public interface ICalculator<T>
    {
    T Add(T a, T b);
    }

    class AlgorithmLibrary<T, IC>
    where T: new()
    where CT: ICalculator<T>
    {
    CT calculator;

    public AlgorithmLibrary(CT 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;
    }
    }
    namespace Int32
    {
    public class Calculator: ICalculator<int>
    {
    public int Add(int a, int b)
    {
    return a + b;
    }
    }
    }
    but i don’t yet have received Whidbey to compare performance.

  2. While the solution does not strike me as anything incredibly new (think STL), the only way you will get it to work (and I mean work in the sense of acceptance) is if you create your own algorithm library, with skeletons required (abstract classes and interfaces) to inject our own custom types into the algorithms.

    I don’t remember if it was you or someone else from MS, but it was said that the only way that something like this is effective is if there is universal coverage, which has more potential to lead to universal adoption.

    Based on that, my question would be, are you going to create such an algorithm library, along the lines of STL, and if so, what kinds of algorithms are you going to create?

  3. Eric says:

    Thanks, Olivier. I had thought about trying interfaces, but hadn’t gotten around to it yet.

  4. (luKa) says:

    Wouldn’t be possible to have a constraints for a type parameter to specifie a required member (a method, an operator, ecc) just like this?

    namespace Int32
    {
    public class Calculator<T>
    where T: T Add(T, T)
    {
    public T Add(T a, T b)
    {
    return a + b;
    }
    }
    }

    TIA (luKa)

  5. (luKa) says:

    Ops… I was meaning this

    class AlgorithmLibrary<T>
    ….where T: new(), T Add(T, T)
    {
    ….// …
    }

  6. andrew queisser says:

    luKa, I think you’re pointing out the fundamental problem with generic algorithms in C#. There’s no way to do anything inside a generic algorithm unless you specify an exact type or interface. That puts the burden on the caller of the generic algorithm to pass in a the type needed by the algorithm. That’s the exact oppositie of a "generic" algorithm. Looks like several people are thinking about how to get around this problem (see Eric’s post above).

    Andrew Queisser