dedecms网站别名解析,网络整合营销推广,自助餐团购网站建设,温州网络公司推广前言 著名的牛顿同学曾经说过#xff1a;如果说我比别人看得更远些,那是因为我站在了巨人的肩上. 原文#xff1a;If I have been able to see further, it was only because I stood on the shoulders of giants. Whats Lambda表达式? 请参考msdn#xff1a;Lambda 表达式…前言 著名的牛顿同学曾经说过如果说我比别人看得更远些,那是因为我站在了巨人的肩上. 原文If I have been able to see further, it was only because I stood on the shoulders of giants. Whats Lambda表达式? 请参考msdnLambda 表达式C# 编程指南 Lambda表达式编写递归函数? How? 建议没有看过老赵的《使用Lambda表达式编写递归函数》这篇文章的朋友请先前往围观你会受益匪浅。 原文实现如下的递归效果 var fac Fixint, int(f x x 1 ? 1 : x * f(x - 1));
var fib Fixint, int(f x x 1 ? 1 : f(x - 1) f(x - 2));
var gcd Fixint, int, int(f (x, y) y 0 ? x : f(y, x % y)); 颇有意思能够把递归发挥到这种极致。更有意思的是Fix这个简短而又神秘莫测的方法 static Func Fix(FuncFunc, Func f)
{return x f(Fix(f))(x);
}
static Func Fix(FuncFunc, Func f)
{return (x, y) f(Fix(f))(x, y);
} Oh my god! 这是人类写的代码吗 据原文介绍此得意之作是装配脑袋的脑袋想出来的。至于有兴趣且希望前往一窥究竟的朋友我先给大家打个预防针——首先选择你一天中最清醒的时候最好带上氧气瓶以防由于其大师级的文章而可能造成短暂性的脑缺氧... 装配脑袋的两篇大师级文章1. VS2008亮点用Lambda表达式进行函数式编程 和 2. 用Lambda表达式进行函数式编程续用C#实现Y组合子 人在江湖高手如云。葵花宝典如来神掌此乃上乘武功高手行走江湖的必杀技。我等后辈深知神功非一日可练就日夜苦练。幸好鄙人天资聪慧一日秋高气爽幸见两位大师切磋比试深得大师真传练就“抛砖引玉”神功我抛我抛——大家请接好 -.-! 抛的是什么砖 前面由Lambda表达式使出的一招函数式编程经润色成递归函数犹如手握屠龙刀一般登峰造极今日我略懂窍门奉上倚天剑与屠龙刀集一身可谓无懈可击。 大家发现前面实现的3个递归函数有什么共同点吗没错都是有返回值的。因为 Fix 返回的是 Func 或 Func 类型换句话说 TResult 就是递归结束后期望返回的类型。如果是无返回值的递归呢好的聪明的你此刻应该知道又是Action 出场了。 没错我们要做的事情就是让 Fix 返回 Action 。当然和前面的不一般的 Func 一样 Action 也不是等闲之辈。 x f(Fix(f))(x) 是的我一不小心写了一个(实际上是照葫芦画瓢) public static Action Fix(FuncAction, Action f)
{return x f(Fix(f))(x);
}
public static Action Fix(FuncAction, Action f)
{return (x, y) f(Fix(f))(x, y);
} 好的在你还没被以上代码弄晕之前我先举一个大家都熟悉的例子——二叉树遍历 二叉树是我大学时学数据结构最感兴趣的一部分另一个感兴趣的是教我数据结构的女老师 先来回顾一下二叉树的一般递归算法如中序遍历算法可用经典的C语言描述为 void InOrder(BinTree T)
{ if(T)// 如果二叉树非空{ InOrder(T-lchild)printf(cT-data) // 访问结点InOrder(T-rchild);}
} // InOrder 题外话想当年我用C语言费了多少时间不断写二叉树的结构和遍历请注意不是照搬书本的代码。多少次内存溢出多少次与指针作斗争了解忘记再了解又忘记... 现在如果让我来用C语言写二叉树遍历可能写出的代码会把编译器吓跑嘿嘿。何况此宝地乃.Net 牛人的汇集之地更何况我想写的是泛型二叉树 泛型二叉树 class Node
{public T Value { get; set; }public Node Left { get; set; }public Node Right { get; set; }public Node(){ }public Node(T value): this(value, null, null){ }public Node(T value, T left, T right): this(value, new Node(left), new Node(right)){ }public Node(T value, Node left, Node right){Value value;Left left;Right right;}
} 老实说在实现手动构造二叉树时我不知道如何写尽量少的代码并且这些代码还要能够清晰反映树的结构。为此我唯一想到的是类似XElement那样它写出的代码是树形的让人从代码可以联想到对象的结构。 现在我们试着用 Node 来构造以下的二叉树 /*建立一棵简单的二叉树A/ \B C/ / \D E F*/
static Nodechar BuildTree()
{return new Nodechar(A,new Nodechar(B,new Nodechar(D), null),new Nodechar(C, E, F));
} 以上代码始终不够理想too many Node期待更好的构造二叉树写法 请原谅我带大家兜了一圈花园现在回到刚才的非人类写的代码 public static Action Fix(FuncAction, Action f)
{return x f(Fix(f))(x);
} 结合刚才的二叉树现在装配以上代码来实现对二叉树的三种遍历——中序先序和后序 var inorder FixNodechar(f n { if (n ! null) { f(n.Left); Console.Write(n.Value); f(n.Right); } });
var preorder FixNodechar(f n { if (n ! null) { Console.Write(n.Value); f(n.Left); f(n.Right); } });
var postorder FixNodechar(f n { if (n ! null) { f(n.Left); f(n.Right); Console.Write(n.Value); } });
Nodechar tree BuildTree();
Console.WriteLine(1 中序序列inorder traversal);
inorder(tree);
Console.WriteLine();
Console.WriteLine(2 先序序列preorder traversal);
preorder(tree);
Console.WriteLine();
Console.WriteLine(3 后序序列postorder traversal);
postorder(tree);
Console.WriteLine(); 运行后的效果 大家可以在脑里对结果进行验证一下或点此查看 其实以上代码的关键部分f n { if (n ! null) { f(n.Left); Console.Write(n.Value); f(n.Right); } } 跟我们的思维还是类似的。如果你不习惯这种写法也可以写成多行的形式 f n {if (n ! null){f(n.Left);Console.Write(n.Value);f(n.Right);}}); f 是 Action 类型可以理解为将要实现递归的委托 n 是 T类型在本文它是 Nodechar 类型是当前遍历的节点。 f(n.Left) 和 f(n.Right) 也就很好理解了就是访问左右节点。 多参数 对于多参数的情况如 f (arg1, arg2) { ... } 虽然上述方法也可以“凑合”着用例如可以改成单参数的形式 object arg2; f arg1 {use arg2 to do sth... } 但是这样一来其中一个弊端就是f arg1 {use arg2 to do sth... }不能单独抽取出来进行复用意味着它的使用范围变窄了。因为如刚才的中序遍历并不一定在方法里构造相应的委托大可“搬”到方法外面去。 例如 var inorder FixNodechar(...); “搬”出去以后 public static ActionNodechar inorder FixNodechar(...); 因此完全有必要重载 Fix 方法提供多参数的形式。 文章开端已经列出了2个参数的重载方法 public static Action Fix(FuncAction, Action f)
{return (x, y) f(Fix(f))(x, y);
} 现在使用上述方法来写一个递归遍历指定目录的所有子目录并记录这些目录到一个List 对象里 var traversal_help Fixstring, Liststring(f (current, pathList)
{//添加当前目录到pathListpathList.Add(current);//访问当前目录的文件夹foreach (string path in Directory.GetDirectories(current)){//递归调用f(path, pathList);}
});
Liststring result new Liststring();
traversal_help(C:\\, result); 重载 (纯Action版) x f(Fix(f), x) Oh my god! 又是非人类写的代码 是的我又一不小心写了另外一个版本 public static Action Fix(ActionAction, T f)
{return x f(Fix(f), x);
}
static Action Fix(ActionAction, T1, T2 f)
{return (x, y) f(Fix(f), x, y);
} 以上两个方法已经彻底见不到 Func 的踪影了我谓之为“纯Action”版跟前一个版本同样是实现无返回值的递归调用。 使用上也极其简单这里还是拿二叉树遍历来说明 var inorder FixNodechar((f, n) { if (n ! null) { f(n.Left); Console.Write(n.Value); f(n.Right); } });
var preorder FixNodechar((f, n) { if (n ! null) { Console.Write(n.Value); f(n.Left); f(n.Right); } });
var postorder FixNodechar((f, n) { if (n ! null) { f(n.Left); f(n.Right); Console.Write(n.Value); } }); 这种写法其实跟前一种写法只有很小的差别 f n ... 写成(f, n) ... 同理多参数的情况: f (n1, n2) ... 写成(f, n1, n2) ... 没错如此而已。这里我想问问大家更乐于使用哪种写法呢 性能比较 两个版本在性能上区别会不会有很大区别 使用计时器 CodeTimer 测试代码 var inorder1 FixNodechar(f n { if (n ! null) { f(n.Left); f(n.Right); } });
var inorder2 FixNodechar((f, n) { if (n ! null) { f(n.Left); f(n.Right); } });
Nodechar tree BuildTree();
CodeTimer.Initialize();
new Listint { 10000, 100000, 1000000 }.ForEach(n
{CodeTimer.Time(Fix v1 * n, n, () inorder1(tree));CodeTimer.Time(Fix v2 * n, n, () inorder2(tree));
}); 测试代码其实就是二叉树中序遍历只是打印节点的语句被去掉即去掉 Console.Write(n.Value) 。 两个版本分别执行一万十万及一百万次得到的测试结果是 Fix v1 * 10000 Time Elapsed: 413ms CPU Cycles: 897,224,108 Gen 0: 10 Gen 1: 0 Gen 2: 0 Fix v2 * 10000 Time Elapsed: 308ms CPU Cycles: 671,960,256 Gen 0: 5 Gen 1: 0 Gen 2: 0 Fix v1 * 100000 Time Elapsed: 3,118ms CPU Cycles: 6,796,717,873 Gen 0: 109 Gen 1: 0 Gen 2: 0 Fix v2 * 100000 Time Elapsed: 3,061ms CPU Cycles: 6,680,823,182 Gen 0: 54 Gen 1: 1 Gen 2: 0 Fix v1 * 1000000 Time Elapsed: 31,358ms CPU Cycles: 67,992,085,293 Gen 0: 1090 Gen 1: 3 Gen 2: 0 Fix v2 * 1000000 Time Elapsed: 31,576ms CPU Cycles: 68,836,391,613 Gen 0: 545 Gen 1: 3 Gen 2: 0 结果显示两个版本在速度上旗鼓相当而“纯Action”版在GC上优于前者。 多参数的VS智能提示问题 上述代码从理论上和实际上来说都是没问题的。但是作为这篇文章的作者我必须要很负责任的告诉大家无论哪个Fix版本对于多参数的情况VS智能提示令我感到很意外甚至无法理解。 而且更令我抓不着头脑的是这些VS智能提示并不是完全“瘫痪”而是时而行时而丢失好像在跟你玩捉迷藏那样。我所见到的有以下两种情况 1. 类型推断正确但智能提示丢失 虽然 VS 对类型的推断是正确的 看后面 f 的类型够吓人的 但当你接着编写 pathList 时VS就判断成未知类型 然后当写完整个pathList后点不到任何方法出来。此时对于VS来说这个pathList相当于是凭空捏造的那样。 于是硬着头皮写完Add方法后把鼠标移上去提示信息又能够跑出来了。 这时候跑回pathList后点方法智能提示才跑出来但对于编程人员来说已经没有用了因为整个方法都已经写完了。 但当你再次写pathList还是判断成未知类型无语。 2. 类型推断令人费解 在foreach语句前写 f VS的智能提示是正确的即 Action 到了foreach里面写 f 你猜猜变成了什么竟然是 Func 由于以上例子递归调用是放在foreach里面所以必须在foreach里面写f于是再次硬着头皮写完整句代码提示信息再一次“回个神来”。 注我的编程环境是win7中文VS2008英文SP1 这莫非是VS2008的一个bug有意思吧大家不妨把以上代码放到自己的VS里试试看看是否只有我的VS才这样。 如果大家的VS对以上代码的智能提示都是乱糟的那么我建议认识微软的朋友高举此文游行到微软的大门嘿嘿。 末了说一句以上代码在VS2010中的智能提示是Perfect的。VS2010真是很好很强大唯一不爽的就是逼得我要换机器可怜我的NoteBook刚买不久 TT。 结语 其实我还想兴致勃勃的看看 x f(Fix(f), x) 在没有 Lambda 表达式和匿名函数的支持会是什么模样以一窥其真谛帮助理解但用Reflector 反编译以后得到的是以下代码... 不是我能看懂的东西作罢...
public static Action Fix(Action, T f)
{c__DisplayClass7 CS$8__locals8;Action CS$1$0000;CS$8__locals8 new c__DisplayClass7();CS$8__locals8.f f;CS$1$0000 new Action(CS$8__locals8.b__6);
Label_001D:return CS$1$0000;
} 请懂得以上代码含义的朋友说说。 至于较早关于Lambda表达式和递归编程结合的博文可能要追溯到这位老外的文章了 Recursive lambda expressions (从Post时间来看是2007年5月11日)
