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

Question

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

import sys

sys.setrecursionlimit(100000)

我正在使用合并排序，当我在一个包含80000个元素的列表上尝试它时，python“意外退出”。这不是我迭代实现合并排序的问题，但我对递归排序很感兴趣。

我使用的是Mac 8 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。

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

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