斐波那契记忆 - 通过左值与右值参考传递

Question

我正在学习记忆化，并决定将此技术应用于计算第 n 个斐波那契数的递归函数。我不确定我是否应该通过左值引用或右值引用来传递我的 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];
}

Answer 1

在C++中，移动一个对象对应如下契约：

I am never planning on using this object again. Person I am moving the object to: you are free to do whatever you'd like with this object's resources. I promise not to use the object again without first assigning it a new value, so I will never see the effects of anything you did. So please, do Cruel and Unusual things to my object if it makes you happy.

现在，考虑这行代码：

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

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

你：嘿，斐波那契先生！我给你一个备忘录 table。它 100% 归您所有，我再也不会使用它了。
斐波那契数列：太棒了！谢谢！
你：好的，既然给了你备忘table，我想把它涂成蓝色，然后在上面放花。
斐波那契：等等，等等！这不再是你的 table！
你：好吧，反正我也要去
Fibonacci：为什么，你这个小东西！（暴力接踵而至）

所以，是的。那是行不通的。

忽略对 memo[n] 的赋值，这里还有另一个问题。您正试图将同一个对象两次移动给两个不同的人。从你们之间的一次对话，第一次调用 Fibonacci，第二次调用 Fibonacci 的角度想想这意味着什么。

你：嗨，斐波那契的第一次通话先生！这里是 memo。是你的。用它做任何你想做的事。没有其他人会看到它。
先生第一次调用斐波那契数列：哇哦！太棒了！
你：嘿，斐波那契的第二次调用先生！这里是 memo。是你的。用它做任何你想做的事。没有其他人会看到它。
先生第二次调用斐波那契数列：哇哦！太棒了！
先生First Call to Fibonacci：等等，等一下！他们给了我那个东西！他们不能给你！
先生第二次调用斐波那契数列：你没在听吗？他们刚刚给了我那个东西！这是我的！
先生First Call to Fibonacci：为什么，你这个小东西！（暴力接踵而至）

是的，这不会有好结果。 :-)

基本上，仅当您或其他任何人计划再次使用该对象时才使用 std::move。在记忆的情况下，当一堆函数调用都需要协调以在调用之间共享相同的记忆 table 时，该要求不成立，因此您不应在此处使用右值语义。

斐波那契记忆 - 通过左值与右值参考传递

Fibonacci memoization - pass by lvalue vs rvalue reference

c++

recursion

memoization

fibonacci

move-semantics