Использование быстрой сортировки в списках> = 7000 вызывает переполнение стека - PullRequest
Новая
       37

Использование быстрой сортировки в списках> = 7000 вызывает переполнение стека

0 голосов
/ 27 мая 2019

Я пытаюсь проверить время вычислений нескольких алгоритмов сортировки на все более крупных наборах данных.Quicksort имеет ошибку памяти при достижении 7000.

Я установил предел рекурсии на 10 ** 6, чтобы бороться с максимальной глубиной рекурсии при использовании timsort 

from random import randint
import time
import math
start = 1000
finish = 10000
inc = 1000
import  sys
sys.setrecursionlimit(10**6)
def generateNew(z):
    listt = []
    for o in range(z):
        listt.append(randint(0, z))
    return listt

...


def partition(arr,low,high): 
    i = ( low-1 )
    pivot = arr[high]

    for j in range(low , high): 
        if   arr[j] <= pivot: 
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 

    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 
def quickSort(arr,low,high): 
    if low < high: 
        pi = partition(arr,low,high) 
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high) 

def quickSortTimer(unsorted):
    start = time.time()
    array = unsorted
    quickSort(array,0,len(array)-1) 

    end = time.time()
    print("Quick Sort: "+str(end - start))


...


def runAll():


    for h in range(start, finish+1, inc):
        print("\n\nCurrent: "+str(h))
        unsorted = generateNew(h)
        oddEvenSortTimer(unsorted)
        #stoogeSortTimer(unsorted)
        gnomeSortTimer(unsorted)
        #bogoSortTimer(unsorted)
        binaryInserionSortTimer(unsorted)
        pancakeSortTimer(unsorted)
        bitonicSortTimer(unsorted)
        cocktailSortTimer(unsorted)
        cycleSortTimer(unsorted)
        pigeonholeSortTimer(unsorted)
        combSortTimer(unsorted)
        timSortTimer(unsorted)
        shellSortTimer(unsorted)
        bucketSortTimer(unsorted)
        radixSortTimer(unsorted)
        heapSortTimer(unsorted)
        quickSortTimer(unsorted)
        mergeSortTimer(unsorted)
        selectionSortTimer(unsorted)
        insertionSortTimer(unsorted)
        bubbleSortTimer(unsorted)

Я ожидаюпрограмма продолжает работать, но вместо этого я получаю сообщение об ошибке: MemoryError: переполнение стека.Этот вопрос был отмечен как дубликат другого вопроса, объясняющего, как увеличить глубину рекурсии, но это еще одна ошибка.Я хочу сохранить глубину рекурсии, но избежать ошибки переполнения стека.

1 Ответ

1 голос
/ 28 мая 2019

Чтобы избежать переполнения стека, используйте рекурсию для меньшей (или равной) части, а затем повторите итерацию для обработки большей части. 

def quicksort(a, lo, hi):
    while(hi - lo > 0):
        pivot = a[hi]
        i = lo
        for j in xrange(lo, hi):
            if a[j] <= pivot:
                a[i],a[j] = a[j],a[i]
                i += 1
        a[i],a[hi] = a[hi],a[i]
        if(i - lo <= hi - i):
            quicksort(a, lo, i-1)
            lo = i+1
        else:
            quicksort(a, i+1, hi)
            hi = i-1
...