Re: [問題] 關於遞迴加快速度的迷思？

看板C_and_CPP作者Feis (永遠睡不著 @@)時間12年前 (2013/09/06 04:05)推噓5(5推 0噓 9→)

留言14則, 4人參與討論串7/10 (看更多)

※ 引述《LPH66 (f0VMRgEBA)》之銘言： <deleted> : 雖然有點像在模仿 GCD 的 "GCD(a,b) = GCD(b,a%b)" : 不過確實是另一條思路... 確實，通常當我們可以用更簡單的形式來表示時，也意味著有一種更高階或不同角度的解釋法。之前我的回應是著重在『遞迴比迴圈效率要差』的論述上，也就是當問題具有遞迴關係時，在語言實作中使用遞迴函式呼叫是否比使用迴圈效率還要差。所以我使用一個比較單純的例子跟寫法來說明其中的關鍵點。不過看來有人對於一些技巧有點興趣，所以我試著將之前的回應導到這個問題上，看看大家有沒有什麼不同的想法 ( 雖然實際上我在講的可能就是動態規劃 (DP) 常用來減少記憶體使用的手法)。這是我在之前回應中寫的最後一個遞迴版本： void f(int n, int *F, int i = 0) { if (n < i) return; if (i <= 1) F[i] = i; else F[i] = F[i-1] + F[i-2]; f(n, F, i+1); } int main() { int F[10+1]; f(10, F); printf("%d\n", F[10]); return 0; } 現在的問題變成是：我們一定需要這麼大的快取空間 (int F[10+1]) 嗎？其實這件事情會跟計算的順序有很大的關係。在把遞迴函式呼叫中呼叫者跟被呼叫者的關係描述成樹後，我上一個回應提到的快取機制 (也就是 memoization) 做的事情是避免具有相同參數值的遞迴函式重複計算造成多餘的遞迴展開。因為在這棵樹上只要其中一個具有某組參數值的函式呼叫被遞迴展開計算完後，其他具有相同參數值的函式呼叫就不需要去做同樣的遞迴展開。概念上，我們是用這個快取機制把這棵樹上的一些子樹剪掉而降低計算量。至於哪些遞迴展開 (子樹) 會被省略掉 (剪掉)，就會跟我們計算的順序有關。之前的快取機制是剪完這棵樹後以參數值當鍵值把所有節點都儲存起來，而這篇要解決的問題是在於是否一定要『同時』記得所有節點？換句話說，我們最少需要準備多大的快取空間？在快取機制中，我們清除快取最好的時機是在確保將來都不可能會再用到的時候。換句話說，在快取空間中，只要該組參數值組合不會再被存取我們就不用去保留該筆資料。 Fibonacci 數列的例子中，清除快取的手法可以透過對快取空間做滑動的技巧來達成： // 用不停更新 F[2], F[1], F[0] 去儲存 F[i], F[i-1], F[i-2]; void f(int n, int *F, int i = 0) { if (n < i) return; // 利用滑動來減少快取空間的使用 F[0] = F[1]; F[1] = F[2]; if (i <= 1) F[2] = i; else F[2] = F[1] + F[0]; f(n, F, i+1); } int main() { // 如果計算順序好，我們只需要三個空間 (F[i] = F[i-1] + F[i-2]) int F[3]; f(10, F); // 此時 F[2] 的值就是我們要的 f(10) 的值 printf("%d\n", F[2]); return 0; } 當然，事實上我們可以用更小的 F 來實現滑動, 只是可能會覺得不直覺： void f(int n, int *F, int i = 0) { if (n < i) return; // 原本滑動做的事情: // ( 這裡 F[i] 表示原本快取的資料，F[i] 表示新的值 ) // F[0] = F[1] // F[1] = F[2] // F[2] = F[1] + F[0]; // 這時我們要省略一個，所以改成同時做下面兩個述句: // F[0] = F[1] // F[1] = F[1] + F[0] // 注意這裡 F[i] 與 F[i] 值不同, // 直接依上述述句做的話, 會有 F[i] 值已經被取代不見的問題 // 因此跟實作變數交換一樣，我們需要一個額外的區域變數 old_F1 // 來暫存 int old_F1 = F[1]; if (i <= 1) F[1] = i; else F[1] = F[1] + F[0]; F[0] = old_F1; f(n, F, i+1); } int main() { int F[2]; f(10, F); printf("%d\n", F[1]); return 0; } 因為需要的快取空間夠小且固定大小，可以將他在參數列展開： void f(int n, int &F1, int &F0, int i = 0) { if (n < i) return; int old_F1 = F1; if (i <= 1) F1 = i; else F1 = F1 + F0; F0 = old_F1; f(n, F1, F0, i+1); } int main() { int F[2]; f(10, F[1], F[0]); printf("%d\n", F[1]); return 0; } 其中 F0 的參考又可以被移掉： void f(int n, int &F1, int F0 = 0, int i = 0) { // 這裡 F0 初始值不重要 if (n < i) return; int old_F1 = F1; if (i <= 1) F1 = i; else F1 = F1 + F0; f(n, F1, old_F1, i+1); } int main() { int F1; f(10, F1); printf("%d\n", F1); return 0; } 接下來我們可以用回傳值來替代參考的功能，同時我們可以將邊界條件當做快取資料的初始值： int f(int n, int F1 = 1 int F0 = 0, int i = 2) { // F0, F1 和 i 初始值很重要 if (n <= 1) return n; if (n < i) return F1; return f(n, F1+F0, F1, i+1); } int main() { printf("%d\n", f(10)); return 0; } 我們最後可以簡化到上面這樣 (但是效率跟泛用性不一定比一開始的版本好) [編輯] 板友 DJWS 覺得我原本不適當的用英文詞彙強調一些中文名詞可能會誤導其他板友，所以我將比較不正式或我不確定正確用法的英文名詞都移除。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.217.49

推

s3748679

09/06 12:13, , 1^F

09/06 12:13, 1^F

推

c2251393

09/06 23:48, , 2^F

09/06 23:48, 2^F

推

joshua5201

09/06 23:51, , 3^F

09/06 23:51, 3^F