python - Python 段错误中修改的 Ackermann 函数

Question

因此，我尝试创建基本 Ackermann 函数的修改版本，该函数使用字典来存储已经计算的值，以便下次程序遇到类似的函数调用时，它可以使用已经计算的值，并且这个似乎大大加速了这个过程。这是代码:

import sys
sys.setrecursionlimit(100000)

resultset ={}

def ackermann(m, n):
    """Computes the Ackermann function A(m, n)

    See http://en.wikipedia.org/wiki/Ackermann_function

    n, m: non-negative integers
    """
    if (m,n) in resultset:
        return resultset[(m,n)]
    if m == 0:
        ans = n+1;
    elif n == 0:
        ans = ackermann(m-1, 1)
    else:
        ans = ackermann(m-1, ackermann(m, n-1))
    if m != 0:
        resultset[(m,n)] = ans
    return ans;

for i in range(0,10) :
    for j in range(0,10) :
        print("ackermann(%d, %d): " % (i, j) + str(ackermann(i,j)))

现在我遇到的问题是它会在很短的时间内停止执行。输出如下:

ackermann(0, 0): 1
ackermann(0, 1): 2
ackermann(0, 2): 3
ackermann(0, 3): 4
ackermann(0, 4): 5
ackermann(0, 5): 6
...
...
...
ackermann(3, 2): 29
ackermann(3, 3): 61
ackermann(3, 4): 125
ackermann(3, 5): 253
ackermann(3, 6): 509
ackermann(3, 7): 1021
ackermann(3, 8): 2045
ackermann(3, 9): 4093
ackermann(4, 0): 13
ackermann(4, 1): 65533
Segmentation fault

我的系统是具有 12 GB 内存的酷睿 i5，该程序在达到内存限制之前退出，可能是什么问题？

我还尝试使用 Shelves 而不是字典，以便它将数据存储在磁盘上。这是代码:

我还尝试使用书架而不是字典，这样我就可以看到磁盘上的使用情况。这是代码..

import sys
sys.setrecursionlimit(100000)

import shelve
resultset = shelve.open("file.o")

def ackermann(m, n):
    """Computes the Ackermann function A(m, n)

    See http://en.wikipedia.org/wiki/Ackermann_function

    n, m: non-negative integers
    """
    if str((m,n)) in resultset:
        return resultset[str((m,n))]
    if m == 0:
        ans = n+1;
    elif n == 0:
        ans = ackermann(m-1, 1)
    else:
        ans = ackermann(m-1, ackermann(m, n-1))
    if m != 0:
        resultset[str((m,n))] = ans
    return ans;

for i in range(0,6) :
    for j in range(0,6) :
        print("ackermann(%d, %d): " % (i, j) + str(ackermann(i,j)))

输出文件大小恰好为 6MB，并且 python 崩溃了。有人知道为什么吗？

Answer 1

经过大量的试验和错误，我了解到问题是由于递归，程序耗尽了堆栈空间。我可以通过将堆栈大小设置为无限来在 Linux 上修复此问题。不幸的是，我认为 Windows 上没有类似的解决方案。这是我所做的代码..

import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (resource.RLIM_INFINITY, resource.RLIM_INFINITY))
sys.setrecursionlimit(10**8)

resultset ={}

def ackermann(m, n):
    """Computes the Ackermann function A(m, n)

    See http://en.wikipedia.org/wiki/Ackermann_function

    n, m: non-negative integers
    """
    if (m,n) in resultset:
        return resultset[(m,n)]
    if m == 0:
        ans = n+1;
    elif n == 0:
        ans = ackermann(m-1, 1)
    else:
        ans = ackermann(m-1, ackermann(m, n-1))
    if m != 0:
        resultset[(m,n)] = ans
    return ans;

for i in range(0,6) :
    for j in range(0,6) :
        print("ackermann(%d, %d): " % (i, j) + str(ackermann(i,j)))

这两行是神奇发生的地方:

resource.setrlimit(resource.RLIMIT_STACK, (resource.RLIM_INFINITY, resource.RLIM_INFINITY)) sys.setrecursionlimit(10**8)

无论如何，感谢您的尝试。 :)