使用地图进行记忆

Question

我正在尝试使用map优化递归问题来处理运行时错误。但是，使用memoization方法并实现地图仍然无法完全解决问题。通过使用天真的递归方式，分段错误错误将不会出现，直到totalNum = 36.优化后，当totalNum变得非常大时，分段错误错误仍将显示，如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

优化（和memoization，作为一种优化技术）用于将慢速代码转换为更快的代码，而不是容易出错的代码转换为无错误的代码。

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

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

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

但是，因为在memoization之后，segfault发生在更大的数字（totalNum），它可能与堆栈大小有关。在C ++中，递归通常会导致堆栈使用量不断增加，并且您可以轻松地使用通常由操作系统提供的所有堆栈（导致堆栈溢出，这通常表示为段错误）。这可能是分段错误的根源。如果您使用的是Linux，请尝试使用ulimit -s来查看当前的堆栈大小并粗暴地增加它（通过使用像ulimit -s 65536这样的64 Mb堆栈），看看是否会让你在更大的totalNum上有一个段错误。如果是这样，那么您现在知道您的问题是堆栈溢出。 Then it will be easier to find solutions for it。因此，无错误的解决方案是将递归算法更改为基于任务的算法（即，设置要处理的值的队列，循环它并处理它的项而不是使用递归）。

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

另外，如果你提供了一个最小的工作示例，一个虚拟主函数和编译所需的一切，那将是非常好的。

Answer 2

即使totalNum大于99999，有没有办法解决这个运行时问题？摆脱递归。很容易弄清楚计算值(r, b)所需的值。您可以使用循环来计算它们。

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

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