Programmiersprache Python: Performante Algorithmen entwickeln und optimieren
Um die kürzeste Strecke zwischen Städten zu ermitteln, greift man auf einen Algorithmus zurück. Arbeitet er nicht effizient genug, lässt er sich optimieren.
(Bild: heise medien)
- Michael Inden
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.
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.
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 = 8Mit 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.
Videos by heise
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 |
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.
