1

我正在学习记忆，并决定将这种技术应用于计算第n-th 斐波那契数的递归函数。我不确定是否应该通过memo左值引用或右值引用传递我的地图。
下面显示的两个片段是否有任何区别（关于性能和程序的一般行为方式）？哪一个会更受欢迎？另外，有没有办法为第一个函数提供默认参数（map& memo = map{}不起作用，因为左值引用不与右值绑定......）？

版本 #1

using map = std::unordered_map<int, unsigned long long>;
unsigned long long fib(int n, map& memo){
    if(memo.find(n) != memo.cend()) return memo[n];
    if(n <= 2) return 1;
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

版本 #2

using map = std::unordered_map<int, unsigned long long>;
unsigned long long fib(int n, map&& memo = map{}){
    if(memo.find(n) != memo.cend()) return memo[n];
    if( n <= 2) return 1;
    memo[n] = fib(n - 1, std::move(memo)) + fib(n - 2, std::move(memo));
    return memo[n];
}
4

1 回答 1

2

在 C++ 中，移动对象对应于以下约定：

我从不打算再次使用这个对象。我将对象移动到的人：您可以随意使用该对象的资源做任何您想做的事情。我保证不会在没有先为其分配新值的情况下再次使用该对象，因此我永远不会看到您所做的任何事情的影响。所以，请对我的对象做一些残忍和不寻常的事情，如果它能让你开心的话。

现在，考虑这行代码：

memo[n] = fib(n - 1, std::move(memo)) + fib(n - 2, std::move(memo));

在这里，您正在调用std::move(memo)，表示“我保证不再使用memo”。但是，在同一行代码中，您将分配给memo[n]，这意味着您确实计划memo稍后使用。这违反了你与任何你std::move反对的人签订的合同。把它想象成你和斐波那契调用之间的对话：

  • 你：嘿，斐波那契先生！我给你一张记忆表。它是 100% 你的，我再也不会使用它了。
  • 斐波那契：太好了！谢谢！
  • 你：好的，既然我刚刚给了你记忆表，我想把它涂成蓝色并在上面放花。
  • 斐波那契：等等，等等！这不再是你的桌子了！
  • 你：好吧，反正我会去做的。
  • 斐波那契：为什么，你这个小家伙！（暴力随之而来）

是的。那是行不通的。

忽略对 的分配memo[n]，这里还有另一个问题。您试图将同一个物体两次移动到两个不同的人身上。从你们之间的对话的角度思考这意味着什么，第一次调用斐波那契，第二次调用斐波那契。

  • 你：嘿，先生。第一次调用斐波那契！这是memo. 是你的。随心所欲地使用它。没有人会看到它。
  • 第一次打电话给斐波那契先生：哇哦！棒极了！
  • 你：嘿，斐波那契的第二次呼叫先生！这是memo. 是你的。随心所欲地使用它。没有人会看到它。
  • 第二次呼叫斐波那契先生：哇哦！棒极了！
  • Mr. First Call to Fibonacci: 等等，等等！他们给了我那个东西！他们不能给你！
  • 第二次呼叫斐波那契先生：你没听吗？他们只是给了我那个东西！这是我的！
  • 第一次打电话给斐波那契先生：为什么，你这个小家伙！（暴力随之而来）

所以，是的，这不会有好的结局。:-)

从根本上说，仅std::move在您或其他任何人计划再次使用该对象时使用。在 memoization 的情况下，当一堆函数调用都需要协调以在调用之间共享同一个 memoization 表时，这个要求不成立，所以你不应该在这里使用右值语义。

于 2021-09-07T21:33:22.123 回答