Entwicklung & Code
Programmiersprache Python: Performante Algorithmen entwickeln und optimieren
Plant man eine Reise durch mehrere Städte und will die kürzeste Route finden, greift man auf Algorithmen zurück, eine wohldefinierte Abfolge deterministischer Operationen. Dieser Artikel begleitet den Entwicklungsprozess eines Algorithmus, der kürzeste Wege zwischen Städten findet. Er zeigt Schritt für Schritt den Weg von der ersten Skizze über Tests und Visualisierung mit Matplotlib und NetworkX bis zur Optimierung durch geeignete Datenstrukturen. So entsteht ein Programm, das nicht nur funktional korrekt arbeitet, sondern auch performant ist.
Weiterlesen nach der Anzeige
Michael Inden ist Java- und Python-Enthusiast mit über zwanzig Jahren Berufserfahrung. Derzeit ist er als Head of Development tätig, spricht auf Konferenzen und schreibt Fachbücher über Java und Python.
Ziel ist, in einem Straßennetz diejenigen Wege zu finden, die Städte am kürzesten verbinden. Zur Modellierung kann man Graphen verwenden. In Abbildung 1 repräsentieren Kreise mit Beschriftung die Städte und die Verbindungslinien mit Zahlen entsprechen Wegen mit Distanzen.
Ein Graph visualisiert die Abstände von Städten; die Zahlen stehen für die Entfernungen (Abb. 1).
Für diese vereinfachte Karte soll der kürzeste Weg von A nach D gefunden werden. Während man bei wenigen Städten und Verbindungen alle Möglichkeiten ausprobieren kann, wird der Ansatz aufwendiger, je mehr Städte und Verbindungen existieren. Folgende Verbindungen sind möglich, wobei 13 die schlechteste ist und 6 die beste:
A -> B -> C -> D => 5 + 1 + 7 = 13
A -> C -> B -> D => 2 + 1 + 3 = 6
A -> C -> D => 2 + 7 = 9
A -> B -> D => 5 + 3 = 8
Mit der O-Notation die Effizienz verstehen
Für eine gute Bedienbarkeit von Programmen ist relevant, wie schnell sich Berechnungen und Operationen ausführen lassen. Das gilt vor allem bei großen Datenmengen. Die O-Notation erlaubt es, Algorithmen zu klassifizieren und das Wachstum der Laufzeit (oder des Speicherbedarfs) eines Algorithmus zu beschreiben, wenn die Eingabemenge größer wird. Somit sind Effekte vorhersagbar, etwa wenn eine Liste nicht mehr 10 oder 20, sondern 100.000 und mehr Daten enthält.
Weiterlesen nach der Anzeige
Die O-Notation hilft, die Laufzeit von Operationen einzuschätzen. Sie ordnet Algorithmen und Funktionen in Komplexitätsklassen ein. Bei O(n³) wächst die Anzahl der Schritte mit der dritten Potenz der Eingabemenge. Bei 100 Eingabedaten ergibt sich ein Aufwand von 1003 für die Berechnung, also 1.000.000 Schritte. Je niedriger die Komplexitätsklasse ist, desto besser. Weitere Klassen zeigt die Tabelle „O-Notation mit in Komplexitätsklassen eingeteilten Algorithmen“, Abbildung 2 visualisiert die Effekte.
| O-Notation mit in Komplexitätsklassen eingeteilten Algorithmen | ||
| Notation | Bedeutung, Wachstum | Beispiel |
| O(1) | konstant | Zugriff auf ein Listenelement |
| O(log n) | logarithmisch | Binärsuche |
| O(n) | linear | einfache Schleife über alle Elemente |
| O(n log n) | linear-logarithmisch | effiziente Sortieralgorithmen (etwa Mergesort) |
| O(n²) | quadratisch | zweifach verschachtelte Schleife |
| O(n3) | kubisch | dreifach verschachtelte Schleife |
Die Graphen zeigen die Anzahl der Operationen in Abhängigkeit von der Eingabegröße (Abb. 2).
Eine Klassifikation mit der O-Notation ist insbesondere wichtig, um Laufzeiten unabhängig von Hardwareausstattung, Implementierungsdetails und gewählten Programmiersprachen bezüglich ihrer Skalierungseigenschaften zu vergleichen.
Für eine vereinfachte Einschätzung betrachtet man bei der Bewertung nur den dominierenden Term, da bei großen Eingabegrößen kleine Konstanten oder niedrigere Terme und Faktoren vernachlässigbar sind. In der Formel n3 + 4n² + 3n + 7 folgt durch die Vereinfachungen die Laufzeitklasse O(n3).
Von der Idee zum Programm
Ein systematisches Vorgehen ist selbst für kleinere Programme und vor allem bei komplexen Softwareprojekten der Schlüssel zu funktionalem, wartbarem und performantem Code.
1. Problem verstehen und analysieren
- klären, welches Problem zu lösen ist, und es in Teilaufgaben zerlegen;
- prüfen, ob es bereits bewährte Lösungen für Teilaufgaben gibt, beispielsweise Binärsuche für performante Suchen in sortierten Datenbeständen, Dijkstra-Algorithmus für kürzeste Wege;
- Eingabe- und Ausgabedaten definieren;
- Randbedingungen und Sonderfälle berücksichtigen.
2. Planen und eine Grobstruktur entwickeln
- Problem in Teilaufgaben zerlegen;
- Abläufe in natürlicher Sprache formulieren oder skizzieren;
- geeignete Datenstrukturen wählen (Listen, Dictionaries, Heaps).
3. Implementierung
- Sourcecode in klar getrennte Funktionen oder Klassen gliedern;
- auf Lesbarkeit und Verständlichkeit achten, aussagekräftige Namen und (falls sinnvoll) ergänzende Kommentare verwenden;
- vorhandene Bibliotheken nutzen, um Entwicklungszeit zu sparen (etwa Matplotlib zur Visualisierung).
4. Testen (Dry-Run- und Unit-Tests)
- Funktionsweise ausprobieren;
- Unit-Tests schreiben, um die Funktionsweise zu prüfen und Rand- und Sonderfälle abzudecken.
5. Performance messen
- Messungen mit kleinen, mittleren und großen Datenbeständen ausführen, etwa mit 100, 10.000 und 1.000.000 Datensätzen;
- Engpässe identifizieren – sie zeigen sich allerdings meist erst bei sehr großen Datenbeständen.
6. Optimieren
Wurden in Schritt 5 Schwachstellen aufgedeckt, sollte man die Umsetzung und die gewählten Algorithmen für Teilprobleme nochmals genauer anschauen.
- O-Notation verwenden, um die Komplexität formal zu bewerten: Was läuft in Schleifen? Wie und wo erfolgt eine Suche – linear oder mit Binärsuche? Für verschiedene Aktionen kann das Laufzeiten von O(1)
, O(log n) oder O(n)bedeuten. - besser geeignete Algorithmen oder effizientere Datenstrukturen einsetzen.
Implementierung und Test miteinander verweben
In der Praxis laufen die Schritte 3 und 4 nicht immer unabhängig voneinander. Wenn sich die Ergebnisse gut vorhersagen lassen, bietet es sich an, mit dem Erstellen von Testfällen zu starten. Manchmal braucht es aber erst einmal eine Idee und einen Prototyp der Implementierung. Gerade bei größeren Programmierprojekten ergeben sich weitere Anforderungen während der Implementierungs- und Testphase.
Der folgende Ablauf hat sich in der Praxis bewährt und lässt sich auch beim Entwickeln eines Algorithmus anwenden.