首先,我创建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)
但是程序在中间的某个地方完成了,我没有得到任何结果。
我怎样才能解决这个问题?
一些观察:
pos
变量将等于end
,因此下一个分区将仅截取一个值,这意味着您的递归深度将等于列表中元素的数量。对于较大的列表,您将因此遇到递归限制。因此,依靠输入列表的随机性,仅解决第一个问题就足够了。替换这些行:
arrIt = numbersForBenchmark[i]
arrRe = numbersForBenchmark[i]
与:
arrIt = numbersForBenchmark[i][:]
arrRe = numbersForBenchmark[i][:]
...而且应该没有其他问题了。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句