Datenstrukturen: Ein zweiter Blick - Einführung in Python

Laufzeitkomplexität¶

Listen¶

Intern ist eine list ein dynamisches Array, bei dem also im Hintergrund Puffer-Speicher reserviert ist, sodass das Hinzufügen eines Elements am Ende in $O(1)$ liegt. Wenn der Puffer voll ist, muss zwar in $O(n)$ neuer Speicher reserviert werden, das passiert aber nur exponentiell selten und damit ist die amortisierte Laufzeit von list.append in $O(1)$ .

Für das hinzufügen am Anfang der Liste mit list.insert sind $O(n)$ Operationen erforderlich, ebenso für list.pop, das Entfernen (und Zurückgeben) des ersten Elements. Eine Datenstruktur, die schnelles Hinzufügen und Entfernen ann beiden Enden bietet, ist collections.deque (deque = double-ended queue).

Listen lassen sich sortieren mit list.sort() (in-place) sowie list.sorted() (gibt die sortierte Liste als neue Liste zurück ohne die Originalliste zu ändern). Beide Funktionen verwenden (wie auch Java) Timsort, was im average case in $O(n\log n)$ läuft und für fast sortierte Daten nahe an $O(n)$ kommt.

Eine häufige Performance-Falle ist die Mitgliedschaftsprüfung: element in my_list ist im worst case in $O(n)$ . Wenn man z.B. über my_list iteriert und dabei in jeder Iteration eine Mitgliedschaftsprüfung durchführt, liegt man schon bei $O(n^2)$ . Das lässt sich vermeiden, wenn man vor der Schleife my_set = set(my_list) ausführt und mit einer Menge arbeitet.

Mengen¶

Intern sind Mengen Hash-Tabellen. Python verwendet die Methode hash, ein Aufruf von hash(x) führt zu x.__hash__(), wenn das implementiert ist (und prüft, dass dabei ein Integer zurück gegeben wird). Das Einfügen in eine Hash-Tabelle geschieht in $O(1)$ . Die Suche (x in my_set) kann im worst case in $O(n)$ liegen, wenn alle Elemente den gleichen Hash haben. Das ist zumindest bei der Python-internen Hashfunktion aber unwahrscheinlich: numerische Werte sind im Wesentlichen ihr eigener Hash, Tupel werden aus den Elementen kombiniert und für Strings verwendet Python SipHash-1-3. Im Durschnitt liegt daher auch die Suche nach einem Element (und das Löschen eines Elements) in $O(1)$ .

Dictionaries:¶

Auch Dictionaries sind als Hash-Tabellen implementiert. Die Schlüssel bilden eine Menge, daher müssen diese alle hashable sein. Das bedeutet insbesondere in der Regel, dass sie immutable sein müssen. Daher kommen Variablen vom Typ list nicht als Schlüssel in Frage, hingegen tuple schon.

Damit sind alle Hauptoperationen auf einem Dictionary in $O(1)$ :

my_dict[key] = value
value = my_dict[key]
if key in my_dict:
    del my_dict[key]

Wenn man ein Schlüssel-Wert-Paar mit del entfernt, bekommt man im Gegensatz zu my_dict.pop(key) nicht den Wert zurück - was minimal effizienter sein kann.

Seit Python 3.7 hat das dict eine besondere Implementierungseigenschaft: die Einfügereihenfolge ist garantiert. Das ist ein Nebeneffekt einer cleveren resourcenschonenden Implementierung: intern wird das dict mit zwei Arrays repräsentiert: die Hashtabelle indices, wo zu jeden Hash ein Index abgelegt ist und der Array entries, der zu jedem Index ein (hash, key, value)-Tupel speichert. Neue Einträge landen einfach am Ende vom entries-Array. Somit lässt sich über das Dictionary iterieren, indem man einfach über das entries-Array iteriert.

Strings¶

Da Strings immutable sind, wird bei jeder scheinbaren Veränderung ein neuer String angelegt. Das kann mitunter zu einem Performanceproblem werden, wenn man etwa Strings in einer Schleife zusammensetzt. Es gibt für die typische Aufgabe, aus einer Liste (oder allgemeiner einem Iterable) einen String zusammenzusetzen die Methode string.join in $O(n)$ , etwa so:

