如何处理python中的递归错误?

马丁

首先,我创建6个随机数列表,每个列表的长度都不同:

arr = [random.randint(1,15000) for _ in range(1000)]

numbersList = [10,100,500,1000,5000,8000]
numbersForBenchmark = []
for i in range(len(numbersList)):
    arr = [random.randint(1,15000) for _ in range(numbersList[i])]
    numbersForBenchmark.append(arr)

print(numbersForBenchmark)
recursionTimeArray = []

现在我有一个递归QuickSort:

def partition(lst, start, end):
    pos = start                           

    for i in range(start, end):           
        if lst[i] < lst[end]:            
            lst[i],lst[pos] = lst[pos],lst[i]
            pos += 1

    lst[pos],lst[end] = lst[end],lst[pos] 
    return pos

def quick_sort_recursive(lst, start, end):
    if start < end:                     
        pos = partition(lst, start, end)
        quick_sort_recursive(lst, start, pos - 1)
        quick_sort_recursive(lst, pos + 1, end)

然后驱动程序在所有阵列上工作:

for i in range(len(numbersForBenchmark)):
   arrRe = numbersForBenchmark[i]
   try:
        n = len(arrRe)
        start = time.time()
        quick_sort_recursive(arrRe,0,n-1)
        end = time.time()
        rekTime = end - start
        recursionTimeArray.append(rekTime)
   except RecursionError as re:
        print('Problem with recursive depth!)

如您所见,我测量time并将时间放入一个数组中。但是我需要6个结果(我有6个数组),但是在两个示例中,两次出现错误:

    print('Problem with recursive depth!)

我试图用以下方法处理它:

import sys
sys.setrecursionlimit(1500)

但是程序在中间的某个地方完成了,我没有得到任何结果。

我怎样才能解决这个问题?

亭子

一些观察:

  • 简化的问题遗漏了早期版本中存在的重要方面:原始代码还包括对迭代排序函数的调用
  • 该测试是有偏见的,因为您首先使用迭代方法对列表进行排序,然后在您的quicksort实现中使用相同的列表(现已排序)
  • 当输入列表已经排序时,您的quicksort实现将进入最坏的情况。pos变量将等于end,因此下一个分区将仅截取一个值,这意味着您的递归深度将等于列表中元素的数量。对于较大的列表,您将因此遇到递归限制。

因此,依靠输入列表的随机性,仅解决第一个问题就足够了。替换这些行:

arrIt = numbersForBenchmark[i]
arrRe = numbersForBenchmark[i]

与:

arrIt = numbersForBenchmark[i][:]
arrRe = numbersForBenchmark[i][:]

...而且应该没有其他问题了。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章