[問題] 關於遞迴加快速度的迷思?

看板C_and_CPP作者 (浪無定所)時間10年前 (2013/09/03 11:40), 編輯推噓6(6021)
留言27則, 8人參與, 最新討論串1/10 (看更多)
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) C 問題(Question): 因為最近在撰寫遞迴,發現執行的時間過於冗長。 上網:項次越高的話,使用迴圈能大幅提高效能。 但因使用方式,還是以遞迴為主。 不經好奇若將遞迴改成static或是marco會更快嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 36.231.18.229

09/03 11:54, , 1F
遞迴不一定會比較慢 主要看你怎麼寫
09/03 11:54, 1F

09/03 11:55, , 2F
Fibbonacci若改寫成tail call的型式,和迴圈版一樣快
09/03 11:55, 2F

09/03 11:56, , 3F
然後遞迴不可能改成macro的,static則完全沒差別
09/03 11:56, 3F

09/03 12:07, , 4F
MACRO是要在compile-time就知道遞迴幾次嗎
09/03 12:07, 4F

09/03 12:08, , 5F
賊克這真是太神奇了
09/03 12:08, 5F

09/03 12:34, , 6F
你先改一次不就知道了。而且我相信大部分的人只會跟你講
09/03 12:34, 6F

09/03 12:35, , 7F
用遞迴加快撰寫程式的速度,不會說加快程式執行的速度
09/03 12:35, 7F

09/03 12:45, , 8F
用樣板遞回,執行期絕對快XD
09/03 12:45, 8F

09/03 12:56, , 9F
template metaprogramming
09/03 12:56, 9F
L和M大,真是抱歉,當初在想對於常呼叫的Function 是否有什麼機制,能加快運算。忘了marco的用法。 想說是否能減少RUN Time的時間。 我會在c++的時候嘗試使用Template測試,謝謝各位的指點,感謝! 至於C的話,則會繼續在找看看。 ※ 編輯: crazycat2 來自: 36.231.18.229 (09/03 13:44)

09/03 13:57, , 10F
通常是以空間換取時間,大多可以與迴圈作法的時間複雜度
09/03 13:57, 10F

09/03 13:57, , 11F
相同。
09/03 13:57, 11F

09/03 13:58, , 12F
不過實際上應該還是比較慢。
09/03 13:58, 12F

09/03 14:30, , 13F
效率還是要看寫法與編譯器
09/03 14:30, 13F

09/03 15:35, , 14F
那個template是來亂的啦 意思和macro一樣
09/03 15:35, 14F

09/03 15:36, , 15F
另外現代化的compiler都足以把tail call轉成迴圈
09/03 15:36, 15F

09/03 15:38, , 16F
如果沒辦法tail call,表示迴圈版也需要stack輔助
09/03 15:38, 16F

09/03 15:38, , 17F
這麼一來誰快誰慢其實也不一定
09/03 15:38, 17F

09/03 17:46, , 18F
有些東西可以算起來等(?)。不過缺點就是呼叫次數有限
09/03 17:46, 18F

09/03 17:47, , 19F
就有點類似靜態多型,有時候的情況是不需要執行期
09/03 17:47, 19F

09/03 17:47, , 20F
個人是這樣在想啦,最近才剛接觸樣板這塊@@
09/03 17:47, 20F

09/03 18:33, , 21F
遞迴系統太小很容易爆,迴圈比較沒這問題
09/03 18:33, 21F

09/04 01:14, , 22F
wuliou: 會這樣想主要還是因為寫法(或是演算法)的問題
09/04 01:14, 22F

09/04 01:18, , 23F
a27417332: 覺得靜態多型的想法在遞迴上的意義是?
09/04 01:18, 23F

09/04 01:20, , 24F
a27417332: 此外靜態多型也是個蠻有趣的詞
09/04 01:20, 24F

09/04 18:17, , 25F
比喻啦XD意思就是有些時候是不需要拖延到執行期
09/04 18:17, 25F

09/04 18:18, , 26F
靜態多形是網路上看到的說法,或許我該說CRTP才是@@
09/04 18:18, 26F

09/04 18:19, , 27F
不過是有些時候,當然也有狀況是拖延到執行期才可能
09/04 18:19, 27F
文章代碼(AID): #1I9Lf4Od (C_and_CPP)
討論串 (同標題文章)
以下文章回應了本文 (最舊先):
完整討論串 (本文為第 1 之 10 篇):
文章代碼(AID): #1I9Lf4Od (C_and_CPP)