Systematische Bestimmung des Laufzeitverhaltens

Laufzeitmessungen

Ziel der folgenden Untersuchungen ist es, das Laufzeitverhalten von Sortieralgorithmen systematisch zu ermitteln und die Ergebnisse genauer zu analysieren.

Hierzu bestimmen wir die Laufzeit t(n) in Abhängigkeit der Listenlänge n für wachsende Listenlängen (z.B. n = 1000, 2000, ...).

Die zu sortierenden Listen werden mit Zufallszahlen gefüllt. Bei der Erzeugung der Testlisten wird der Zahlenbereich, aus dem die Zufallszahlen stammen, an die Listengröße angepasst, um ähnliche Ausgangssituationen zu erhalten.

Hier ein Python-Programm, mit dem man auf diese Weise systematisch Laufzeiten bestimmen kann. Es fehlt nur noch eine Implementierung des Selectionsort-Algorithmus.

from time import *
from random import randint
# Sortieralgorithmus
...
# Initialisierung der Anzahl der Listenelemente
anzahl = 1000
while anzahl < 10000:
    # Erzeugung der Liste
    L = []
    for i in range(anzahl):
        L = L + [randint(1, 10*anzahl)]
    # Bestimmung der Rechenzeit beim Sortieren
    t1 = process_time()
    L_sortiert = selectionsort(L)
    t2 = process_time()
    t = t2 - t1
    # Ausgabe des Messergebnisses
    print("Anzahl der Listenelemente: ", anzahl, "Rechenzeit: ", t)
    # Erhoehung der Anzahl der Listenelemente
    anzahl = anzahl + 1000

Aufgabe 1: Sortieren durch Auswählen

(a) Ergänze das Programm und bestimme die Laufzeit t(n) in Abhängigkeit der Listenlänge n (hier für n = 1000, 2000, ...).

(b) Du wirst Ergebnisse erhalten, die vom Prinzip her so aussehen:

>>> 
Anzahl der Listenelemente:  1000 Rechenzeit:  0.208472864568
Anzahl der Listenelemente:  2000 Rechenzeit:  0.82472800314
Anzahl der Listenelemente:  3000 Rechenzeit:  1.83589394742
Anzahl der Listenelemente:  4000 Rechenzeit:  3.3119754047
Anzahl der Listenelemente:  5000 Rechenzeit:  5.27956234661
Anzahl der Listenelemente:  6000 Rechenzeit:  7.45063213341
Anzahl der Listenelemente:  7000 Rechenzeit:  9.99217191012
Anzahl der Listenelemente:  8000 Rechenzeit:  13.1027999369
Anzahl der Listenelemente:  9000 Rechenzeit:  16.5563961341

Kannst du eine Vorhersage treffen, wie lange es dauert, wenn man die Rechenzeit analog für 10000 Listenelemente bestimmt? Versuche hierzu, anhand der Messwerte Gesetzmäßigkeiten aufzudecken: Wie ändert sich t(n), wenn man n verdoppelt? Überprüfe deine Vorhersage.
Klicke für eine Hilfe!

Aufgabe 2: Sortieren durch Einfügen

Bestimme analog Laufzeiten bei einer Implementierung zum Insertionsort-Algorithmus (Sortieren durch Einfügen). Analysiere auch hier die Messergebnisse.

Wenn du selbst keine Implementierung des Insertionsort-Algorithmus hast, dann kannst du auch diese benutzen:

def insertionsort(L):
    n = len(L)
    i = 1
    while i < n:
        z = L[i]
        j = i
        while (j > 0) and (L[j-1] > z):
            L[j] = L[j-1]
            j = j-1
        L[j] = z
        i = i+1
    return L

Aufgabe 3: Sortieren durch Aufsteigen

Bestimme analog Laufzeiten bei einer Implementierung zum Bubblesort-Algorithmus (Sortieren durch Aufsteigen). Analysiere auch hier die Messergebnisse.

Wenn du selbst keine Implementierung des Bubblesort-Algorithmus hast, dann kannst du auch diese benutzen:

def bubblesort(L):
    ende = len(L)
    while ende > 0:
        for i in range(0, ende-1):
            # Vergleichen
            if L[i+1] < L[i]:
                # Aufsteigen
                h = L[i]
                L[i] = L[i+1]
                L[i+1] = h
        ende = ende - 1
    return L

Aufgabe 4: Sortieren durch Zerlegen

(a) Bestimme analog Laufzeiten bei Implementierungen zum Quicksort-Algorithmus (Sortieren durch Zerlegen). Benutze deine eigenen und auch die folgenden Implementierungen:

Implementierung 1: mit Erzeugung neuer Listen

def quicksort(L):
    if L != []:
        pivot = L[0]
        kleinerPivot = []
        groessergleichPivot = []
        for e in L[1:]:
            if e < pivot:
                kleinerPivot = kleinerPivot + [e]
            else:
                groessergleichPivot = groessergleichPivot + [e]
        kleinergPivotSortiert = quicksort(kleinerPivot)
        groessergleichPivotSortiert = quicksort(groessergleichPivot)
        LSortiert = kleinergPivotSortiert + [pivot] + groessergleichPivotSortiert
    else:
        LSortiert = []
    return LSortiert

Implementierung 2: mit Vertauschungen auf der Ausgangsliste

def quicksort(L, anfang, ende):
    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 anfang < rechts:
        L = quicksort(L, anfang, rechts)
    if links < ende:
        L = quicksort(L, links, ende)
    return L

(b) Laufzeiten können wesentlich von der gewählten Implementierungsvariante abhängen. Wenn du die beiden oben gezeigten Implementierungen von Quicksort getestet hast, dann ist dir sicher aufgefallen, dass die Version mit den Hilfslisten bei langen Listen viel mehr Rechenzeit benötigt. Woran liegt das? Das folgende Testprogramm liefert einen Erklärungsansatz:

from time import *

anzahl = 60000
print(anzahl)
# 
print("Start")
t1 = process_time()
# 
L = []
for i in range(anzahl):
    L = L + [anzahl]
# 
t2 = process_time()
t = t2 - t1
print("Stopp")
print("Rechenzeit: ", t)

Führe das Testprogramm mit unterschiedlichen Listengrößen aus. Welches Verhalten erwartest du, wenn du die Listenlänge verdoppelst? Welches Verhalten tritt hier tatsächlich ein? Woran könnte das liegen?