C++记忆没有附加映射对象

Question

我试图在C++中练习基本的动态编程，但由于某些原因，它没有向std::map对象中插入新值。因此，它只是像标准的fibonacci函数一样运行，而不是用动态编程制作的快速版本。有人能告诉我我做错了什么吗？

int fib(int n, std::map<int, int> memo = {}) {
if (memo.count(n) >= 1) {
return memo[n];
}
if (n <= 2) {
return 1;
}
else {
int result = fib(n - 1, memo) + fib(n - 2, memo);
memo.insert(std::pair<int,int>(n,result));
return result;
}
}

Answer 1

每次都创建一个新的map，因为通过值而不是引用传递memo。

实现这一点的另一种方法是创建一次map，然后通过引用将其传递给实际实现。下面的例子做到了这一点，它的优点是它隐藏了你如何进行记忆：

int fib(int n)
{
std::map<int, int> memo;
return fib_impl(n, memo)
}
int fib_impl(int n, std::map<int, int> &memo) {
if (memo.count(n) >= 1) {
return memo[n];
}
if (n <= 2) {
return 1;
}
else {
int result = fib(n - 1, memo) + fib(n - 2, memo);
memo.insert(std::pair<int,int>(n,result));
return result;
}
}

Answer 2

将memo作为值类型传递会使事情变得更慢。您可以将备忘录作为参考类型传递，如下所示：

int fib(int n, std::map<int, int> &memo) {
if (memo.count(n) >= 1) {
return memo[n];
}
if (n <= 2) {
return 1;
}
else {
int result = fib(n - 1, memo) + fib(n - 2, memo);
memo.insert(std::pair<int,int>(n,result));
return result;
}
}
int main(){
map<int,int>memo;
cout<<fib(5,memo)<<"n";
}

或者，你可以全球申报备忘录。

map<int,int>memo; 
int fib(int n) {
if(memo.count(n)>=1)return memo[n];
if (n <= 2) {
return 1;
}
else {
int result = fib(n - 1) + fib(n - 2);
memo.insert(std::pair<int,int>(n,result));
return result;
}
}
int main(){

cout<<fib(10)<<"n";
}

Answer 3

正如其他答案所说，您正在按值传递备忘录，这样它就不会保留值并重用值。因为通过值传递可以防止备忘录被修改，因为只有副本被修改然后丢失。

你必须通过引用传递它。但通过引用传递有点棘手，因为您必须在函数之外创建备忘录，并手动将其传递给函数。其他答案给出了如何通过引用从外部传递的例子。

我想向你展示做这件事的其他方法。

第一种变体是创建并传递std:：shared_ptr。这种方法允许函数的用户不关心自己创建备忘录，他们不需要传递任何信息。除此之外，这个备忘录函数参数现在可能成为一个可选参数，并且可以通过函数调用自动创建。让我们看看它看起来是什么样子：

在线试用！

#include <map>
#include <memory>
#include <iostream>
int fib(int n, std::shared_ptr<std::map<int, int>> memo =
std::make_shared<std::map<int, int>>()) {
if (memo->count(n))
return memo->at(n);
if (n <= 2)
return 1;
else {
int result = fib(n - 1, memo) + fib(n - 2, memo);
memo->insert(std::pair<int, int>(n, result));
return result;
}
}
int main() {
std::cout << fib(45) << std::endl;
}

输出：

1134903170

这是斐波那契45的正确输出，正如我们在WolframAlpha页面中看到的。

可以看出，在上面的方法中，我不必向fibonacci函数传递任何信息，带有共享指针的可选参数是自动创建的。

人们可能会倾向于将可选参数作为可变引用传递，比如：

int fib(int n, std::map<int, int> & memo = std::map<int, int>()) {
..........
fib(n - 1, memo) + ...
}

上面的这种语法非常方便，可以解决问题，但不幸的是，C++无法将临时对象分配给可变引用。所以上面的代码不起作用，也无法编译。

只能将临时对象分配给const &，如下所示：

std::map<int, int> const & memo = std::map<int, int>()

但const引用将不允许我们修改底层memo并更改其值。

因此，在这种情况下，上面使用的共享指针通过允许创建临时对象并允许修改它并递归传递来节省我们的时间。

解决任务的一个更有趣的方法是在函数体中使用thread_local变量：

在线试用！

#include <map>
#include <memory>
#include <iostream>
int fib(int n) {
thread_local std::map<int, int> memo;
if (memo.count(n))
return memo.at(n);
if (n <= 2)
return 1;
else {
int result = fib(n - 1) + fib(n - 2);
memo.insert(std::pair<int, int>(n, result));
return result;
}
}
int main() {
std::cout << fib(45) << std::endl;
}

上面的解决方案允许我们根本不向函数传递任何内容，而是将memo作为本地函数的变量。

线程局部修饰符允许我们为每个线程重用备忘录中相同的计算值。如果您打算使用来自多个核心和/或线程的函数，那么这个thread_local修饰符非常方便。这个修饰符不允许使用任何互斥来同步对它的写入。但是memo值只能在每个线程中单独共享。下一个解决方案通过使用static修饰符在所有线程之间共享值来避免这种情况。

在线试用！

#include <map>
#include <memory>
#include <iostream>
int fib(int n) {
static std::map<int, int> memo;
if (memo.count(n))
return memo.at(n);
if (n <= 2)
return 1;
else {
int result = fib(n - 1) + fib(n - 2);
memo.insert(std::pair<int, int>(n, result));
return result;
}
}
int main() {
std::cout << fib(45) << std::endl;
}

上面的static方法和线程本地方法一样，允许不向函数传递任何内容。此外，它还允许在不同的调用之间以及不同的线程/核心之间全局共享所有备忘录值。但与线程本地解决方案不同的是，静态方法不是线程安全的，这意味着在没有互斥同步的情况下无法使用它，所以实际使用静态变量的正确方法如下：

在线试用！

#include <map>
#include <memory>
#include <iostream>
#include <mutex>
int fib(int n) {
static std::recursive_mutex mux;
static std::map<int, int> memo;
std::lock_guard<std::recursive_mutex> lock(mux);

if (memo.count(n))
return memo.at(n);
if (n <= 2)
return 1;
else {
int result = fib(n - 1) + fib(n - 2);
memo.insert(std::pair<int, int>(n, result));
return result;
}
}
int main() {
std::cout << fib(45) << std::endl;
}

可以在上面看到，我使用了递归互斥，这是同步递归函数的正确方式。现在有了这个互斥锁，我们的函数是线程安全的，这意味着我们可以在多核心线程上使用它。