将 python 中的递归深度增加到 100000

Question

python 有一个默认的最大递归深度，我可以增加它：

import sys

sys.setrecursionlimit(100000)

我正在使用归并排序，当我在包含 80000 个元素的列表上尝试它时，python "quits unexpectedly"。这不是我迭代实现合并排序的问题，但我对递归排序感兴趣。

我使用的是 Mac OSX 8GB 内存。有没有办法让它在我的机器上运行，或者它会在更好的机器上运行？

import sys

sys.setrecursionlimit(100000) # python has a recurison depth of < 1000~. so for the purpose of this assignment I'm increasing it

counter = 0


def merge_sort(lst):
    global counter
    if len(lst) <= 1:
        counter += 1   # increment counter when we divide array in two
        return lst
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)


def merge(left, right):
    global counter
    if not left:
        counter += 1   # increment counter when not left (not left - is also comparison)
        return right
    if not right:
        counter += 1   # the same as above for right
        return left
    if left[0] < right[0]:
        counter += 1   # and the final one increment
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])


lines = [line.rstrip('\n') for line in open('words.txt')]

当我在 40000 上尝试上述操作时，它起作用并对列表进行排序：

print(merge_sort(lines[0:40000]))

但在 50000 或以上时则不会。 .txt文件总字数80000左右

我收到的消息：

Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)

Answer 1

问题来自您的 merge(left, right) 实现，它在 O(n) 中是递归的。在每个递归步骤中，您将两个排序列表按一个元素合并。合并递归的想法在优化尾递归的语言中可能有意义，but it is not the case in python。

一般来说，合并是迭代的，因为它的复杂性始终至少是要合并的元素数。

def merge(left, right):
    merged = []
    i = 0
    j = 0
    while i < len(left) and j < len(right) :
        if left[i] < right[j]:
            merged.append(left[i])
            i+=1
        else:
            merged.append(right[j])
            j+=1
    merged += left[i:]
    merged += right[j:]
    return merged

将 python 中的递归深度增加到 100000

increasing recursion depth in python to 100000

python

memory

recursion

ram

stack