應用記憶化使golom序列變慢

我正在嘗試使用 C 來解決記憶問題，并且我正在嘗試使用“golom 序列”做一個示例

int main(int argc, char* argv[])
{
    std::unordered_map<int, int> hashTable;

    
    int value = 7;
    
    auto start = std::chrono::high_resolution_clock::now(); 
    std::cout << golomS(4, hashTable) << std::endl;
    auto stop = std::chrono::high_resolution_clock::now();
    
    auto start1 = std::chrono::high_resolution_clock::now();
    std::cout << golom(4) << std::endl;;
    auto stop1 = std::chrono::high_resolution_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(stop1 - start1);

    std::cout << "Time taken by function 1: "
           << duration.count() << " microseconds" << std::endl;

    
    std::cout << "Time taken by function 2: "
          << duration1.count() << " microseconds" << std::endl;
    
    return 0;
}

int golom(int n)
{
    if (n == 1) {return 1;}
    return 1   golom(n - golom(golom(n - 1)));
}

int golomS(int n, std::unordered_map<int, int> golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1   golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}

作為輸出，我得到了這個：

4

4

函式1所用的時間：687微秒 //這是Golom S

函式2所用的時間：242微秒 //這是Golom

GolomS 不應該通過記憶更快嗎？我試著把我的頭繞在除錯器上，但我不確定有效的“緩慢”來自哪里。

我的問題是：我怎樣才能改變我做golomS的方法，比戈洛姆更快。謝謝你。-亞當

uj5u.com熱心網友回復：

除了其他答案之外，我想補充一點，這確實可以從適當的基準測驗中受益。

為了獲得可靠的結果，您需要多次運行測驗，并采取措施確保記憶體快取和其他系統級惡作劇不會干擾結果。

值得慶幸的是，有一些庫可以為我們處理大多數這些復雜性。例如，這是使用 google 的

在快速作業臺上看到

uj5u.com熱心網友回復：

int golomS(int n, std::unordered_map<int, int> golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1   golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}

在您的goloms函式中，您傳遞的golomb是一個值，而不是一個參考。這意味著每次呼叫 時goloms，編譯器都會創建一個副本golomb并在它超出范圍時銷毀該副本，而不是更改實際golomb值。

你應該通過參考傳遞。

int golomS(int n, std::unordered_map<int, int>& golomb)
{
    if(n == 1)
    {
        return 1; 
    }
    if(!golomb[n])
    {
        golomb[n] = 1   golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}

uj5u.com熱心網友回復：

您的代碼中有兩個問題。首先主要問題是按值傳遞無序地圖。您必須通過參考傳遞它以使其更快，以避免在每次函式呼叫時復制整個地圖。此外，如果您按值傳遞映射，則不會保留回傳時新計算的值，但如果您通過參考傳遞它，則新值將使呼叫者函式受益。

第二個重要問題是，您使用非常小的值4作為函式的輸入來測量時間，4計算時間很少，您必須使用更大的值，例如50，以便計算需要更多時間，從而提供更準確的時間測量。

與第二個（對于 input 50）相比，您的代碼的固定版本已經大大改善了第一個函式的計時：

13
13
Time taken by function 1: 110 microseconds
Time taken by function 2: 118345 microseconds

固定代碼：

在線試試吧！

#include <unordered_map>
#include <iostream>
#include <chrono>

int golom(int n)
{
    if (n == 1) {return 1;}
    return 1   golom(n - golom(golom(n - 1)));
}

int golomS(int n, std::unordered_map<int, int> & golomb)
{
    if(n == 1)
        return 1; 
    if(golomb.find(n) == golomb.end())
        golomb[n] = 1   golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    return golomb[n];
}

int main(int argc, char* argv[])
{
    std::unordered_map<int, int> hashTable;
    
    auto start = std::chrono::high_resolution_clock::now(); 
    std::cout << golomS(50, hashTable) << std::endl;
    auto stop = std::chrono::high_resolution_clock::now();
    
    auto start1 = std::chrono::high_resolution_clock::now();
    std::cout << golom(50) << std::endl;;
    auto stop1 = std::chrono::high_resolution_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(stop1 - start1);

    std::cout << "Time taken by function 1: "
           << duration.count() << " microseconds" << std::endl;
    
    std::cout << "Time taken by function 2: "
          << duration1.count() << " microseconds" << std::endl;
    
    return 0;
}

標籤：C 递归 记忆

上一篇：從嵌套字典python中遞回查找并回傳鍵和值

下一篇：輸入范圍內的遞回函式