Как справиться с ошибкой рекурсии в python? - PullRequest
Новая
       5

Как справиться с ошибкой рекурсии в python?

2 голосов
/ 01 февраля 2020

Сначала я создаю 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)

Но Программа заканчивается где-то в середине, и я не получаю никаких результатов.

Как я могу это исправить?

1 Ответ

2 голосов
/ 01 февраля 2020

Некоторые наблюдения:

  • Ваш упрощенный вопрос не учитывает важный аспект, который присутствовал в более ранней версии вашего вопроса: ваш исходный код также включает вызов функции итеративной сортировки
  • Этот тест смещен, потому что сначала вы сортируете список с помощью итеративного метода, а затем используете тот же список - который теперь отсортирован - с вашей реализацией быстрой сортировки
  • Ваша реализация быстрой сортировки попадет в наихудший случай, когда список ввода уже отсортирован. Переменная pos станет равной end, и поэтому при следующем разбиении будет отрублено только одно значение, то есть глубина рекурсии будет равна числу элементов в вашем списке. Таким образом, для больших списков вы столкнетесь с пределом рекурсии.

Таким образом, если учитывать случайность ваших входных списков, достаточно решить первую проблему. Замените эти строки: 

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

на: 

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

... и больше проблем не должно быть.

...