優化遞歸函數

-2

對於n = 18，我的代碼在1GHz機器上花費的時間超過0.5秒。我認爲這是由於我使用遞歸函數，但我並不真正知道如何優化此代碼，因爲它實際上只是「打印」數字...... 因此，也許問題來自這樣一個事實：我正在使用遞歸函數。優化遞歸函數

這裏是我的代碼：

#include<iostream> 

void singleSquareRemove (int s) 
{ 
    if (s == 1) 
    { 
     std::cout << 1 << std::endl; 
     return; 
    } 
    else 
    { 
     for (int i = s-1; i >=1; --i) 
    singleSquareRemove(i); 
     std::cout << s << std::endl; 
    } 
} 
void whenSquareisFull (int v) 
{ 
    if (v == 1) 
    { 
     std::cout << 1 << std::endl; 
     return; 
    } 
    else if (v == 2) 
    { 
     std::cout << 2 << std::endl; 
     return; 
    } 
    else if (v == 3) 
    { 
     std::cout << 1 << std::endl; 
     std::cout << 3 << std::endl; 
     return; 
    } 
    else 
    { 
     whenSquareisFull(v-2); 
     for (int i = v-3; i > 0; --i) 
    singleSquareRemove(i); 
     std::cout << v << std::endl; 
    } 
} 
int main() 
{ 

    unsigned int n {0}; 
    std::cin >> n; 

    whenSquareisFull(n); 
    for (int i = n-1; i > 0; --i) 
    { 
     singleSquareRemove(i); 
     } 

}

來源

2017-10-17 Salutsalut1

簡介，評估和優化熱點，重複。 – crashmstr

通常情況下，你必須進行基準測試等，但是'std :: endl'可能會佔用很多時間。 – Rakete1111

我認爲這可能會有所幫助，如果您將遞歸調用作爲尾調用，以便可以通過編譯器進行優化。 –

的時間接收器是在您打印的價值和沖洗輸出（std::endl）。

您可以通過使用「緩衝區」類型（如std::vector）然後迭代打印來避免該時間陷入。通過這種方式，時間花在了實際的「計算」上，然後您可以進行分析，而不是花時間打印輸出。使用

示例代碼：

#include <iostream> 
#include <vector> 

static std::vector<int> values; 

void singleSquareRemove (int s) 
{ 
    for (int i = s - 1; i >= 1; --i) 
     singleSquareRemove(i); 
    values.push_back(s); 
} 

void whenSquareisFull (int v) 
{ 
    switch (v) { 
     case 1: case 2: 
      values.push_back(v); 
     break; 
     case 3: { 
      values.push_back(1); 
      values.push_back(v); 
     } break; 
     default: { 
      whenSquareisFull(v - 2); 
      for (int i = v - 3; i > 0; --i) singleSquareRemove(i); 
      values.push_back(v); 
     } break; 
    } 
} 

int main() 
{ 
    unsigned int n {0}; 
    std::cin >> n; 
    // start timing here 
    whenSquareisFull(n); 
    while (--n > 0) singleSquareRemove(n); 
    // stop timing here 
    for (auto itr = values.begin(); itr != values.end(); ++itr) 
     std::cout << *itr << std::endl; 
    return 0; 
}

希望幫助！

來源

2017-10-17 20:22:45 txtechhelp

優化遞歸函數

回答

相關問題