使用地图记忆

Question

我正在尝试使用 map 来优化递归问题以处理运行时错误。然而，使用记忆方法和实现地图仍然不能完全解决问题。通过使用递归的朴素方式，直到totalNum = 36才会出现segmentation fault错误。优化后，当totalNum变得非常大时，segmentation fault错误仍然会出现，比如99999。即使 totalNum 大于 99999，是否有任何方法可以解决此运行时问题？以下是我的头文件代码：

using namespace std; 
static map<pair<int, int>, double> map;

double val(int r, int b){   
if (0 == r)
    return ((double) b);
if (0 == b)
    return (0);
if (map.find(make_pair(r, b)) != map.end()){
    return (double)map[make_pair(r, b)];
} else{
    double num1 = ((double) r/(r+b)) * value(r-1, b);
    double num2 = ((double) b/(r+b)) * value(r, b-1);
    double value = max((num1 + num2), (double) (b - r));
    map[make_pair(r, b)] = value;
    return value;
}
}

#endif

它在 main() 中用于打印一条消息：cout << "Value = " << val(totalNum/2,totalNum/2) << endl;

Answer 1

优化（和记忆化，作为一种优化技术）用于将慢速代码变成更快的代码，而不是将容易出错的代码变成无错代码。

很可能您的段错误（请参阅 wiki 上的 common causes）与记忆无关。当然，添加记忆改变了段错误的频率和行为，但它并没有导致它也没有被删除。

段错误的最常见原因是尝试使用释放的（C++ 中的 deleted）指针，但您的代码不直接处理任何原始指针，所以这可能不是原因。

段错误的第二个最常见原因是返回对局部变量的引用，在这种情况下也不会发生这种情况。

但是，因为在记忆之后，段错误发生在更大的数字（totalNum）上，这可能与堆栈大小有关。在 C++ 中，递归通常会导致堆栈使用量不断增加，您可以很容易地用完操作系统通常提供的所有堆栈（导致堆栈溢出，通常以段错误的形式发出信号）。这可能是分段错误的来源。如果你在 linux，尝试使用 ulimit -s 查看你当前的堆栈大小并粗暴地增加它（通过使用类似 ulimit -s 65536 的东西来获得 64 Mb 的堆栈）看看这是否让你有totalNum 更大的段错误。如果是这样，那么您现在知道您的问题是堆栈溢出。 Then it will be easier to find solutions for it。那么，无错误的解决方案是将递归算法更改为基于任务的算法（即设置要处理的值队列，循环遍历它并处理其中的项目而不是使用递归）。

否则有更多的代码可以查看，因为段错误不太可能是由这段记忆代码引起的。

此外，如果您提供一个最小的工作示例，带有虚拟主函数和编译所需的一切，那就太好了。

Answer 2

Is there any way to solve this runtime problem even when the totalNum gets bigger than 99999? Get rid of the recursion. It's easy to figure out which values are required to calculate value (r, b). You can use a loop to calculate them.

递归版本的问题是它需要大量的堆栈space，这是相当有限的。因此，此解决方案无法扩展。记忆并没有改变这一点，因为函数参数和 return 值仍然需要保存在堆栈中。即使可以优化递归（通常仅使用尾递归），未优化的构建仍然不会运行。这可能意味着您无法有效地调试您的程序。

当您更改为循环时，您可以为函数参数重用堆栈 space，并且可以将结果存储在堆上。

使用地图记忆

Memoization using a map

c++

recursion

dictionary

memoization

data-structures