Python „maximale Rekursionstiefe überschritten“ multithreaded

Question

Ich verwende Python Multithreading Quicksort zu realisieren. Quicksort ist in einer Funktion implementieren. Es ist eine rekursive Funktion. Jeder Thread ruft Quicksort das Array zu sortieren, es hat. Jeder Thread verfügt über einen eigenen Array speichert, dass die Zahlen Bedarf sortiert werden. Wenn die Array-Größe kleiner ist (<10.000). Es läuft ok. Wenn jedoch die Array-Größe größer ist, es zeigt die „maximale Rekursionstiefe überschreiten“. Also, ich benutze setrecursionlimit () Funktion, um die Rekursionstiefe bis 1500. Aber das Programmabsturz direkt zurückgesetzt ... Im Folgenden ist quicksort Code. Es funktioniert gut, wenn nicht in Multi-Thread-Umgebung. Es scheint, mehrere Threads ist die Ursache für Rekursionstiefe Problem.

def partition (array, p, r):
    x = array[r]
    i = (p-1)
    j = p
    while (1):
        if array[j] <= x:
            i = (i+1)
            temp = array[j]
            array[j] = array[i]
            array[i] = temp
        j+=1
        if j == r:
            break
    temp = array[i+1]
    array[i+1] = array[r]
    array[r] = temp
    return i+1

def quicksort (array, p, r):
    if p < r:
        q = partition (array, p, r)
        quicksort (array, p, q-1)
        quicksort (array, q+1, r)

Answer 1

Es klingt wie Ihre eigentliche Frage ist: „Warum ist die Rekursionstiefe kürzer, wenn Fäden mit“? Ich werde versuchen, diese Frage zu beantworten.

Zuerst Hintergrund. Jede Ebene der Rekursion ist ein Bereich des Speichers, bekannt als Stapel gespeichert. Leider hat das System den Stapelspeicher im Voraus reservieren und sie nicht wissen im Voraus, wie viel Stapelspeicher Ihr Programm benötigen. Deshalb zu viel Rekursion eine „maximale Rekursionstiefe“ Fehler verursacht. Ihr Programm hat all das Stapelspeicherplatz verbraucht

Jeder Thread benötigt seinen eigenen Stapel die Liste der Funktionen zu speichern, die gerade in diesem Thread ausgeführt wird. In einem einzigen Gewinde Programm kann das System leisten einen großen Teil des Speichers zu dem Stapel für diesen einen Faden zu geben. In einem Multi-Threaded-Programm hat das System ein wenig konservativ sein, und es gibt nur einen kleinen Stapel auf jeden Thread. Andernfalls wird ein Programm mit vielen Threads schnell alle Systemspeicher nur mit Stapelspeicher nutzen könnte (von denen die meisten nicht genutzt werden).

All dies wird durch das Betriebssystem und / oder durch die C-Bibliothek durchgeführt, den Python (genauer gesagt, CPython) läuft auf der Oberseite. Python versucht, hart Sie zu verhindern, dass der gesamten C-Stack verwenden, denn das ist ein harten Absturz, anstatt einfach eine Ausnahme verursachen würde. Sie können Python sagen, wie mit der setrecursionlimit Funktion verhalten, aber das ändert nicht die ist Menge Stapelspeicherplatz zur Verfügung.

Auf einem Unix-artiges System mit einem Bash-Shell, können Sie in der Lage sein, die Stack-Größe mit dem ulimit -s Befehl zu ändern. Typ help ulimit an Ihrem Bash-Shell-Eingabeaufforderung für weitere Informationen.

Answer 2

