Hello World
Spiga

“表达式树”配合“泛型参数字典”定义通用操作

2009-11-13 13:53 by 老赵, 17426 visits

上午有朋友提出了这么一个问题:如何定义一个通用的相加操作。这样的话,我们就可以定义如下的扩展方法了:

public static class EnumerableExtensions
{
    public static T Sum<T>(this IEnumerable<T> source)
    {
        T sum = default(T);
        bool first = true;

        foreach (var item in source)
        {
            if (first)
            {
                sum = item;
                first = false;
            }
            else
            {
                sum += item;
            }
        }

        return sum;
    }
}

这个扩展方法的作用便是计算出source中所有的T类型元素之和——显然,上面标红的那行代码是无法编译通过的,因为并非所有的类型都有“相加”操作。因此,我们要设法实现这个功能。这又是“泛型参数字典”的用武之地了,当然更关键的其实是“表达式树”的“编译”功能:

public static class AddOperation<T>
{
    static AddOperation()
    {
        var x = Expression.Parameter(typeof(T), "x");
        var y = Expression.Parameter(typeof(T), "y");
        var add = Expression.Add(x, y);
        var lambda = Expression.Lambda<Func<T, T, T>>(add, x, y);
        s_add = lambda.Compile();
    }

    private static Func<T, T, T> s_add;

    public static T Add(T x, T y)
    {
        return s_add(x, y);
    }
}

无论是什么类型,“相加”操作的表达式都是“Add”,因此从表达式树的角度来说它们是完全相同的。因此,我们只要使用表达式树进行Compile得到的结果,自然可以应对各种情况。很显然,性能也是非常高的——这是“泛型参数字典”和“表达式树”共同努力的结果。那么来尝试一下:

public struct Complex
{
    public int m_real;
    public int m_imaginary;

    public Complex(int real, int imaginary)
    {
        this.m_real = real;
        this.m_imaginary = imaginary;
    }

    public static Complex operator +(Complex c1, Complex c2)
    {
        return new Complex(c1.m_real + c2.m_real, c1.m_imaginary + c2.m_imaginary);
    }
    
    public override string ToString()
    {
        return (String.Format("{0} + {1}i", m_real, m_imaginary));
    }
}

// 调用
AddOperation<int?>.Add(3, 5);
AddOperation<double>.Add(3.5, 6.8);
AddOperation<Complex>.Add(new Complex(1, 2), new Complex(2, 3));

可见,无论是Nullable Int32,Double还是使用自定义“+”操作符的Complex类型,AddOperation类都能正常工作。只可惜字符串不行——因为编译器其实是将字符串相加编译为String.Concat方法的调用,而String类型本没有“相加”操作。因此,我们AddOperation需要进行修改,补充一个特殊情况:

static AddOperation()
{
    if (typeof(T) == typeof(string))
    {
        Func<string, string, string> strAdd = (x, y) => x + y;
        s_add = (Func<T, T, T>)(object)strAdd;
    }
    else
    {
        var x = Expression.Parameter(typeof(T), "x");
        var y = Expression.Parameter(typeof(T), "y");
        var add = Expression.Add(x, y);
        var lambda = Expression.Lambda<Func<T, T, T>>(add, x, y);
        s_add = lambda.Compile();
    }
}

如果T是字符串,那么我们“强行”指定一个加法的实现,至于其他情况,那还是最最普通的Add操作了。那么,还有哪些类型是需要特殊处理的呢?嗯……我还想到了“委托”……还有吗?

于是乎,我们的通用Sum方法便可以这样实现了:

public static T Sum<T>(this IEnumerable<T> source)
{
    T sum = default(T);
    bool first = true;

    foreach (var item in source)
    {
        if (first)
        {
            sum = item;
            first = false;
        }
        else
        {
            sum = AddOperation<T>.Add(sum, item);
        }
    }

    return sum;
}

感觉如何?是不是比.NET框架中定义的Enumerable.Sum扩展方法要强大许多呢?

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

