Komischer Error

[Hard_Veur]

Ich sollte einen Sortiralgo in Python implementieren mit O(n*log n) und O(n^2).
Jetzt wollte ich Quicksort nehmen, weil ich finde er sei einiger Maßen einfach zu programmieren.

Mein Problem ist nun ich habe eine Liste zufällig während der Laufzeit erzeugt. Dies tat ich mit bis zu 1.000.000 zufälligen Elementen.
Als ich jedoch nun die Test Daten meines Prof nehmen wollte mit nur 339446 Einträgen kam es auf einmal zu einem rekursions Error da die rekursions tiefe erreicht wurde.

Mein meine Zufallsfunktion zur Erzeugung der Liste.

Code: Alles auswählen

def test_liste_erzeugen(leange_list):

	sequenz = []

	for rand in range(leange_list):
		rand = random.randint(1, 100000)
		sequenz.append(rand)
	
	return sequenz

Und der Quicksort Algo:

Code: Alles auswählen

def quicksort(L, anfang=0, ende=None):
              
    if ende == None:
        ende = len(L) - 1
              
              
    if len(L) > 1:
        pivot = L[anfang]
        links = anfang
        rechts = ende
        while links <= rechts:
            while L[links] < pivot:
                links = links+1
            while L[rechts] > pivot:
                rechts = rechts-1
            if links <= rechts:
                if links < rechts:
                    h = L[links]
                    L[links] = L[rechts]
                    L[rechts] = h
                links = links+1
                rechts = rechts-1
                if rechts < anfang:
                    rechts = anfang
        if anfang < rechts:            
            L = quicksort(L, anfang, rechts)
        if links < ende:
            L = quicksort(L, links, ende)
            
    return L

Als ich die Daten nicht während der Laufzeit in die Liste schrieb habe ich sie mit copy and paste in L=[1,2,4.....] (Liste mit den wie gesagt 339446 Elementen) eingefügt, falls das hilft!?

Also wie kann es zu so etwa kommen bei weniger Elementen?

Danke schon mal für eure Antworten

[__deets__]

Ist alles einen Weile her, aber Quicksort kann ja im schlimmsten Fall quadratisch werden, wenn du das Pivot ungluecklich waehlst bzw zB vorsortierte Listen einfuetterst. Und dann wird AFAIK die Rekursion so tief, wie die Liste lang ist. Und ein Stack mit ~.3 Millionen Frames ist schon etwas viel des guten...

Das ist natuerlich auch unberuehrt davon, dass dein Code ggf. Fehler hat, das habe ich jetzt nicht geprueft.

[noisefloor]

Hallo,

@Hard_Veur: mit Rekursion in Python arbeiten ist in der Regel keine gute Idee, weil zumindest CPython keine Optimierung bei der Rekursion vornimmt und auch das Default Rekursionlimit auf 1000 gesetzt ist.

Und wie __deets__schon sagt können bei Quicksort im allerschlechtesten Fall n^2 Rekursionen nötig sein, also bei "nur" 339.446 Werten wärst du da bei 115.223.586.916 Rekursionen.

Müsst ihr das in Python rekursiv lösen oder war Rekursion deine Wahl?

Gruß, noisefloor

[Hard_Veur]

Rekursion war meine Wahl

[BlackJack]

@Hard_Veur: Dann wirst Du jetzt also entweder einen anderen Algorithmus finden müssen, oder den Quicksort ohne rekursiven Aufruf implementieren müssen. Das Rekursionslimit höher setzen mag verlockend klingen, aber dann ist nicht mehr garantiert, dass das Programm bei zu hoher Tiefe nicht einfach mit einem Speicherzugriffsfehler hart abstürzt, weil der Speicher für den Aufrufstapel begrenzt ist.

Anmerkungen zum Quelltext:

Das Erzeugen der Testliste ist ziemlich ”geschwätzig” implementiert. Die Schleifenvariable wird nicht verwendet, hat aber einen Namen der *in* der Schleife dann doch — für etwas anderes — verwendet wird. Das ist verwirrend. Bei Namen die zwar aus syntaktischen Gründen da sein müssen, aber nicht verwendet werden, hat sich der Name `_` eingebürgert.

`rand` braucht man aber auch nicht wirklich. Es macht das Programm nicht wirklich verständlicher wenn man das Zwischenergebnis an einen Namen bindet.

Letztlich kann man die Funktion aber auch sehr kompakt mit einer „list comprehension“ formulieren:

Code: Alles auswählen

def testliste_erzeugen(laenge):
    return [random.randint(1, 100000) for _ in range(laenge)]

