C++实现Golom序列时记忆化版本比普通递归慢的优化咨询

核心问题点 #

• 记忆化函数golomS的哈希表参数为值传递：每次递归调用都会完整拷贝当前的哈希表，产生极高的内存复制开销，直接抵消了记忆化减少重复计算带来的收益，甚至会更慢。
• 测试输入规模过小：你测试时输入的n=4，普通递归本身仅需要极少量计算，记忆化的哈希表查询、插入的固定开销相对更突出，无法体现记忆化的优势。
• 缓存结构选型不合适：std::unordered_map存在哈希计算、冲突处理的额外开销，对于Golom序列这种输入为连续正整数的场景，用数组/std::vector做缓存效率更高。

代码修改方案 #

第一步：修改golomS的参数为引用传递 #

将函数签名改为int golomS(int n, std::unordered_map<int, int>& golomb)，加引用符号&避免哈希表拷贝。

第二步：替换缓存结构（可选优化） #

改用std::vector作为缓存，读写效率更高，提前预留足够大小即可。

第三步：调整测试输入规模 #

测试时将n调整为更大的值（比如n=500、n=1000），才能看到记忆化的性能优势。

修复后的完整示例代码 #

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

// 普通递归版本
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.count(n))
    {
        golomb[n] = 1 + golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}

// 更高效率的vector缓存版本
int golomS_vec(int n, std::vector<int>& golomb)
{
    if(n == 1)
    {
        return 1;
    }
    if(golomb[n] == 0)
    {
        golomb[n] = 1 + golomS_vec(n - golomS_vec(golomS_vec(n - 1, golomb), golomb), golomb);
    }
    return golomb[n];
}

int main(int argc, char* argv[])
{
    const int test_n = 500; // 改用更大的n测试
    std::unordered_map<int, int> hashTable;
    std::vector<int> vecCache(test_n + 1, 0);

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

    auto start2 = std::chrono::high_resolution_clock::now();
    std::cout << golomS_vec(test_n, vecCache) << std::endl;
    auto stop2 = 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);
    auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(stop2 - start2);

    std::cout << "Time taken by 记忆化哈希版本: "
           << duration.count() << " microseconds" << std::endl;

    std::cout << "Time taken by 普通递归版本: "
          << duration1.count() << " microseconds" << std::endl;

    std::cout << "Time taken by 记忆化数组版本: "
          << duration2.count() << " microseconds" << std::endl;
    
    return 0;
}

测试效果说明 #

当测试n=500时，普通递归版本需要数秒甚至数十秒才能返回结果，而两个记忆化版本都可以在几微秒到几十微秒的量级完成计算，性能差距非常明显。

内容的提问来源于stack exchange，提问作者Adam Kostandy