应用记忆使 golom 序列变慢

Question

我正在尝试使用 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的方法，使其比golom更快。谢谢。-亚当

Answer 1

除了其他答案之外，我想补充一点，这确实可以从适当的基准测试中受益。

为了获得可靠的结果，您需要多次运行测试，并采取措施确保内存缓存和其他系统级恶作剧不会干扰结果。

值得庆幸的是，有一些库可以为我们处理大部分复杂的问题。例如，下面是使用 google 的Benchmark库对代码进行更好的基准测试：

注意其他答案提出的修复已被集成。

#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[n])
    {
        golomb[n] = 1 + golomS(n - golomS(golomS(n - 1, golomb), golomb), golomb); 
    }
    return golomb[n];
}


static void TestGolomb(benchmark::State& state) {
  for (auto _ : state) {
    benchmark::DoNotOptimize(golom(state.range(0)));
  }
}
BENCHMARK(TestGolomb)->DenseRange(1, 17, 2);

static void TestGolombS(benchmark::State& state) {
  for (auto _ : state) {
    // Make sure we always start from a fresh map
    std::unordered_map<int, int> golomb;

    // Ignore construction and destruction of the map
    auto start = std::chrono::high_resolution_clock::now();
    benchmark::DoNotOptimize(golomS(state.range(0), golomb));
    auto end = std::chrono::high_resolution_clock::now();

    auto elapsed_seconds =
      std::chrono::duration_cast<std::chrono::duration<double>>(
        end - start);

    state.SetIterationTime(elapsed_seconds.count());
  }
}
BENCHMARK(TestGolombS)->DenseRange(1, 17, 2);

下面的数据表明盈亏平衡点在 14-15 左右：

见快速板凳