如何在计算Ackermann时检查堆栈使用情况

我正在了解我的系统计算Ackermann算法的两个和三个参数版本的能力。对于非常小的m和n值，我的系统将计算并打印从A0和A1方法调用返回的结果。然而，高于3或4的任何东西都不会返回并冻结我使用atm的终端。我的问题是，我确定我的机器可以计算出m和n的值。如何在计算Ackermann时检查堆栈使用情况

我已经尝试了一些事情来捕捉堆栈溢出，对于我所知的C++没有可以捕获的stackoverflowexception。 try-catch块不起作用。在下面的代码中，我使用getrlimit（）来查找堆栈限制，在主gStackRef中创建一个地址位置。我调用checkStack递归检查局部变量指针gStackLimit。

有没有更好的方法来检查我的堆栈使用与递归方法有关？我还要检查段故障吗？我会让你知道我在unix终端上运行。

#include <cstdlib> 
#include <iostream> 


#define _XOPEN_SOURCE_EXTENDED 1 
#include <sys/resource.h> 

int getrlimit(int resource, struct rlimit *rlp); 

using namespace std; 

int * gStackRef; 
int gStackLimit; 

void checkStack(void); 

int main(int argc, char *argv[]) 
{ 
     int temp = 0; 
     gStackRef = &temp; 
     rlimit myl; 
     getrlimit(RLIMIT_STACK, &myl); 
     gStackLimit = (myl.rlim_cur/3 * 8/10) ;/* modified for segment fault */ 
     cout << gStackLimit << "\n"; 
     checkStack(); 
} 

void checkStack() 
{ 
     int temp = 0; 
     int* pVariableHere = &temp; 
     size_t stackUsage = gStackRef - pVariableHere; 
     printf("Stack usage: %d/%d \n", stackUsage, gStackLimit); 
     if(stackUsage > gStackLimit) return; 
     else checkStack(); 
}

来源

2011-09-27 ASLilly

1.固定标题的拼写错误。 2.重新标记的C++ - > C;这里没有C++。 3.用POSIX标记，因为这是你明显建立在其上的API。 –

通过动态规划（对于它的价值，使用某种形式的动态规划，而不是递归的可能是最好的计算阿克曼），你是说我尽量节省A0和A1的返回的值的表？这样我可以在进行另一次递归调用之前检查表格并节省一些空间。 – ASLilly

是的，动态规划是一种表驱动算法求解方法。有关更多详细信息，请参阅我的答案中链接的wikipedia文章。 AFAIK你不需要超过'm * n'的空间和时间来使用表格来计算。（尽管我可能是错的;我自己也没有实现）考虑一个类似的情况，即斐波那契数列，它按照递归计算指数时间，但只使用动态规划计算线性时间。 –

然而任何超过3或4更高不返回并冻结我使用ATM终端。

这就是阿克曼功能的要点。它增长得非常快。对于m >= 4和n >= 3，如果你递归计算A(m, n)，我怀疑你的函数会在你死前返回。

我已经尝试了一些事情来捕捉堆栈溢出，因为我知道C++没有可以捕获的stackoverflowexception。

当然不是。该进程没有堆栈空间。它应该立即拆除。

有没有更好的方式来检查我的堆栈使用与递归方法有关？

如果您必须使用递归，请通过创建自己的堆栈数据结构来手动执行此操作，该堆栈数据结构分配在堆上而不是堆栈空间中。用它来跟踪你在递归中的位置。推送和弹出，并在递归时，而不是通过嵌套方法调用递归。

但最后，你不应该使用递归来计算阿克曼无论如何。

来源

2011-09-27 18:36:29 jason

你能详细说明为什么你不应该使用递归来计算Ackermann？我认为这不能用迭代循环来完成。 –

我已经尝试了一些事情来捕捉堆栈溢出，我知道C++没有stackoverflowexception我可以捕获。 try-catch块不起作用。在下面的代码中，我使用getrlimit（）来查找堆栈限制，在主gStackRef中创建一个地址位置。我调用checkStack递归检查局部变量指针gStackLimit。

POSIX没有检测堆栈溢出的“安全”方法。堆栈溢出导致SIGSEGV信号，您（通常）不应该捕获这些信号，因为它们也表示一般的分段错误，which should crash your program。 Windows环境可以安全地处理堆栈溢出，使用EXCEPTION_STACK_OVERFLOW - 但在这种情况下，Windows正在做的仅仅是在堆栈末尾放置一个防护页并通知SEH。如果你用完了保护页面（在忽略了SEH异常之后），那么你的程序就会被终止（就像它在POSIX-land中那样）。

有没有更好的方式来检查我的堆栈使用与递归方法有关？我还要检查段故障吗？我会让你知道我在unix终端上运行。

号你在做什么，即使有不确定的行为。在一些机器上，堆栈增长。在一些机器上堆叠增长下来。编译器可能会在两个方法之间插入任何数量的slop空间。从技术上讲，编译器可以实现这样的事情，即有两个单独的堆栈，位于两个完全不同的内存段中，并且仍然符合要求。

如果要计算阿克曼堆栈中的安全的方式，既可以使用从堆中分配一个明确的堆栈结构，或使用dynamic programming。

来源

2011-09-27 18:37:09

如何在计算Ackermann时检查堆栈使用情况

回答

相关问题