等引數列，for回圈，遞回和尾遞回的對比

生活中，如果1+2+3+4.....+100，大家基本上都會用等引數列計算，如果有人從1開始加，不是傻就是白X，那么程式中呢，是不是也是這樣，今天無意中看到了尾遞回，以前也寫過，但是不知道這個專業名詞，今天寫一下對比下性能問題，

今天主要是看到了尾遞回，所以聯想到了這些，寫下這篇文章，其中也把Benchmark (Nuget上的BenchmarkDotNet)的基準測驗用了下，感覺比較好用，贊，Benchmark 需要在release下運行，

原則上所有的遞回操作，都可以寫成回圈操作，尾遞回是指，在函式回傳的時候，呼叫自身本身，并且return陳述句不能包含運算式，這樣編譯器或者解釋器就可以把尾遞回做優化，試運行速度更快，

測驗類

public class TestClass{    /// <summary>    /// for回圈    /// </summary>    /// <param name="n"></param>    /// <param name="counter"></param>    /// <returns></returns>    public int TestFor(int n)    {        int s = 1;        for (int i = 2; i < n + 1; i++)        {            s = s + i;        }        return s;    }    /// <summary>    /// 等引數列    /// </summary>    /// <param name="n"></param>    /// <param name="counter"></param>    /// <returns></returns>    public int TestForG(int n)    {        int s = (1 + n) * n / 2;        return s;    }    /// <summary>    /// 遞回    /// </summary>    /// <param name="n"></param>    /// <param name="counter"></param>    /// <returns></returns>    public int TestRec(int n)    {        if (n == 1) return 1;        return n + TestRec(n - 1);    }    /// <summary>    /// 尾遞回    /// </summary>    /// <param name="n"></param>    /// <param name="counter"></param>    /// <returns></returns>    public int TestTail(int n)    {        return TestTail(1, n);    }    public int TestTail(int sum, int n)    {        if (n == 1) return sum;        sum = sum + n;        return TestTail(sum, n - 1);    }}

基準測驗

[SimpleJob(RuntimeMoniker.NetCoreApp30)][RPlotExporter]public class TestClassForBenchmark{    private readonly TestClass testClass = new TestClass();    [Params(100,500,1000,5000)]    public int N;    [Benchmark]    public void TestFor()    {        testClass.TestFor(N);    }    [Benchmark]    public void TestForG()    {        testClass.TestForG(N);    }    [Benchmark]    public void TestRec()    {        testClass.TestRec(N);    }    [Benchmark]    public void TestTail()    {        testClass.TestTail(N);    }}

Main程式呼叫

BenchmarkRunner.Run<TestClassForBenchmark>();

結果

用Benchmark的基準測驗發現，運行時間：等差 < for < 尾遞回(接近for) < 遞回，for的運行速度比遞回快，但是遞回結構比較清晰，容易理解，

發現TestForG有點問題，接下來自己簡單測驗

實際用Stopwatch測驗

TestClass testClass = new TestClass();Stopwatch stopSwitch = new Stopwatch();int n = 5000;stopSwitch.Start();int sum = testClass.TestFor(n);stopSwitch.Stop();Console.WriteLine($"結果：{sum},TestFor時間:{stopSwitch.ElapsedTicks}");stopSwitch.Start();sum = testClass.TestForG(n);stopSwitch.Stop();Console.WriteLine($"結果：{sum},TestForG時間:{stopSwitch.ElapsedTicks}");stopSwitch.Restart();sum = testClass.TestRec(n);stopSwitch.Stop();Console.WriteLine($"結果：{sum},TestRec時間:{stopSwitch.ElapsedTicks}");stopSwitch.Restart();sum = testClass.TestTail(n);stopSwitch.Stop();Console.WriteLine($"結果：{sum},TestTail時間:{stopSwitch.ElapsedTicks}");

Stopwatch測驗結果

1. 10次結果：55,TestFor時間:2024結果：55,TestForG時間:3799結果：55,TestRec時間:1603結果：55,TestTail時間:23712. 100結果：5050,TestFor時間:1704結果：5050,TestForG時間:2708結果：5050,TestRec時間:1069結果：5050,TestTail時間:14013. 500結果：125250,TestFor時間:1794結果：125250,TestForG時間:3096結果：125250,TestRec時間:9398結果：125250,TestTail時間:23324. 1000結果：500500,TestFor時間:2080結果：500500,TestForG時間:4147結果：500500,TestRec時間:2003結果：500500,TestTail時間:25405. 5000結果：12502500,TestFor時間:1428結果：12502500,TestForG時間:3982結果：12502500,TestRec時間:6815結果：12502500,TestTail時間:2799

結論

1. for的運行速度比遞回快，但是遞回結構比較清晰，容易理解，

2. 等差計算不一定比for回圈快

斐波那契數列對比

        /// <summary>        /// 回圈實作 counter:運行次數        /// </summary>        public long Fib(int n, ref int counter)        {            if (n < 1) return 0;            long a = 1, b = 1;            long temp;            for (int i = 3; i <= n; i++)            {                counter++;                temp = a;                a = b;                b = temp + b;            }            return b;        }        /// <summary>        /// 遞回實作        /// </summary>        public long FibRec(int n, ref int counter)        {            counter++;            if (n < 1) return 0;            if (n < 3) return 1;            return FibRec(n - 1, ref counter) + FibRec(n - 2, ref counter);        }        /// <summary>        /// 尾遞回實作        /// </summary>        public long FibTailRec(int n, ref int counter)        {            if (n < 1) return 0;            if (n < 3) return 1;            return FibRec(1, 1, n, ref counter);        }        public long FibRec(long last, long prev, int n, ref int counter)        {            counter++;            long temp = last + prev;            if (n == 3) return temp;            last = prev;            prev = temp;            return FibRec(last, prev, n - 1, ref counter);        }

效果

counter是運行的次數，斐波那契數列直接用遞回，n=100都直接堆疊溢位，遞回用的好了，思路清晰，用的不好的話，資料稍微大點就是深深的坑，用遞回盡量優化為尾遞回，也就是回傳的時候呼叫自身，不要有運算式，

標籤：.NET Core

上一篇：【架構篇】ASP.NET Core 基于 Consul 動態配置熱更新

下一篇：阿里云K8S下玩.NET CORE 3.1