meine_liste = ["a", "b", "c"]
bridge = " | "
print(bridge.join(meine_liste))
# Output: a | b | c

Das Pendant beim Zerlegen ist string.split, etwa so:

meine_liste = "a, b, c".split(", ")
print(">>".join(meine_liste))
# Output: a>>b>>c

Um schnell Strings zusammenzusetzen, sollte man auf + und insb. += verzichten und voll auf join und f-Strings setzen (die wir noch besprechen werden). Die alte Methode, um Strings mit % zu formatieren, sollte man aus Performancegründen nicht mehr verwenden.

Slicing¶

Eine Liste meine_liste mit 100 Einträgen, also len(meine_liste) == 100 lässt sich über Slicing eine Teilliste abringen, etwa zweite_liste = meine_liste[10:30]. Dabei wird eine Kopie der Daten erstellt, somit ist die Laufzeitkomplexität dieser Operaton in $O(k)$ wobei $k$ die Länge der Liste ist, hier ist also $k=20$ , denn len(zweite_liste) == 20.

Um z.B. in einer Schleife über eine Liste zu iterieren und dabei jeweils zwei benachbarte Einträge zu behandeln, könnte man naiv so implementieren:

meine_liste = ["a", "b", "b", "c"]
for i in range(len(meine_liste) - 1):
    a, b = meine_liste[i:i+2]
    if(a == b):
        print(i, a)

# Output: 1 b

Eleganter wäre aber z.B. eine Doppelliste mit zip anzulegen:

for i, (a, b) in enumerate(zip(meine_liste, meine_liste[1:])):
    if(a == b):
        print(i, a)

# Output: 1 b

Um das Problem zu umgehen, dass hierbei mit meine_liste[1:] eine Kopie der Liste im Speicher angelegt wird, kann man seit Python 3.10 auch direkt itertools.pairwise benutzen:

from itertools import pairwise
for a, b in pairwise(meine_liste):
    if a == b:
        print(a)

# Output: b

Billig und teuer¶

Einen Wert an einen Namen zu binden und das Erstellen von kleinen ganzen Zahlen ist billig, da beim Start von Python vorab Singletons im Speicher angelegt werden und x = 10 kein neues Objekt erstellt sondern nur eine Referenz auf das existierende Objekt 10 holt. Der Aufruf eingebauter C-Funktionen wie len oder join ist extrem schnell. Hingegen der Aufruf einer selbst geschriebenen Methode oder Abruf einer Variablen, die nicht im lokalen Scope liegt, ist vergleichsweise teuer. Ebenso wird beim Aufruf eines Operators wie + eine interne Methode __add__ aufgerufen, was also mit den Kosten eines Methodenaufrufs (dynamischer Dispatch) einhergeht. Man könnte in Python theoretisch mitten in einer Schleifeniteration umdefinieren, wie die Elemente addiert werden.

Grundsätzlich ist es aber ein gesundes Mindset, über Performance erst nachzudenken, wenn man Bottlenecks identifiziert hat - also die Stellen im Programm, die lange dauern bzw. von der Menge an Eingabedaten abhängig länger rechnen. Mit zunehmender Erfahrung im Programmieren (nicht notwendig in Python) kommt dann auch eine innere Einstellung bei der Performance durchaus von Anfang an mitgedacht wird, aber auch dann strategisch nur an den Stellen Zeit und Gehirnschmalz investiert wird, wo es sich lohnen könnte. Wir werden in einer späteren Unterrichtseinheit noch lernen, wie man mit Python systematisch nach Performance-Bottlenecks suchen kann, etwa mit Hilfe eines Profilers.

Typensystem¶

Type Hints¶

Man kann in Python optional Typen deklarieren:

ein_name: str = "Nutzername"
eine_id: int = 42
def hallo(name: str) -> str:
    return "Hallo " + name

print(hallo(ein_name))
# Output: Hallo Nutzername

