C++

Question

我正在尝试使用记忆在 C++ 中实现斐波那契函数。我的实施工作但非常慢。 为什么我的实现这么慢？ 我在 javascript 中看到过类似的实现，使用对象进行记忆，而且速度非常快。 是不是因为我用了map数据结构？

#include <iostream>
#include <map>

unsigned int fib(unsigned short n, std::map<unsigned short, unsigned int> memo = {});

int main(void)
{
    for (unsigned short i = 0; i <= 50; i++)
    {
        std::cout << i << " " << fib(i) << std::endl;
    }
};

unsigned int fib(unsigned short n, std::map<unsigned short, unsigned int> memo)
{
    if (memo.find(n) != memo.end())
    {
        return memo.find(n)->second;
    }
    if (n <= 2)
    {
        return 1;
    }

    memo.insert(
        std::pair<unsigned short, unsigned int>(
            n, fib(n - 1, memo) + fib(n - 2, memo)));

    return memo.find(n)->second;
}

Answer 1

, std::map<unsigned short, unsigned int> memo)

那是地图的副本。

您在每次调用时都在复制记忆图，然后忘记添加到其中的任何内容。

unsigned int fib(unsigned short n, std::map<unsigned short, unsigned int>* memo = nullptr);

unsigned int fib(unsigned short n, std::map<unsigned short, unsigned int>* pmemo)
{
  std::map<unsigned short, unsigned int> local;
  auto& memo = pmemo?*pmemo:local;

然后将&memo传递给fib的递归调用。

这会在每次递归调用时占用一些额外的堆栈 space，但只有在进行 100,000 次以上调用时才值得担心。

unsigned int fib(unsigned short n)
{
  std::map<unsigned short, unsigned int> memo = {
    {0u,0u},
    {1u,1u},
    {2u,1u},
  };
  std::vector<unsigned short> todo = {n};
  while (!todo.empty()) {
    // solved?
    if (memo.find(todo.back()) != memo.end())
    {
      todo.pop_back();
      continue;
    }

    unsigned short a = todo.back()-1;
    unsigned short b = todo.back()-2;
    auto ita = memo.find(a);
    auto itb = memo.find(b);

    // solved?
    if (ita != memo.end() && itb !=  memo.end())
    {
       memo.insert( {todo.back(), ita->second+itb->second} );
       todo.pop_back();
       continue;
    }
    todo.push_back(a);
    todo.push_back(b); // could skip this actually
  }
  return memo.find(n)->second;
}

这是一个手动维护待办事项“调用堆栈”而不是使用递归调用的示例。

C++ - 为什么使用地图的斐波那契记忆化实现如此缓慢？

C++ - Why is this implementation of fibonacci memoization using map so slow?

performance

data-structures

dynamic-programming

memoization