使用泛型进行计算

Rüdiger Klaehn

4.94/5 (136投票s)

2004年10月11日

6分钟阅读

540779

3167

使用泛型类型进行计算并不像看起来那么容易。本文展示了如何做到这一点。

下载演示项目 - 32.8 Kb

引言

.NET 泛型的当前实现主要用于使类型安全的集合更快、更易于使用。对泛型类型进行计算并不像看起来那么直接。

问题所在

对泛型类型进行计算的一个例子是，计算 List<T> 中所有元素的总和的泛型方法。当然，只有当 T 是像 int、double、decimal 这样定义了加法运算的类型时，对列表中的所有元素求和才有意义。

来自 C++ 背景的人可能会像这样实现这样的方法

public class Lists {
    ...
    public static T Sum(List<T> list) 
    {
        T sum=0;
        for(int i=0;i<list.Count;i++)
            sum+=list[i];
        return sum;
    }
    ...
}

这在 C# 中是不可能的，因为未经约束的类型参数被假定为 System.Object 类型，该类型不定义 + 操作。

要在 C#/.NET 中约束类型参数，需要指定类型必须实现的接口。问题是接口不能包含任何静态方法，而运算符方法是静态方法。

因此，在当前的约束系统下，无法定义运算符约束。

启用数值计算的一个简洁方法是让基本数据类型，如 int、float、double、decimal 等实现算术运算的接口。然后可以使用该接口来约束类型参数。这将类似于所有基本数据类型都实现的 IComparable<T> 接口。

我曾试图说服微软的人实现这样一个接口，但显然他们赶不上 Whidbey 发布。

我们只能靠自己了

许多人一直在思考这个问题，其中包括 Eric Gunnerson 甚至 Anders Hejlsberg。

Anders Hejlsberg 提出的解决方案是使用一个抽象类 Calculator<T>，该类必须为每种基本类型进行专门化。然后泛型类型将使用适当的计算器的实例来进行计算。

这是代码（从 Eric Gunnerson 的博客复制）

首先定义抽象基类

public abstract class Calculator<T>
{
    public abstract T Add(T a, T b);
}

然后专门化您要进行计算的类型

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

然后使用适当的 Calculator<T> 来进行计算。下面是一个计算 List<T> 中所有元素总和的示例。

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;
    }
}

您会这样使用它

AlgorithmLibrary library = new AlgorithmLibrary<int>(new Int32.Calculator());

还有许多其他富有创意的解决方案，但它们都有一个缺点，那就是涉及某种形式的动态方法调用（虚方法、接口或委托）。因此，虽然它们使得使用泛型参数进行计算成为可能，但对于数值应用来说，性能是不可接受的低。

解决方案

第一个提出不涉及任何虚方法调用的解决方案的人是 Jeroen Frijters。该解决方案利用了“使用接口约束类型参数与转换为接口不同”这一事实。通过接口调用方法会产生动态方法分派的开销，但调用由接口约束的类型参数上的方法则没有这种开销。

这是一个例子。它是一个对两个数字进行排序的泛型方法。类型 T 必须实现 IComparable<T>，这样我们才能确保它具有 CompareTo 方法。但是，调用 CompareTo 方法并没有通常与接口相关的开销。

public class Sorter
{
    private static void Swap<T>(ref T a, ref T b)
    {
        T t=a;a=b;b=t;
    }
    public static void Sort<T>(ref T a,ref T b)
        where T:IComparable<T>
    {
        if(a.CompareTo(b)>0)
            Swap(ref a,ref b);
    }
}

Jeroen Frijters 提出的方法使用第二个类型参数。为了避免不必要的对象创建和虚方法分派，最好使用值类型来存储操作。下面是这种方法的一个小示例

interface ICalculator<T> 

{ 
    T Sum(T a,T b); 

} 

struct IntCalculator : ICalculator<int> 

{ 
    public int Add(int a,int b) { return a+b; } 

} 

// struct FloatAdder ... 

// struct DoubleAdder ... 

class Lists<T,C>
    where T:new() 
    where C:ICalculator<T>,new();{
    //since C is a struct with zero size, we can create an instance
    //of C whenever we need one without any overhead.
    private static C calculator=new C();
    public static T Sum(List<T> list) 
    { 
        T sum=new T();
        for(int i=0;i<list.Count;i++)
            sum=calculator.Add(sum,list[i]); 
        return sum; 
    } 

}

