等引數列，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時間:2371

2. 100
結果：5050,TestFor時間:1704
結果：5050,TestForG時間:2708
結果：5050,TestRec時間:1069
結果：5050,TestTail時間:1401
3. 500
結果：125250,TestFor時間:1794
結果：125250,TestForG時間:3096
結果：125250,TestRec時間:9398
結果：125250,TestTail時間:2332
4. 1000
結果：500500,TestFor時間:2080
結果：500500,TestForG時間:4147
結果：500500,TestRec時間:2003
結果：500500,TestTail時間:2540
5. 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都直接堆疊溢位，遞回用的好了，思路清晰，用的不好的話，資料稍微大點就是深深的坑，用遞回盡量優化為尾遞回，也就是回傳的時候呼叫自身，不要有運算式，

標籤：其他

上一篇：C# convert json to datatable,convert list to datatable

下一篇：C#設計模式學習筆記：(4)建造者模式