使顯式堆棧算法更快

有一些遞歸算法可以很快填滿堆棧。一種解決方法是使棧顯式化，從而將算法轉換爲迭代算法。使顯式堆棧算法更快

但我注意到有了顯式堆棧會讓算法慢得多（這可能不會讓我感到意外）。是否有任何通用的C++指南可以更快地製作顯式堆棧？它們可能比原始遞歸算法運行得更快嗎？

編輯：我寫了一個明確的堆棧功能如下。我也粘貼了迭代代碼。出於某種原因，使用std::vector而不是std::stack會更快，這是相當令人驚訝的。

// A(m, n) = n + 1     if m = 0 
//   = A(m - 1, 1)   if m > 0 and n = 0 
//   = A(m - 1, A(m, n - 1)) if m, n > 0 


int A(int m, int n, long& iterations, 
    std::vector<std::pair<int, int> >& stack) 
{ 
    stack.push_back(std::make_pair(m, n)); 
    long result = 0; 
    bool result_available = false; 

    while (stack.size() > 0) 
    { 
     iterations += 1; 

     if (result_available) { 
      stack.back().second = result; 
      result_available = false; 
     } 

     m = stack.back().first; 
     n = stack.back().second; 
     stack.pop_back(); 

     if (m == 0) { 
      result = n + 1; 
      result_available = true; 
     } 
     else if (m > 0 && n == 0) { 
      stack.push_back(std::make_pair(m - 1, 1)); 
     } 
     else if (m > 0 && n > 0) { 
      stack.push_back(std::make_pair(m - 1, n)); 
      stack.push_back(std::make_pair(m, n - 1)); 
     } 
    } 

    return result; 
}

來源

2012-10-24 Paul Manta

如果你包括一個遞歸和顯式堆棧版本的算法，其中時間顯着不同，這將更容易回答。一般來說，很難回答性能問題（超越算法複雜性），因爲影響性能的因素很多。 – Mankarse

嚴格猜測（正如@Mankarse所說，顯示一些代碼），但是創建堆棧幀通常比分配堆內存要快得多，所以如果迭代方法最終頻繁地擴展堆棧，您將會受到堆分配的影響。解決方案是使分配更少頻繁... –

某些類型的遞歸可以被消除到一個循環（尾遞歸）。那麼你根本不需要堆棧。知道實際的算法和遞歸行爲是很好的。 –

嘗試從堆中儘可能少分配內存。這很慢。
消除尾遞歸 - 對於他們你不需要遞歸調用。它看起來不像遞歸解決方案那麼優雅，但它更快。有關如何完成這個示例，請搜索斐波那契實現。有2個遞歸變體和一個非遞歸變體。
作爲函數調用，顯式堆棧不會更快&通過堆棧傳遞參數是一些最快的彙編指令，因爲它們經常使用。

來源

2012-10-24 14:53:02

在斐波那契的情況下，我們不要忘記，第一個改進是移到O（N）實現（由於記憶/動態編程） –

是的 - 這是第二個帶遞歸遞歸的遞歸算法。但是如果你消除了該算法中的尾遞歸，它甚至更快。 –

還有另一種解決方案，對於最近版本的gcc的幸運用戶：-fsplit-stack。

拆分堆棧不是一個新想法，Lisp把它放回去了......它只是意味着編譯器創建了一個程序，它不需要預先設置完整的堆棧，而是可以將其擴展爲必要。因此堆棧變得不連貫。

當然，這需要所有（或大多數）庫適應這種新的堆棧機制（因此需要重新編譯整個軟件堆棧）。對此不理解的庫可能仍然會產生堆棧溢出異常，如果您避免在這些庫中使用深度遞歸函數，這並不是什麼問題。

有了這個機制，只要你有可用的內存，堆棧就會增長以適應你的程序。

來源

2012-10-24 14:43:57

使顯式堆棧算法更快

回答

相關問題