由于第二个类型参数，这个类的使用有点笨拙。但您可以使用别名。下面是如何使用 Lists<T,C> 类型

using IntLists=Lists<int,IntCalculator>;
//...
List<int> list=new List<int>();
list.Add(1);
list.Add(2);
list.Add(3);
Console.WriteLine("The sum of all elements is {0}",
IntLists.Sum(list));

性能

由于我们确保我们的代码不包含任何虚方法调用或不必要的对象创建，因此泛型代码的速度应该与非泛型代码完全相同。为了测试这一点，我写了一个小的基准测试。结果令人鼓舞。即使是目前非常有限的 JIT 编译器也能内联 Sum 方法，因此在我的机器上，泛型版本确实与非泛型版本一样快。

请确保在发布模式下运行基准测试，因为在调试模式下，许多非常重要的优化（如方法内联）是禁用的。

对类型参数使用运算符

现在我们可以以可接受的性能对泛型类型进行计算。但我们仍然不能对类型参数使用运算符。在上面的示例中，我们不得不写 sum=calculator.Add(sum,list[i]) 而不是简单地写 sum+=list[i]。

如果您只想执行简单的加法，这可能没什么大不了的。但如果您有大量使用运算符的方法，将其转换为使用方法调用将是一个繁琐且容易出错的过程。

幸运的是，可以创建一个包装器 struct，它定义了运算符。通过使用到和从包装器类型的隐式转换，我们可以几乎透明地使用这个包装器 struct。

上面的 ICalculator 接口的包装器 struct 可能看起来像这样

public struct Number<T,C>
    where C:ICalculator<T>,new()
{
    private T value;
    private static C calculator=new C();
    private Number(T value) {
        this.value=value;
    }
    public static implicit operator Number<T,C>(T a)
    {
        return new Number<T,C>(a);
    }
    public static implicit operator T(Number<T,C> a)
    {
        return a.value;
    }
    public static Number<T,C> operator + (Number<T,C> a, Number<T,C> b)
    {
        return calculator.Add(a.value,b.value);
    }
    ...other operators...
}

现在，在您的泛型类中，您将使用包装器 struct 而不是 T。下面是使用包装器 struct 的 Sum 示例的样子

class Lists<T,C>
    where T:new()
    where C:ICalculator<T>,new()
{
    public static T Sum(List<T> list)
    {
        Number<T,C> sum=new T();
        for(int i=0;i<list.Count;i++)
            sum+=list[i];
        return sum;
    }
}

您可能期望这段代码的运行速度与非运算符版本完全相同。但遗憾的是，事实并非如此。当前的 .NET JIT 编译器有一些非常严重的限制。基本上，它不会对具有显式结构参数的方法进行任何内联（是的，我也很震惊）。

由于包装器 struct 中的运算符方法具有 struct 参数，因此它们不会被内联，性能会受到影响。但我相信微软很快就会修复这个重要的性能问题。

这里有一个关于这个话题的建议，您可以投票。这是 C# 中实现闪电般快速且易于使用的数值计算所缺少的唯一东西。

结论

尽管 .NET 泛型系统的约束语法非常有限，但通过使用第二个类型参数可以绕过这些限制。这种方法对于泛型类库的编写者来说需要更多的工作，但对于类库的用户来说却相当透明，并且性能与非泛型版本相同。就像 C++ 模板一样，抽象的运行时成本为零。

存在一些限制，但这些限制应该很快会消失，因为微软和竞争供应商正在提高 JIT 编译器的性能。因此，可以编写与 C++ STL 等编译时模板库一样快甚至更快的数值库。

关于代码

包含的项目包括所有基本类型的接口、实现和包装器，以及一些不错的附加功能。列表基准测试使用泛型和非泛型方法计算大型列表的标准差。另一个基准测试比较了非泛型 System.Drawing.Point 和 System.Drawing.PointF struct 与泛型 Point<T> 版本的性能。

代码采用 BSD 许可证，因此可以自由用于您自己的项目。

参考文献

Anders Hejlsberg 提出了使用抽象基类。
一种解决方案使用动态方法生成。
Jeroen Frijters 提出使用值类型作为计算器。
这是我关于该主题的第一篇帖子。您可能注意到，我当时非常生气...
在这里我将发布代码的新版本。
我关于该主题的两篇文章发表在 osnews 上。
请投票支持这个建议。它比总统选举更重要 :-)