Bei dem sortieren macht die Rückgabe von `L` keinen Sinn. Entweder eine Funktion (dann oft auch Prozedur genannt) verändert eine Datenstruktur, oder sie gibt ein Ergebnis zurück. Aber die Struktur die sortiert wurde, zusätzlich noch als Ergebnis zurück zu geben, macht keinen Sinn. Der Aufrufer hat den Wert ja bereits.

Es gibt die ``+=`` und ``-=`` Operatoren.

Zwei Werte tauschen geht in Python auch ohne Namen für einen temporären Zwischenwert:

Code: Alles auswählen

h = a
a = b
b = h

# <=>

a, b = b, a

Ich lande dann als Zwischenstand ungefähr hier (ungetestet):

Code: Alles auswählen

def quicksort(items, anfang=0, ende=None):
             
    if ende is None:
        ende = len(items) - 1
             
    if len(items) > 1:
        pivot = items[anfang]
        links = anfang
        rechts = ende
        while links <= rechts:
            while items[links] < pivot:
                links += 1
            while items[rechts] > pivot:
                rechts -= 1
            if links <= rechts:
                if links < rechts:
                    items[links], items[rechts] = items[rechts], items[links]
                links += 1
                rechts -= 1
                if rechts < anfang:
                    rechts = anfang
        if anfang < rechts:            
            quicksort(items, anfang, rechts)
        if links < ende:
            quicksort(items, links, ende)

Da `items` sich bei den rekursiven Aufrufen immer das selbe Objekt ist, würde ich hier eine lokale Funktion für die Rekursion schreiben, die auf `items` aus dem umgebenden Namensraum zugreifen kann. Das kann auch hilfreich sein wenn man das ohne rekursiven Aufruf umschreiben will, denn diese innere Funktion muss man dann durch eine Schleife und eine Liste als expliziten Stapelspeicher ersetzen.

[Hard_Veur]

Viel dank für eure Antworten und sehr hilfreichen Tipps mit denen mein Code hoffentlich bald besser aussieht
Eine Frage hätte ich noch. Du meinst also ich sollte die liste als globale Variable definiere oder verstehe ich das jetzt falsch?
Programmiere sonst nicht so viel mit Python tut mir leid wenn meine Frage jetzt unsinnig ist.

[BlackJack]

@Hard_Veur: Nein, nicht als globale Variable, sondern so wie jetzt lokal zu der Sortierfunktion, aber eben nicht als Argument für die innere, lokale, rekursive Funktion in die ich das sortieren selbst verschieben würde. Die kann dann trotzdem auf die Liste zugreifen. Das Stichwort hier ist Closure.

[BlackJack]

Um es mal konkret zu machen:

Code: Alles auswählen

def quicksort(items):
    
    def recurse(anfang, ende):
        if len(items) > 1:
            pivot = items[anfang]
            links, rechts = anfang, ende
            while links <= rechts:
                while items[links] < pivot:
                    links += 1
                while items[rechts] > pivot:
                    rechts -= 1
                if links <= rechts:
                    if links < rechts:
                        items[links], items[rechts] = items[rechts], items[links]
                    links += 1
                    rechts -= 1
                    if rechts < anfang:
                        rechts = anfang
            if anfang < rechts:            
                recurse(anfang, rechts)
            if links < ende:
                recurse(links, ende)

    recurse(0, len(items) - 1)

Und hier kann man jetzt relativ leicht die Rekursion durch einen Stapel und eine Schleife ersetzen. Für einen Stapel bieten Listen die erforderlichen Operationen.

[Hard_Veur]

Was du meinst habe ich glaube erstmal ganz gut verstanden. Danke

Jedoch müsste man items nicht noch als nonlocal defienieren?

[BlackJack]

@Hard_Veur: Nein, das funktioniert so. Wieso sollte man da ``nonlocal`` brauchen? (Hätte mir hier unter Python 2 auch gar nicht zur Verfügung gestanden. )

[BlackJack]

Mit einem expliziten Stapel und ohne rekursiven Aufruf:

Code: Alles auswählen

def quicksort(items):
    stack = [(0, len(items) - 1)]
    while stack:
        anfang, ende = stack.pop()
        if len(items) > 1:
            pivot = items[anfang]
            links, rechts = anfang, ende
            while links <= rechts:
                while items[links] < pivot:
                    links += 1
                while items[rechts] > pivot:
                    rechts -= 1
                if links <= rechts:
                    if links < rechts:
                        items[links], items[rechts] = items[rechts], items[links]
                    links += 1
                    rechts -= 1
                    if rechts < anfang:
                        rechts = anfang
            if anfang < rechts:            
                stack.append((anfang, rechts))
            if links < ende:
                stack.append((links, ende))