如何防止我的 Ackerman 函数溢出堆栈? [英] How can I prevent my Ackerman function from overflowing the stack?
问题描述
有没有办法防止我的 Ackerman 函数创建堆栈溢出是针对相对较小的数字，即 (4,2).这是错误
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;
}
}
推荐答案
避免StackOverflowException的最好方法是不使用堆栈.
The best way to avoid StackOverflowException is to not use the stack.
让我们摆脱否定的情况，因为当我们使用 uint 调用时它毫无意义.或者，如果我们在考虑其他可能性之前将否定测试作为方法中的第一件事，那么下面的内容也将起作用:
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));
}
现在成功至少在数学上是可能的.现在， n == 0 情况是一个足够简单的尾调用.让我们手动消除它.我们将使用 goto 因为它是临时的，所以我们不必担心 velociraptors 或 Dijkstra:
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));
}
这已经需要更长的时间来炸毁堆栈，但是炸毁它，它会.看看这个形式，请注意 m 永远不会由递归调用的返回设置，而 n 有时是.
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.
扩展这个，我们可以把它变成一个迭代形式，而只需要处理跟踪m的先前值，并且我们以递归形式返回的地方，我们分配给n 在我们的迭代形式中.一旦我们用完等待处理的ms，我们返回n的当前值:
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;
}
此时，我们已经回答了 OP 的问题.这将需要很长时间才能运行，但它会返回所尝试的值 (m = 4, n = 2).它永远不会抛出 StackOverflowException，尽管它最终会耗尽 m 和 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.
消除goto，同时保持优化留给读者作为练习:)
Eliminating goto while keeping that optimisation is left as an exercise for the reader :)
顺便说一句，我在测试这个时太不耐烦了，所以我做了一个作弊形式，当 m 小于 3 时，使用阿克曼函数的已知属性:
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;
}
使用这个版本，我可以得到 true for Ackermann(4, 2) == BigInteger.Pow(2, 65536) - 3 的结果超过一秒钟(Mono，发布版本，在 Core i7 上运行).鉴于非作弊版本在为 m 的此类值返回正确结果方面是一致的，我认为这是前一版本正确性的合理证据，但我将让它继续运行并查看.
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.
当然，我并不真正期望以前的版本在任何合理的时间范围内返回，但我认为无论如何我都会让它继续运行，看看它的内存使用情况如何.6 小时后，它很好地低于 40MiB.我很高兴虽然显然不切实际，但如果在真机上给予足够的时间，它确实会恢复.
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.
显然有人认为 Stack 达到其 2³¹ 项的内部限制也算作一种堆栈溢出".如果必须，我们也可以处理:
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;
}
再次调用 Ackermann(4, 2) 返回:
这是正确的结果.所使用的堆栈结构永远不会抛出，因此剩下的唯一限制是堆(当然还有时间，如果输入足够大，您将不得不使用宇宙生命周期"作为度量单位......).
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屋！
