等差數列,for迴圈,遞歸和尾遞歸的對比

来源:https://www.cnblogs.com/zhao123/archive/2020/01/14/12192116.html

生活中,如果1+2+3+4.....+100,大家基本上都會用等差數列計算,如果有人從1開始加,不是傻就是白X,那麼程式中呢,是不是也是這樣。今天無意中看到了尾遞歸,以前也寫過,但是不知道這個專業名詞,今天寫一下對比下性能問題。 今天主要是看到了尾遞歸,所以聯想到了這些,寫下這篇文章,其中也把Ben ...


生活中,如果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);
    }
}
View Code

基準測試

[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);
    }

}
View Code

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}");
View Code

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都直接堆棧溢出。遞歸用的好了,思路清晰,用的不好的話,數據稍微大點就是深深的坑。用遞歸儘量優化為尾遞歸,也就是返回的時候調用自身,不要有表達式。


您的分享是我們最大的動力!

更多相關文章
  • Web服務 Web服務可以讓你在HTTP協議的基礎上通過XML或者JSON來交換信息。如果你想知道上海的天氣預報、中國石油的股價或者淘寶商家的一個商品信息,你可以編寫一段簡短的代碼,通過抓取這些信息然後通過標準的介面開放出來,就如同你調用一個本地函數並返回一個值。 Web服務背後的關鍵在於平臺的無關 ...
  • AbstractCollection介紹 AbstractCollection抽象類是Collection的基本實現,其實現了Collection中的大部分方法,可以通過繼承此抽象類以最少的代價來自定義Collection; 如果要定義一個不可變Collection,只需要繼承此類,並實現itera ...
  • 這裡沒有線程 原文地址: "https://blog.stephencleary.com/2013/11/there is no thread.html" 前言 我是在看 C 8.0 新特性非同步流時在評論里看到這篇文章的,閱讀之後發現這篇文章乾貨滿滿,作者解釋的非常清晰,裡面的本質分析內容在《CLR ...
  • 在這個互聯網時代,數據被稱為石油,由此數據安全是被看得尤為重要,本篇文章意在普及密碼學的基礎知識。 ...
  • 1 static DataTable ConvertJsonToTable(string jsonValue) 2 { 3 DataTable dt = (DataTable)JsonConvert.DeserializeObject(jsonValue, typeof(DataTable)); 4 ...
  • 本筆記摘抄自:https://www.cnblogs.com/PatrickLiu/p/7614630.html,記錄一下學習過程以備後續查用。 一、引言 在現實生活中,我們經常會遇到一些構成比較複雜的物品。比如電腦,是由CPU、主板、記憶體條、硬碟、顯卡、機箱等組裝而成的。手機也是複雜物品, 由主板 ...
  • 做了一個 項目本地測了沒問題發佈到正式環境上,幾天之後有個統計頁面報錯了,看了本地是正常的, 於是就排查,發現 ID 列 在對 字元串轉int 時候 由於用了 Convert.TonInt16 長度不夠, 資料庫的ID 已經到了33000。 自己也知道 Convert.TonInt16 、 Conv ...
  • 微信公眾號: "Dotnet9" ,網站: "Dotnet9" ,問題或建議: "請網站留言" , 如果對您有所幫助: "歡迎贊賞" 。 C WPF之Material Design自定義顏色 閱讀導航 1. 本文背景 2. 代碼實現 3. 本文參考 1. 本文背景 主要介紹使用Material De ...
一周排行
  • 微信公眾號: "Dotnet9" ,網站: "Dotnet9" ,問題或建議: "請網站留言" , 如果對您有所幫助: "歡迎贊賞" 。 .NET CORE(C ) WPF 抽屜式菜單 閱讀導航 1. 本文背景 2. 代碼實現 3. 本文參考 4. 源碼 1. 本文背景 使用簡單動畫實現抽屜式菜單 ...
  • 在上面abp(net core)+easyui+efcore實現倉儲管理系統——ABP WebAPI與EasyUI結合增刪改查之八(三十四) 文章的學習之後。我們通過前面的八篇文章已經學習了通過WebAPI介面與控制器去實現新增、刪除與修改功能。接下來,我們要在控制器中實現查詢功能。 ...
  • 1.選中項目-->屬性-->生成-->選中 XML文檔文件(xml路徑和該項目相同) 2.選擇生成序列化程式集:自動/開 ...
  • 本筆記摘抄自:https://www.cnblogs.com/PatrickLiu/p/7640873.html,記錄一下學習過程以備後續查用。 一、引言 從今天開始我們開始講結構型設計模式,結構型設計模式有如下幾種:適配器模式、橋接模式、裝飾模式、組合模式、外觀模式、享元模式、代理模式。 創建型設 ...
  • C 中 ConfigureAwait 相關答疑FAQ 在前段時間經常看到園子里有一些文章討論到 ConfigureAwait,剛好今天在微軟官方博客看到了 "Stephen Toub" 前不久的一篇答疑 ConfigureAwait 的一篇文章,想翻譯過來。 原文地址:https://devblog ...
  • 想要實現二維數組中根據某個欄位排序,一般可以通過數組迴圈對比的方式實現。這裡介紹一種更簡單的方法,直接通過PHP函數實現。array_multisort() :可以用來一次對多個數組進行排序,或者根據某一維或多維對多維數組進行排序。詳細介紹可參考PHP手冊:https://www.php.net/m ...
  • 常用的軟體: 播放器: cloundMusic(網易雲音樂) https://music.163.com/#/download PotPlayer(一款強大的視頻播放器) https://daumpotplayer.com/download/ ACDsee(ACDsee圖片編輯器免費版) https ...
  • 發現問題 在一次偶然中,在爬取某個網站時,老方法,打開調試工具查看請求方式,請求攔截,是否是非同步載入,不亦樂乎,當我以為這個網站非常簡單的時候,發現二級網頁的地址和源碼不對應 Ajax非同步載入?源碼也是這樣的 而且這些鏈接直... ...
  • 準備年後要跳槽,所以最近一直再看面試題,並且把收集到的面試題整理了以下發到博客上,希望對大家有所幫助。 首先是集合類的面試題 1. HashMap 排序題,上機題。 已知一個 HashMap<Integer,User>集合, User 有 name(String)和 age(int)屬性。請寫一個方 ...
  • JVM體繫結構圖 Native Interface(本地介面) Java本地介面(Java Native Interface (JNI))允許運行在Java虛擬機(Java Virtual Machine (JVM))上的代碼調用本地程式和類庫,或者被它們調用,這些程式和類庫可以是其它語言編寫的,比 ...
x