首页 > 安全资讯 >

C#也玩尾递归(续)

11-07-28

今天重新看了下文中最后的实现代码,感觉还是不够满意:因为引入了一个对用户来说不是很必要的数据结构RecFunc<>,用户需要定义的代码大概是这样:(rec,i,n,a,b) => (n<3 ? 1 : (i==n ? a+b : rec.Cal...

 

今天重新看了下文中最后的实现代码,感觉还是不够满意:因为引入了一个对用户来说不是很必要的数据结构RecFunc<>,用户需要定义的代码大概是这样:

 

(rec,i,n,a,b) => (n<3 ? 1 : (i==n ? a+b : rec.Callback(i+1, n, b, a+b)))

  从调用方的角度来看,下面代码就比上面的更容易理解(不用self都不好意思说自己学过python):

 

(self,i,n,a,b) => (n<3 ? 1 : (i==n ? a+b : self(i+1, n, b, a+b)))

  是不是该将那个类继承自Delegate?可是C#不许直接继承这个特殊类。或许可以用Delegate.CreateDelegate创建一个委托对象来组合?顺着这个方向,进而想到了直接创建一个匿名委托来实现。

 

  于是我将代码重新修改了下,短小精悍了不少,最终尾递归包装的代码如下:

 

public static Func<T1,T2,T3,T4,TResult> TailRecursive<T1,T2,T3,T4,TResult>

    (Func<Func<T1,T2,T3,T4,TResult>,T1,T2,T3,T4,TResult> func)

{

    return (p1,p2,p3,p4) =>

    {

        bool callback = false;

        Func<T1,T2,T3,T4,TResult> self = (q1,q2,q3,q4) =>

        {

            p1 = q1;

            p2 = q2;

            p3 = q3;

            p4 = q4;

            callback = true;

            return default(TResult);

        };

        do

        {

            var result = func(self,p1,p2,p3,p4);

            if (!callback)

            {

                return result;

            }

            callback = false;

        } while (true);

    };

}

  另外还补充了普通递归的包装方法:

 

public static Func<T1,T2,T3,T4,TResult> Recursive<T1,T2,T3,T4,TResult>

    (Func<Func<T1,T2,T3,T4,TResult>,T1,T2,T3,T4,TResult> func)

{

    Func<T1,T2,T3,T4,TResult> self = null;

    self = (p1,p2,p3,p4) => func(self,p1,p2,p3,p4);

    return self;

}

  写完代码,自然还是要测试下的,我测试对比了三种方式的计算Fib数列的性能:(1)最基本的递归调用的方式(2)用上面的Recursive<> (3)用上面的TailRecursive<>尾递归。

 

  前两种都属于普通递归,受到调用栈的限制Fib(10000)还可以执行,但是Fib(20000)就堆栈溢出了。第三种方法由于是尾递归,调用Fib(20000)自然没问题,就是Fib(10000000)也是瞬间执行完。

 

  测试总要有数据支持才行,刚刚的测试发现,前两种方法Fib(10000)时Stopwatch记录的毫秒数都是0,无法根据花费时间来比较三者的性能。于是我又加了段很邪恶的测试代码,白白浪费CPU时间:

 

// 外部初始化

int x = 10000;

var s = x.ToString();

// 递归循环中

x = -x;

for (int j = 0; j < Math.Abs(x); j++)

{

    s = (s + x.ToString()).Substring(0, 5);

}

  料想这代码该不会被编译器或JIT优化掉吧?果然,添加后时间对比就比较明显了:

 

Normal

Fib(100) = -980107325 (206 ms)

Fib(1000) = 1556111435 (2419 ms)

Fib(10000) = 1242044891 (65435 ms)

/////////////////////////////////////

Recursive

Fib(100) = -980107325 (192 ms)

Fib(1000) = 1556111435 (2735 ms)

Fib(10000) = 1242044891 (103156 ms)

/////////////////////////////////////

TailRecursive

Fib(100) = -980107325 (186 ms)

Fib(1000) = 1556111435 (1889 ms)

Fib(10000) = 1242044891 (18969 ms)

  可以看出,在递归次数较多的情况下,尾递归确实在性能上有较大的优势。出乎意料的是像Recursive这种简单的包装竟然降低了不少性能,不知有哪位大哥可以看看测试代码,看到底问题出在哪里?或许哪天我想通了,到时可以再写篇<续2>呵呵

 

测试代码

static void Main(string[] args){    Console.WriteLine("Normal");    int x = 10000;    var s = x.ToString();    GC.Collect();    GC.WaitForPendingFinalizers();    Func<int, int, int, int, int> fib1 = null;    fib1 = (i, n, a, b) =>    {        x = -x;        for (int j = 0; j < Math.Abs(x); j++)        {            s = (s + x.ToString()).Substring(0, 5);        }        return (n < 3 ? 1 : (i == n ? a + b : fib1(i + 1, n, b, a + b)));    };    Action<int> Fib1 = n =>    {        Console.Write("Fib({0}) = ", n);        var sw = System.Diagnostics.Stopwatch.StartNew();        var result = fib1(3, n, 1, 1);        sw.Stop();        Console.WriteLine("{0} ({1} ms)", result, sw.ElapsedMilliseconds);    };    Fib1(100);    Fib1(1000);    Fib1(10000);    Console.WriteLine("/////////////////////////////////////");    Console.WriteLine("Recursive");    GC.Collect();    GC.WaitForPendingFinalizers();    var fib2 = Recursive<int, int, int, int, int>((self, i, n, a, b) =>    {        x = -x;        for (int j = 0; j < Math.Abs(x); j++)        {            s = (s + x.ToString()).Substring(0, 3);        }        return (n < 3 ? 1 : (i == n ? a + b : self(i + 1, n, b, a + b)));    });    Action<int> Fib2 = n =>    {        Console.Write("Fib({0}) = ", n);        var sw = System.Diagnostics.Stopwatch.StartNew();        var result = fib2(3, n, 1, 1);        sw.Stop();        Console.WriteLine("{0} ({1} ms)", result, sw.ElapsedMilliseconds);    };    Fib2(100);    Fib2(1000);    Fib2(10000);    Console.WriteLine("/////////////////////////////////////");    Console.WriteLine("TailRecursive");    GC.Collect();    GC.WaitForPendingFinalizers();    var fib3 = TailRecursive<int, int, int, int, int>((self, i, n, a, b) =>    {        x = -x;        for (int j = 0; j < Math.Abs(x); j++)        {            s = (s + x.ToString()).Substring(0, 3);        }        return (n < 3 ? 1 : (i == n ? a + b : self(i + 1, n, b, a + b)));    });    Action<int> Fib3 = n =>    {        Console.Write("Fib({0}) = ", n);        var sw = System.Diagnostics.Stopwatch.StartNew();        var result = fib3(3, n, 1, 1);        sw.Stop();        Console.WriteLine("{0} ({1} ms)", result, sw.ElapsedMilliseconds);    };    Fib3(100);    Fib3(1000);    Fib3(10000);}

相关文章
最新文章
热点推荐