等差數列,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 ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...