• Sie verwenden eine rekursive Implementierung von Quicksort. Sie wollen Iteration statt implementieren quicksort verwenden.

  Rekursion ist nicht skalierbar in Python (in CPython zumindest), so dass für größeren Eingang wird es scheitern. Sie können die Rekursion Grenze erhöhen, aber das wird man nur einen größeren Bereich skalieren lassen, nicht die Implementierung wirklich skalieren lassen. Es kommt auch auf Kosten der damit die Möglichkeit einer segfault wenn Sie zu viel Rekursion haben. Dieser Ansatz funktioniert (oder tut eher nicht wirklich Arbeit) als auch für Multi-Thread-Code, Sie müssen es nur mehr tun, weil die Rekursion Grenze für jeden Thread niedriger sein wird. Alles in allem ist es ein Verlustgeschäft. Verwendung Iteration statt

• Sie verwenden Threads (oder Planung), die in der Regel ist ein schlechtes Zeichen. Themen sind verwirrend und gefährlich und hart. Was mehr ist, Threads in Python nicht gibt Ihnen die parallele Ausführung, wenn das, was Sie erwartet haben. Mit Gewinde für eine quicksort Umsetzung, vor allem in Python, wird sich wahrscheinlich weniger als ideal. (Wenn Sie verpflichtet sind, es zu tun, sollten Sie zumindest Schritt zurück und verstehen, dass es nicht der beste Ansatz sein könnte.)

Answer 3

Warum schreiben Sie Ihre eigene quicksort Routine? Ist das Hausaufgaben?

Wenn nicht, würde ich den eingebauten empfehlen die Verwendung von Mechanismen bei der Sortierung; sie sind recht gut für die überwiegende Mehrheit der Fälle, und leiden nicht unter einem Problem Rekursionstiefe. Wenn Sie bei extrem großen Datenmengen suchen, würde ich auf den verschiedenen Containern und Algorithmen vorschlägt, Blick verfügbar von scipy und numpy.

Wenn es rein aus Neugier ist die Routine der Umsetzung, als Marcelo in den Kommentaren schon sagt, wir müssen den Code sehen.

Answer 4

Das Problem, das Sie haben, ist eine rekursive Funktion nutzt den Hauptspeicher und mit einer großen Anzahl von Elementen und somit eine große Anzahl von Rekursion, Sie laufen von Speicher aus. Dies erklärt, warum Ihr Programm Erhöhung der Rekursion Grenze stürzt -. Sie mehr Speicher sind gefragt, als Sie haben

Wenn Sie wirklich für eine große Anzahl von Elementen implementieren quicksort wollen, sollten Sie lesen diese Artikel auf Wikipedia auf Speichernutzung speziell mit quicksort. Sonst wie Nathan vorgeschlagen, hat Python bereits in sorted() Funktion eingebaut. Es sei denn, diese Hausaufgaben oder Neugier ist, würde ich sehr empfehlen, dass mit.

Answer 5

Hier ist der Iterative Code für QuickSort

    import time
    import random

    stack = []

    def partition(data,p,q):
        global stack
        pivot = p
        pivotvalue = data[q]
        for index in range(p,q+1):
            if data[index] < pivotvalue:
                temp = data[index]
                data[index] = data[pivot]
                data[pivot] = temp
                pivot = pivot + 1
        temp = data[q]
        data[q] = data[pivot]
        data[pivot] = temp
        return pivot

    def qSort(data,p,q):
        global stack
        push(stack,p,q)
        while isEmpty(stack) == False:
            q = pop(stack)
            p = pop(stack)
            pivot = partition(data,p,q)
            if pivot-1 > p:
                push(stack,p,pivot-1)
            if pivot+1 < q:
                push(stack,pivot+1,q)


    def push(stack,p,q):
        stack.append(p)
        stack.append(q)

    def pop(stack):
        global top
        if(len(stack)==0):
            return -1
        element = stack.pop()
        return element

    def isEmpty(stack):
        return len(stack) == 0

    if __name__ == '__main__':
        start_time = time.time()
        data = (range(1000000,0,-1))
        random.shuffle(data)
        #print data
        qSort(data,0,len(data)-1)
        #print data
        print time.time() - start_time, "seconds"