Der Interpreter ignoriert die Information : str bzw. -> str einfach. Es ist auch möglich, den Code hallo(eine_id) auszuführen, was zu einem TypeError führt, weil man str und int nicht direkt addieren kann ohne explizites Typecasting. Die Type Hints dienen dazu, dass ein externes Analysewerkzeug den Code hallo(eine_id) markieren kann als nicht-typesafe. Dadurch lässt sich eine Klasse von Fehlern bereits zur Kompilierzeit abfangen. Abgesehen davon sind Typeninformationen für menschliche Programmierer (und auch LLM Kopiloten) sinnvoll, um schnell erfassen zu können, was ein Stück Code leisten soll.

Die wichtigste Information zu Typendeklarationen in Python ist, dass der Interpreter diese Typendeklarationen nicht verwendet. Somit lassen sie sich beim Lesen von Code ebenfalls übergehen (wenn etwa die Typenannotationen komplexer sind als der eigentliche Code).

Sammlungen¶

Um eine Sammlung von Objekten gleichen Typs zu beschreiben, schreibt man direkt:

meine_liste_von_strings : list[str]
meine_map_von_int_auf_int: dict[int, int]
meine_menge_von_strings: set[str]

None, Any, Union¶

Da None vom NoneType ist, ergibt es keinen Sinn diesen Wert in eine Variable zu füllen, die z.B. als int markiert ist. In Sprachen wie Haskell gibt es die Maybe-Monade, sodass Maybe(int) der Datentyp ist, der entweder int oder None ist (in Java ist es Optional[int], in anderen Sprachen int?). In Python wird das seit Python 3.10 über Union-Types gelöst:

x : int | None = None
x = 42

Mit typing.Any als Typ wird einem Typechecker signalisiert, dass hier keine Typenprüfung stattfinden soll.

Mypy¶

Ein separates Programm, welches Type Hints liest und auswertet ist mypy. Damit werden eine Reihe von Fehlerquellen mit statischer Analyse (also ohne das Programm laufen zu lassen) gefunden:

Typen-Konflikte (z.B. int übergeben, str erwartet)
Methodensignatur passt nicht (z.B. Anzahl Parameter)
Unerwarteter None-Zugriff
Nicht-None-Rückgabewerte (return)

Man kann mit pip install mypy direkt Mypy installieren und auf der Kommandozeile ausführen, aber die meisten IDEs integrieren es direkt (etwa über ein Plugin).

Man kann Code mit und ohne Type Hints mischen, und so z.B. für eine Kernlogik korrekte Type Hints verwenden (und von Mypy profitieren), aber für experimentellen Wegwerfcode keine Type Hints schreiben (und so erstmal schneller Code generieren).

Assertions¶

Wenn man sich mit Hilfe von Mypy zur Erstellung klar macht, dass eine bestimmte Variable zur Laufzeit stets einen String (und nicht None) enthält, kann man auf eine Prüfung is not None verzichten. Anstelle einer Prüfung (also einer Verzweigung im Kontrollfluss) lässt sich die Annahme/Aussage auch mit Hilfe einer Assertion im Code ausdrücken:

assert x

Dieser Code wertet x zu einem Boolean aus; wenn es False ist, wirft diese Zeile eine AssertionError. Der Interpreter kann so instrumentiert werden, dass die assert-Zeilen nicht mit ausgeführt werden (etwa um das Programm zu beschleunigen):

python -O script.py

Man sollte solche AssertionError nicht zur Verwaltung des Kontrollflusses verwenden, sondern assert wirklich nur für Aussagen einsetzen, bei denen zu jedem Programmzustand erwartet wird dass sie True sind. Ungültige Programmzustände (etwa durch verletzte Annahmen an Nutzereingaben oder Verhalten anderer Systeme) sollten zuvor ausgeschlossen werden. Es bleibt dann natürlich, dass zur Laufzeit ein AssertionError darauf hinweist, dass der/die Programmierer einen Denkfehler gemacht hat bei der Modellierung der möglichen Programmzustände.

Exceptions¶

