如何防止Ackerman函数溢出堆栈？ [英] How can I prevent my Ackerman function from overflowing the stack?
问题描述
有没有一种方法可以防止我的Ackerman函数创建溢出堆栈，它是针对相对较小的数字执行的，即（4,2）。这是错误
{由于当前线程处于堆栈
溢出状态，因此无法评估表达式。}
private void Button1Click（对象发送者，EventArgs e）
{
var t =阿克曼（4,2）;
label1.Text + = string.Format（：{0}，t）;
label1.Visible = true;
}
int Ackermann（uint m，uint n）
{
if（m == 0）
return（int）（n + 1 ）;
if（m> 0&& n == 0）
return Ackermann（m-1，1）;
if（m> 0&& n> 0）
return Ackermann（m-1，（uint）Ackermann（m，n-1））;
else
{
return -1;
}
}
避免 StackOverflowException 的最佳方法是不使用堆栈。
让我们摆脱负面的情况，因为当我们使用 uint 调用时没有意义。另外，如果在我们考虑其他可能性之前，如果使否定测试成为方法中的第一件事，那么下面的内容也将起作用：
首先，我们要需要更大的船：
public static BigInteger Ackermann（BigInteger m，BigInteger n）
{
如果（m == 0）
返回n + 1;
if（n == 0）
return Ackermann（m-1，1）;
else
返回Ackermann（m-1，Ackermann（m，n-1））;
}
现在至少在数学上是可能的。现在， n == 0 的情况很简单。让我们手动消除它。我们将使用 goto 因为它是临时的，所以我们不必担心速激肽或Dijkstra：
公共静态BigInteger Ackermann（BigInteger m，BigInteger n）
{
重新启动：
如果（m == 0）
返回n + 1;
if（n == 0）
{
m--;
n = 1;
goto重新启动；
}
其他
返回Ackermann（m-1，Ackermann（m，n-1））;
}
这会花更长的时间才能吹起烟囱，但吹倒它，它会。不过，从此表格来看，请注意， m 从未通过递归调用的返回来设置，而 n 有时是。
扩展这一点，我们可以将其转换为迭代形式，而不必处理跟踪先前的 m ，然后以递归形式返回，则以迭代形式将其分配给 n 。一旦我们用完等待处理的 m ，我们将返回当前值 n ：
公共静态BigInteger Ackermann（BigInteger m，BigInteger n）
{
Stack< BigInteger> stack =新Stack< BigInteger>（）;
stack.Push（m）;
while（stack.Count！= 0）
{
m = stack.Pop（）;
if（m == 0）
n = n +1;
else if（n == 0）
{
stack.Push（m-1）;
n = 1;
}
else
{
stack.Push（m-1）;
stack.Push（m）;
--n;
}
}
返回n；
}
至此，我们已经回答了OP的问题。这将花费很长时间，但是会返回尝试的值（m = 4，n = 2）。它将永远不会抛出 StackOverflowException ，尽管它最终会耗尽某些 m 和<$的值的内存。 c $ c> n 。
为进一步优化，我们可以跳过向堆栈中添加值的操作，只是在以下操作后立即将其弹出：
公共静态BigInteger Ackermann（BigInteger m，BigInteger n）
{
Stack< BigInteger> stack =新Stack< BigInteger>（）;
stack.Push（m）;
while（stack.Count！= 0）
{
m = stack.Pop（）;
skipStack：
if（m == 0）
n = n +1;
else if（n == 0）
{
--m;
n = 1;
转到skipStack;
}
else
{
stack.Push（m-1）;
--n;
转到skipStack;
}
}
返回n；
}
这不会帮助我们使用堆栈，也不会有意义地使用堆，但是鉴于
消除 goto >，同时保持最佳化的做法留给读者练习：）
顺便说一句，我对此测试太耐心了，所以我做了一个使用已知属性的作弊表格m小于3时，Ackerman函数的值：
公共静态BigInteger Ackermann（BigInteger m，BigInteger n）
{
Stack< BigInteger> stack =新Stack< BigInteger>（）;
stack.Push（m）;
while（stack.Count！= 0）
{
m = stack.Pop（）;
skipStack：
if（m == 0）
n = n +1;
else if（m == 1）
n = n + 2;
else if（m == 2）
n = n * 2 + 3;
else if（n == 0）
{
--m;
n = 1;
转到skipStack;
}
else
{
stack.Push（m-1）;
--n;
转到skipStack;
}
}
返回n；
}
使用此版本，我可以获得的结果true for Ackermann（4，2）== BigInteger.Pow（2，65536）-3 一秒钟后（Mono，发行版）构建，并在Core i7上运行）。鉴于非作弊版本在为 m 这样的值返回正确结果时是一致的，因此我将其作为先前版本正确性的合理证据，但我
编辑：当然，我并不是真的希望以前的版本会在任何合理的时间范围内返回，但是我想我会离开它仍在运行，并查看其内存使用情况如何。 6小时后，它位于40MiB以下的位置。我很高兴，尽管显然不切实际，但如果在真实的计算机上给予足够的时间，它的确会返回。
编辑：显然有人认为 Stack< T> 达到其23.1的内部限制也算是一种堆栈溢出。如果必须，我们也可以处理该问题。
公共类OverflowlessStack< T>
{
内部密封类SinglyLinkedNode
{
//越大越好，但是我们要足够低
//来说明节点溢出的情况
//，然后创建另一个。
private const int ArraySize = 2048;
T [] _array;
int _size;
public SinglyLinkedNode接下来；
public SinglyLinkedNode（）
{
_array = new T [ArraySize];
}
public bool IsEmpty {get {return _size == 0;}}}
public SinglyLinkedNode Push（T item）
{
if（_size == ArraySize- 1）
{
SinglyLinkedNode n = new SinglyLinkedNode（）;
n.Next = this;
n.Push（item）;
返回n；
}
_array [_size ++] =项目；
返回此值；
}
public T Pop（）
{
return _array [--_ size];
}
}
private SinglyLinkedNode _head = new SinglyLinkedNode（）;
public T Pop（）
{
T ret = _head.Pop（）;
if（_head.IsEmpty& _amp; _head.Next！= null）
_head = _head.Next;
回程；
}
public void Push（T项目）
{
_head = _head.Push（item）;
}
公共布尔IsEmpty
{
get {return _head.Next == null&& _head.IsEmpty; }
}
}
公共静态BigInteger Ackermann（BigInteger m，BigInteger n）
{
var stack = new OverflowlessStack< BigInteger>（）;
stack.Push（m）;
while（！stack.IsEmpty）
{
m = stack.Pop（）;
skipStack：
if（m == 0）
n = n +1;
else if（m == 1）
n = n + 2;
else if（m == 2）
n = n * 2 + 3;
else if（n == 0）
{
--m;
n = 1;
转到skipStack;
}
else
{
stack.Push（m-1）;
--n;
转到skipStack;
}
}
返回n；
}
再次调用 Ackermann（4，2）返回：
这是正确的结果。使用的堆栈结构将永远不会抛出，因此剩下的唯一限制是堆（当然，对于足够大的输入，您将必须使用 Universe Lifetime作为度量单位...）。
由于其使用方式类似于图灵机的磁带，因此我们想起了一个论点，即可以在足够大小的图灵机上计算任何可计算函数。
Is there a way to keep my Ackerman function from creating a stack over flow is does it for relatively small numbers , i.e. (4,2). This is the error
{Cannot evaluate expression because the current thread is in a stack overflow state.}
private void Button1Click(object sender, EventArgs e)
{
var t = Ackermann(4,2);
label1.Text += string.Format(": {0}", t);
label1.Visible = true;
}
int Ackermann(uint m, uint n)
{
if (m == 0)
return (int) (n+1);
if (m > 0 && n == 0)
return Ackermann(m - 1, 1);
if (m > 0 && n > 0)
return Ackermann(m - 1, (uint)Ackermann(m, n - 1));
else
{
return -1;
}
}
The best way to avoid StackOverflowException is to not use the stack.
Let's get rid of the negative case, as it's meaningless when we call with uint. Alternatively, what follows here will also work if we make the negative test the very first thing in the method, before the other possibilities are considered:
First, we're going to need a bigger boat:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
if (m == 0)
return n+1;
if (n == 0)
return Ackermann(m - 1, 1);
else
return Ackermann(m - 1, Ackermann(m, n - 1));
}
Now success is at least mathematically possible. Now, the n == 0 case is a simple enough tail-call. Let's eliminate that by hand. We'll use goto because it's temporary so we don't have to worry about velociraptors or Dijkstra:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
if (m == 0)
return n+1;
if (n == 0)
{
m--;
n = 1;
goto restart;
}
else
return Ackermann(m - 1, Ackermann(m, n - 1));
}
This will already take a bit longer to blow the stack, but blow it, it will. Looking at this form though, note that m is never set by the return of a recursive call, while n sometimes is.
Extending this, we can turn this into an iterative form, while only having to deal with tracking previous values of m, and where we would return in the recursive form, we assign to n in our iterative form. Once we run out of ms waiting to be dealt with, we return the current value of n:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
Stack<BigInteger> stack = new Stack<BigInteger>();
stack.Push(m);
while(stack.Count != 0)
{
m = stack.Pop();
if(m == 0)
n = n + 1;
else if(n == 0)
{
stack.Push(m - 1);
n = 1;
}
else
{
stack.Push(m - 1);
stack.Push(m);
--n;
}
}
return n;
}
At this point, we have answered the OP's question. This will take a long time to run, but it will return with the values tried (m = 4, n = 2). It will never throw a StackOverflowException, though it will end up running out of memory above certain values of m and n.
As a further optimisation, we can skip adding a value to the stack, only to pop it immediately after:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
Stack<BigInteger> stack = new Stack<BigInteger>();
stack.Push(m);
while(stack.Count != 0)
{
m = stack.Pop();
skipStack:
if(m == 0)
n = n + 1;
else if(n == 0)
{
--m;
n = 1;
goto skipStack;
}
else
{
stack.Push(m - 1);
--n;
goto skipStack;
}
}
return n;
}
This doesn't help us with stack nor meaningfully with heap, but given the number of loops this thing will do with large values, every bit we can shave off is worth it.
Eliminating goto while keeping that optimisation is left as an exercise for the reader :)
Incidentally, I got too impatient in testing this, so I did a cheating form that uses known properties of the Ackerman function when m is less than 3:
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
Stack<BigInteger> stack = new Stack<BigInteger>();
stack.Push(m);
while(stack.Count != 0)
{
m = stack.Pop();
skipStack:
if(m == 0)
n = n + 1;
else if(m == 1)
n = n + 2;
else if(m == 2)
n = n * 2 + 3;
else if(n == 0)
{
--m;
n = 1;
goto skipStack;
}
else
{
stack.Push(m - 1);
--n;
goto skipStack;
}
}
return n;
}
With this version, I can get a result of true for Ackermann(4, 2) == BigInteger.Pow(2, 65536) - 3 after a little over a second (Mono, Release build, running on a Core i7). Given that the non-cheating version is consistent in returning the correct result for such values of m, I take this as reasonable evidence of the correctness of the previous version, but I'll leave it running and see.
Edit: Of course, I'm not really expecting the previous version to return in any sensible timeframe, but I thought I'd leave it running anyway and see how its memory use went. After 6 hours it's sitting nicely under 40MiB. I'm pretty happy that while clearly impractical, it would indeed return if given enough time on a real machine.
Edit: Apparently it's being argued that Stack<T> hitting its internal limit of 2³¹ items counts as a sort of "stack overflow", too. We can deal with that also if we must:
public class OverflowlessStack <T>
{
internal sealed class SinglyLinkedNode
{
//Larger the better, but we want to be low enough
//to demonstrate the case where we overflow a node
//and hence create another.
private const int ArraySize = 2048;
T [] _array;
int _size;
public SinglyLinkedNode Next;
public SinglyLinkedNode()
{
_array = new T[ArraySize];
}
public bool IsEmpty{ get{return _size == 0;} }
public SinglyLinkedNode Push(T item)
{
if(_size == ArraySize - 1)
{
SinglyLinkedNode n = new SinglyLinkedNode();
n.Next = this;
n.Push(item);
return n;
}
_array [_size++] = item;
return this;
}
public T Pop()
{
return _array[--_size];
}
}
private SinglyLinkedNode _head = new SinglyLinkedNode();
public T Pop ()
{
T ret = _head.Pop();
if(_head.IsEmpty && _head.Next != null)
_head = _head.Next;
return ret;
}
public void Push (T item)
{
_head = _head.Push(item);
}
public bool IsEmpty
{
get { return _head.Next == null && _head.IsEmpty; }
}
}
public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
var stack = new OverflowlessStack<BigInteger>();
stack.Push(m);
while(!stack.IsEmpty)
{
m = stack.Pop();
skipStack:
if(m == 0)
n = n + 1;
else if(m == 1)
n = n + 2;
else if(m == 2)
n = n * 2 + 3;
else if(n == 0)
{
--m;
n = 1;
goto skipStack;
}
else
{
stack.Push(m - 1);
--n;
goto skipStack;
}
}
return n;
}
Again, calling Ackermann(4, 2) returns:
Which is the correct result. The stack structure used will never throw, so the only limit remaining is the heap (and time of course, with large enough inputs you'll have to use "universe lifetime" as a unit of measurement...).
Since the way it's used is analogous to the tape of a Turing machine, we're reminded of the thesis that any calculable function can be calculated on a Turing machine of sufficient size.
这篇关于如何防止Ackerman函数溢出堆栈？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