32 条回复

  1. Leon Weng
    *.*.*.*
    链接

    Leon Weng 2009-11-13 14:10:00

    表达式树,恩,为什么我没有用到呢?

  2. 温景良(Jason)
    *.*.*.*
    链接

    温景良(Jason) 2009-11-13 14:21:00

    一直不太会使用表达式树,更不能用它来为我们构造好的代码

  3. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-11-13 14:22:00

    表达式树,恩,为什么我没有用到呢?

  4. ruson
    *.*.*.*
    链接

    ruson 2009-11-13 14:29:00

    感谢,这个一定要顶.

  5. 老赵
    admin
    链接

    老赵 2009-11-13 14:33:00

    温景良(Jason):一直不太会使用表达式树,更不能用它来为我们构造好的代码


    其实感觉就两点作用:
    1、强类型的高级语言表达形式。
    2、简化Emit工作。

  6. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-11-13 14:36:00

    一直手工Emit的飘过。。。。。。。

  7. 老赵
    admin
    链接

    老赵 2009-11-13 14:42:00

    @Ivony...
    拜大牛

  8. Joyaspx
    *.*.*.*
    链接

    Joyaspx 2009-11-13 14:49:00

    老赵用Lambda表达式和泛型真是倒了炉火纯青的地步了^_^

  9. 黄明
    *.*.*.*
    链接

    黄明 2009-11-13 14:51:00

    一直想使用 表达式 无奈没有时间好好深入。顶一个。

  10. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-11-13 14:59:00

    Jeffrey Zhao:
    @Ivony...
    拜大牛




    汗到死。。。。

    我只是觉得写表达式树太费键盘了而已。。。



    这个东西记得脑袋以前也做过的么,这个,似乎比脑袋的更先进些了,用表达式树来自动选择运算符重载或是IL。

    嗯嗯,这才是表达式树完全适用场景,手工Emit的话,判断运算符重载就不美了。。。


    脑袋的:
    http://www.cnblogs.com/Ninputer/archive/2006/04/14/374921.html

  11. 老赵
    admin
    链接

    老赵 2009-11-13 15:04:00

    @Ivony...
    发现我原来看过这篇,但是忘了……看VB好累……

  12. 韦恩卑鄙 alias:v-zhewg
    *.*.*.*
    链接

    韦恩卑鄙 alias:v-zhewg 2009-11-13 15:09:00

    表达式树,恩,为什么我没有用到呢?

  13. ruson
    *.*.*.*
    链接

    ruson 2009-11-13 15:26:00

    我要求的并不是T=T+T的形式, 而是TResult=T+T的形式,具体的TResult以及要取对象中的哪些值来相加是由func来决定的。 不过参考您的代码做成如下形式ok。
    感谢!

    /// <summary>
        /// 对 Enumerable 的相关扩展。
        /// </summary>
        public static class EnumerableExtensions
        {
            /// <summary>
            /// 遍历列表中的每一个项,并返回每项通过func处理返回值相 + 的结果。
            /// </summary>
            /// <typeparam name="TResult"></typeparam>
            /// <param name="source"></param>
            /// <param name="func"></param>
            /// <returns></returns>
            public static TResult AddResultEach<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> func)
            {
                TResult result = default(TResult);
                bool first = true;
    
                foreach (var item in source)
                {
                    if (first)
                    {
                        result = func.Invoke(item);
                        first = false;
                    }
                    else
                    {
                        result = AddOperation<TResult>.Add(result, func.Invoke(item));
                    }
                }
    
                return result;
            }
        }
    
        /// <summary>
        /// 处理通用类型的相关操作。
        /// </summary>
        /// <typeparam name="T"></typeparam>
        public static class AddOperation<T>
        {
            static AddOperation()
            {
                if (typeof(T) == typeof(string))
                {
                    var strAdd = new Func<string, string, string>((x, y) => x + y);
                    add = (Func<T, T, T>)(object)strAdd;
                }
                else
                {
                    var x = Expression.Parameter(typeof(T), "x");
                    var y = Expression.Parameter(typeof(T), "y");
                    var body = Expression.Add(x, y);
                    var lambda = Expression.Lambda<Func<T, T, T>>(body, x, y);
                    add = lambda.Compile();
                }
            }
    
            private static Func<T, T, T> add;
    
            public static T Add(T x, T y)
            {
                return add(x, y);
            }
        }
    


    应用场景可能如下
    protected void Page_Load(object sender, EventArgs e)
        {
            var list = new List<PassengerInfo>
            {
                new PassengerInfo { Age = 5 },
                new PassengerInfo { Age = 10 },
                new PassengerInfo { Age = 20 },
                new PassengerInfo { Age = 50 }
            };
            Response.Write(list.AddResultEach((item) =>
            {
                return string.Format("<umAge>{0}</umAge>", item.Age);
            }).HtmlEncode());
        }
    

  14. ruson
    *.*.*.*
    链接

    ruson 2009-11-13 15:30:00

    那样显的比较简洁可以省略代码中的很多
    foreach类的循环或处理方法。

  15. 老赵
    admin
    链接

    老赵 2009-11-13 15:32:00

    @ruson
    关键就在于通用的Add操作,具体怎么用就无所谓了……

    其实我觉得,你的AddResultEach封装多了,其实用Select和Sum正好,呵呵。

    var sum = source.AddResultEach(x => ...)
    var sum = source.Select(x => ...).Sum()

    或者直接写成Sum的重载:
    var sum = source.Sum(x => ...);

    还有就是,你的示例代码,我一般会写成这样:
    list.Sum(item => "<umAge>{0}</umAge>".FormatWith(item.Age));

  16. 鹤冲天
    *.*.*.*
    链接

    鹤冲天 2009-11-13 15:55:00

    太棒了,没想到还可以这样。
    要好好学习一下表达式树!

  17. 鹤冲天
    *.*.*.*
    链接

    鹤冲天 2009-11-13 15:59:00

    正准备写一篇扩展方法与T4相结合的文章,这下要换换思路了。

  18. 木野狐(Neil Chen)
    *.*.*.*
    链接

    木野狐(Neil Chen) 2009-11-13 16:08:00

    为了这个功能感觉有点 overkill.. 不过锻炼编程技巧是有帮助的。
    其实就像 System.Linq.Enumerable.Aggregate 那些方法一样传入 add 的委托不也蛮好的~

  19. 老赵
    admin
    链接

    老赵 2009-11-13 16:36:00

    @木野狐(Neil Chen)
    这也是,只略微烦一点而已。

  20. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-11-13 16:47:00

    我2005年的VBF中包含类似逻辑,知道我的前瞻性了吧。。虽然那时候还没有表达式树,但是我用了动态对象,这个直到今天才被C#er奉为
    “新特性”的技术,来支持运算符重载……

  21. 麒麟.NET
    *.*.*.*
    链接

    麒麟.NET 2009-11-13 16:49:00

    装配脑袋:我2005年的VBF中包含类似逻辑,知道我的前瞻性了吧。。


    嗯,大家一起出来看上帝……

  22. 老赵
    admin
    链接

    老赵 2009-11-13 16:57:00

    @装配脑袋
    被脑袋鄙视了,55555

  23. 近近
    *.*.*.*
    链接

    近近 2009-11-13 17:06:00

    棒极了,简短明了。没有对象自己的操作符重载,是不是那个add就不能对对象起作用了。

  24. 老赵
    admin
    链接

    老赵 2009-11-13 17:15:00

    @近近
    那是,你总归该提供一个可以Add的东西。
    当然,这点在编译期是没法检测到的,只是会跑出异常。

  25. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-11-13 20:26:00

    呃,,,,,我真的不得不承认,类型字典这个玩意儿的潜力即使在脑袋的论文发表四年后还没有被完全的发掘。



    最近遇到了一个和泛型相关的有意思的问题,怎么收缩泛型类。

    简单的说有一个泛型类Type<T>。那么很显然,Type<T>并不是所有的成员都与T有关(例如IList<T>.Count),那么我们显然会有一些需求针对类型Type<T>,T可以为任意类型。但糟糕的是,这些功能并没有一个非泛型基类涵盖(例如IList<T>就不扩展接口IList)。那么对于不同的T而言,Type<T>是不同的类型。

    如果只是一个方法还好办,我们可以用泛型方法来应付,如Method<T>( Type<T> obj )
    然后在方法内完全忽略掉这个T就可以了。

    比如说:

    public int GetCount<T>( IList<T> list )
    {
      return list.Count;
    }
    


    但是如果我们要把这个Type<T>的实例保存到字段,就非常麻烦!

    因为我怎么知道这个字段的类型是什么?除非我们的类型是泛型的,否则我们没法定义这个字段的类型。Type?还是Type<>?或者Type<T>?

    但如果这个Type<T>只是类型的一小部分,我们把整个类型都变成泛型就很不划算,而且这只会使得问题向上传播,使用我们这个类型的类型,原来面对的是一个非泛型类,现在突然变成了一个泛型类。

    我发现委托或内部类都可以解决这个问题,总觉得不够优美。

    正好大牛们都在,,,,,看能不能找到一个优美的解决方案?

  26. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-11-13 21:09:00

    @Ivony...

    提取一个非泛型的基类。。我一直用这种做法
    Java那个Type<?>根本就是骗人的。。。

  27. ProjectDD
    *.*.*.*
    链接

    ProjectDD 2009-12-23 08:09:00

    我觉得 表达式树就是codedom的运行时应用,结合成一个委托,再利用上泛型,让它变得,很好,很强大。

  28. straybird
    219.136.28.*
    链接

    straybird 2010-05-21 15:02:07

    表达式树很奇妙啊,开阔思维,非常感谢。用IEnumerable接口下的Aggregate迭代器,帮赵老师写了个简洁版的。

    Complex[] array = new Complex[] { new Complex(1, 2), new Complex(2, 3), new Complex(3, 4) };
    Complex result = array.Aggregate<Complex>((x, y) => new Complex(x.m_real + y.m_real, x.m_imaginary + y.m_imaginary));
    
    int[] array2 = new int[] { 1, 2, 3, 4 };
    int result2 = array2.Aggregate<int>((x, y) => x + y);
    
    string[] array3 = new string[] { "1", "2", "3", "4" };
    string result3 = array3.Aggregate<string>((x, y) => x + y);
    
  29. stevey
    116.226.7.*
    链接

    stevey 2012-05-24 14:25:05

    哇,之前在InfoQ上看到老赵一篇,今又看到这篇。从中学习到很多,无法用言语表达感激之情^_^ 原来这种(泛型类中静态字段存储)实践,还有个称呼“泛型参数字典”,膜拜!学习ing

    附上我之前总结的一篇,超级模仿老赵做法,有时间的话给个意见吧。 [Expression Tree实践之通用Parse方法------"让CLR帮我写代码"]

  30. Scan
    119.130.187.*
    链接

    Scan 2014-11-17 01:23:03

    这最终方案,感觉是在给自己添堵

    首先,老赵想要为每种类型,特化独立的“Add”操作,这思路没错。问题是,最终方案中,仍然是通过委托来实现的。它限定了,“每种类型只能有一种操作”这样的1-1对应关系,又没能从中得到性能上的受益。

    如果是在C++中,通过为不同的类型重载不同的Add(T)实现(或者说特化),于是不同类型的Sum在内联Add后得到不同的代码,进而性能得到提升。 这里的Add因为静态决议,得以内联优化,可算是牺牲一定的灵活性得到性能补偿的选择。 C++ STL的algorithm大量的使用functor而不是函数指针,是为每种类型特化算法从而优化性能的典范。

    所以说,既然老赵最终的方案,也相当于是在调用函数指针,那么,为何要做“类型-行为”的绑定? 我觉得这样就够了:(忽略算法上的细微差别)

    public static T Sum<T>(T[] source, Func<T, T, T> add) { 
            T r = default(T);
            foreach (var v in source) r = add(r, v);
            return r;
        }
    

    一次迭代,同样付出O(n)的调用委托的开销。

    这实际上也就是Enumerable.Aggregate。所以,一句话就好:

    ints.Aggregate((a,b)=>a+b)
    
  31. Scan
    119.130.187.*
    链接

    Scan 2014-11-17 02:01:49

    实际上C#也真能做静态绑定,这样:

    public interface IFoldOperator<T> {
            T Op(T a, T b);
        }
        public static T Fold<T, TOp>(T[] values, TOp op) where TOp: IFoldOperator<T> {
            T r = default(T);
            foreach (var v in values) r = op.Op(r, v);
            return r;
        }
        public class FoldOperator_AddInt: IFoldOperator<int> {
            public int Op(int a, int b) {
                return a + b;
            }
        }
    

    调用的时候:

    Fold(ints, new FoldOperator_AddInt());
    

    由于这行调用,实际上执行的是“Fold<int, FoldOperator_AddInt>“

    这样,泛型Fold中那句“op.Op”,其实就能明确的在编译期决议为“FoldOperator_AddInt.Op”,于是有可能内联了。

    虽然原来的委托调用,也有可能被JIT编译器内联,但上面这个用法,AOT编译器就有能力做内联优化了,我觉得可以期待后面的这个方案跑得更快。

    我测试了一下,上面这个方案确实比用委托更快( 快50%以上;而老赵你的emit,和直接传入delegate参数的Enumerable.Aggregage,一样快),可惜还是比不上直接用加法,看来C#编译器生成的代码仍然不够好...

  32. Scan
    119.130.187.*
    链接

    Scan 2014-11-17 02:06:04

    说不定如果.Net的字典的声明是“Dictionary<TKey, TValue, TEqualityComparer>”,有可能更快呢

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我