Wir haben zuvor bereits über die Kontrollfluss-Aspekte von Exceptions mit try..except kurz gesprochen. Exceptions sind, wie alles in Python, Objekte; Genauer sind alle Exception-Klassen Unterklassen von BaseException. Wenn man eine neue Art von Exception einführt, dann stets als Unterklasse von Exception.

Wenn man z.B. versucht 7 / 0 auszuwerten, wird eine ZeroDivisionError geworfen (die sich mit try..except auffangen lässt). Um zu sehen, was für eine Art von Objekt ein ZeroDivisionError ist, können wir z.B. die method resolution order (mro) betrachten:

x = ZeroDivisionError
print(type(x), x.__mro__)
# Output: <class 'type'> (<class 'ZeroDivisionError'>, <class 'ArithmeticError'>, <class 'Exception'>, <class 'BaseException'>, <class 'object'>)

Wir sehen, x.__mro__ ist ein Tupel, welches (angeordnet) die Superklassen von x enthält. Wir sehen hier, jeder ZeroDivisionError ist ein ArithmeticError:

assert issubclass(ZeroDivisionError, ArithmeticError)

Wenn wir eine Instanz vom Fehler haben, sehen wir das auch:

msg = ""
try:
    x = 7 / 0
except ArithmeticError as e:
    if isinstance(e, ZeroDivisionError):
        msg = "zero"
    else:
        msg = "not zero"

print(msg)
# Output: zero

Die häufigeren Exceptions, die beim Programmieren mit Python durchaus auftreten (und gelegentlich sogar auftreten sollen, damit wir sie mit try..except behandeln) sind:

LookupError, Oberklasse für IndexError, KeyError etwa beim Zugriff auf Dictionaries
AssertionError haben wir eben gesehen
AttributeError wenn man z.B. x.y zugreifen möchte, aber das Objekt x hat gar kein Attribut y
ImportError wenn ein Modul mit import nicht geladen werden kann
KeyboardInterrupt wenn der Nutzer Ctrl+C o.ä. eingibt -- Besonderheit ist, dass diese Exception nicht von Exception erbt sondern von BaseException sodass ein try..except Exception den KeyboardInterrupt nicht auffängt, und das Programm somit abbrechen kann.
NameError wenn ein Bezeichner im Scope nicht gefunden werden kann.
OSError für alle möglichen Fehlerzustände, die das Betriebssystem zurückgibt, insb. wenn Dateien nicht gefunden werden können oder die Festplatte voll ist.
RuntimeError ist die Oberklasse für alle Fehler, die nicht in eine der anderen Kategorien passen. Gelegentlich wird spezieller der NotImplementedError eingesetzt, wenn in Zukunft noch Code geschrieben werden soll: raise NotImplementedError("will do soon")
StopIteration ist ein spezieller Fehler, denn er wird im “Fehlerzustand” geworfen, wenn ein Iterator keine weiteren Items hat. Das ist in der Regel kein echter Fehler sondern ein erwarteter Zustand, daher ist es zumindest für manche ungewohnt, hierfür Exception handling einzusetzen.
TypeError und ValueError: wenn eine Variable von einem anderen Typ erwartet wird, als benötigt, wird ein TypeError geworfen; wenn lediglich der Wert abweicht vom erwarteten Wert (z.B. Zahl negativ, aber positiv erwartet), wird ein ValueError geworfen.

Es gibt noch eine ganze Reihe weiterer Exceptions und die meisten Module definieren ihrerseits wesentlich spezifischere Exceptions.

Es lohnt sich, im Interpreter mit konkreten Instanzen zu spielen, damit man später Fehlerbehandlung auch zum Debugging einsetzen kann. Ein Beispiel für Inspektion bei Fehlerbehandlung:

try:
    x = input("Give me a number: ")
    try:
        y = int(x)
        z = y / 0
    except ValueError as e:
        print(e)
    except ZeroDivisionError as e:
        raise RuntimeError(e)
except Exception as e:
    print("here:", e.args)

Eine gute Übersicht über die Sorte Gedanken, die man sich bei der Fehlerbehandlung wirklich machen muss (unabhängig von Python, aber angewendet auf Python) ist der Ultimate Guide to Error Handling in Python von Miguel Grinberg.