Connect with us

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

Michael Inden

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).

Ein Graph visualisiert die Abstände von Städten; die Zahlen stehen für die Entfernungen (Abb. 1).

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).

Die Graphen zeigen die Anzahl der Operationen in Abhängigkeit von der Eingabegröße (Abb. 2).

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.



Source link

Verwandte Themen:
Weiterlesen

Entwicklung & Code

GitHub-Store 1.6.0: Plattformübergreifender App-Store für Open-Source


Der plattformübergreifende App-Store GitHub-Store ist in Version 1.6.0 erschienen. Die neue Version erweitert die Unterstützung für Linux-Systeme und bringt zahlreiche Funktionsverbesserungen für die Verwaltung von Open-Source-Anwendungen. Das Projekt ist trotz des Namens kein offizielles Microsoft-Produkt.

Weiterlesen nach der Anzeige

Ein Store für GitHub-Projekte

GitHub-Store ist ein freier App-Store, der sich auf Open-Source-Anwendungen konzentriert. Anders als etablierte Stores wie der Google Play Store oder F-Droid nutzt die Anwendung die GitHub Search API und die Releases API, um automatisch Projekte zu finden, die installierbare Binaries bereitstellen. Entwickler müssen ihre Apps nicht manuell einreichen – der Store zeigt automatisch alle GitHub-Repositories an, die in ihren Releases passende Installationsdateien wie APK, EXE oder DMG anbieten.

Das Projekt basiert auf Kotlin Multiplatform und Compose Multiplatform, was eine einheitliche Codebasis für verschiedene Betriebssysteme ermöglicht. Die Anwendung läuft auf Android, Windows, macOS und Linux, wobei sie automatisch die passenden Assets für die jeweilige Plattform erkennt und zum Download anbietet. Installierte Apps lassen sich über den Store auf Updates überwachen.

Neue Features in Version 1.6.0

Nutzer können ab sofort direkt im Store ihre mit GitHub-Sternen markierten Repositories anzeigen lassen, was die Verwaltung favorisierter Projekte vereinfacht. Für Linux-Anwender stehen sowohl AppImage-Dateien als auch Debian-Packages für Debian 12 zur Verfügung.

Entwicklerprofile ermöglichen es, mehr über die Urheber von Projekten zu erfahren. Deep Linking erlaubt das direkte Öffnen bestimmter Apps oder Bereiche im Store über URLs. Die Verwaltung von Releases und installierten Anwendungen wurde ebenfalls überarbeitet.

Weiterlesen nach der Anzeige

Für Nutzer in Regionen mit Netzwerkbeschränkungen bietet Version 1.6.0 eine dynamische Proxy-Unterstützung. Ein verbessertes Caching-System beschleunigt das Laden von Inhalten erheblich. Auch manuelle Installationen von APK-Dateien sind nun möglich, begleitet von nativen Splash-Screens beim App-Start.

Die Benutzeroberfläche haben die Entwickler ebenfalls aktualisiert: Neue „Liquid Glass Chips“ genannte UI-Elemente, überarbeitete Icons und integrierte Übersetzungen sollen die Bedienung verbessern. Die Community trug Übersetzungen in Polnisch, Türkisch, Bengalisch und Hindi bei.

Unter der Haube wurde die Codebasis modularisiert, was zukünftige Erweiterungen und Wartungsarbeiten vereinfachen soll. Die Suchfunktion wurde komplett überarbeitet, diverse Fehler behoben – darunter Probleme bei der Erkennung der APK-Architektur. Auch die Dokumentation und die Security Policy wurden aktualisiert. Detaillierte Informationen zu allen Änderungen finden sich in den offiziellen Release Notes.

Kontroverse um Googles Android-Richtlinien

Die Veröffentlichung erfolgt vor dem Hintergrund einer Kontroverse um Googles geplante Änderungen an Android. In den Release Notes warnt das Projekt: „Freies und Open-Source-Android ist bedroht“. Google plant ab Herbst 2026, auf zertifizierten Android-Geräten eine Registrierungspflicht auch für App-Entwickler einzuführen, die ihre Software außerhalb des Play Store verbreiten wollen.

Gegen diese Pläne richtet sich ein aktueller offener Brief, den Organisationen wie der Chaos Computer Club, die Free Software Foundation, Tuta, Vivaldi und Codeberg unterzeichnet haben. Die Kritik richtet sich gegen die Torwächterrolle Googles, anfallende Gebühren, Ausweispflichten und mögliche Datenschutzrisiken. Auch wenn kein vollständiges Sideloading-Verbot geplant ist, befürchten Kritiker eine Wettbewerbsverzerrung und erhebliche Hürden für unabhängige Entwickler.

GitHub-Store positioniert sich auch vor diesem Hintergrund explizit als Alternative für Nutzer, die ihre Freiheit bei der Software-Installation bewahren möchten. Das Projekt verweist ferner auf die Initiative keepandroidopen.org, die sich für ein offenes Android-Ökosystem einsetzt.


(fo)



Source link

Weiterlesen

Entwicklung & Code

Software Testing: Der perfekte Konferenz-Abstract


In dieser Episode spricht Richard Seidl mit Elmar Jürgens über die Kunst, hochwertige Programme für Softwaretest-Konferenzen wie die Eurostar in Oslo zu gestalten. Die beiden nehmen die Hörer mit hinter die Kulissen: Was unterscheidet die Eurostar von anderen Konferenzen? Wie läuft die Auswahl von Vorträgen ab, und warum reicht KI-generierter Text allein nicht aus?

Weiterlesen nach der Anzeige

Elmar Jürgens erzählt, wie viele Einreichungen geprüft wurden, welche Kriterien für Akzeptanz und Ablehnung eine Rolle spielen und warum Feedback für Speaker so wichtig ist. Das Motto „Testing at its best“ dient als roter Faden und regt dazu an, eigene Erfahrungen auf die Bühne zu bringen.

Dr. Elmar Jürgens hat über statische Codeanalyse promoviert und für seine Doktorarbeit den Software-Engineering-Preis der Ernst-Denert-Stiftung erhalten. Er ist Mitgründer der CQSE GmbH und begleitet seit zehn Jahren Teams bei der Verbesserung ihrer Qualitätssicherungs- und Testprozesse. Elmar Jürgens spricht regelmäßig auf Forschungs- und Industriekonferenzen und wurde für seine Vorträge mehrfach ausgezeichnet. 2015 wurde er zum Junior Fellow der Gesellschaft für Informatik ernannt.

Software Testing im Gespräch

Bei diesem Format dreht sich alles um Softwarequalität: Ob Testautomatisierung, Qualität in agilen Projekten, Testdaten oder Testteams – Richard Seidl und seine Gäste schauen sich Dinge an, die mehr Qualität in die Softwareentwicklung bringen.

Die aktuelle Ausgabe ist auch auf Richard Seidls Blog verfügbar: „Der perfekte Konferenz-Abstract – Elmar Jürgens“.

Weiterlesen nach der Anzeige


(mdo)



Source link

Weiterlesen

Entwicklung & Code

Browser-Engine Servo 0.0.5 mit Post-Quanten-Kryptografie veröffentlicht


Die Open-Source-Browser-Engine Servo ist in Version 0.0.5 erschienen. Das monatliche Release bringt Unterstützung für moderne Kryptografie-Standards: Servo gibt an, als erste Browser-Engine die Post-Quanten-Algorithmen ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism) und ML-DSA (Module-Lattice-Based Digital Signature Algorithm) vollständig in der Web Crypto API implementiert zu haben. Dazu kommen AES-OCB und verbessertes AES-GCM sowie detailliertere Fehlermeldungen bei kryptografischen Operationen.

Weiterlesen nach der Anzeige

Die quantenresistenten Verfahren schützen vor sogenannten Harvest-Now-Decrypt-Later-Angriffen, bei denen Angreifer verschlüsselte Daten sammeln, um sie später mit Quantencomputern zu entschlüsseln. ML-DSA hasht den Public Key zusätzlich, um Kollisionen und Key-Swapping-Angriffe zu verhindern. Wie das Servo-Projekt im Blog mitteilt, führt die Engine damit vor etablierten Browsern bei neuen Web-Cryptography-Algorithmen.

Bei den Web-Standards hat Servo 0.0.5 zahlreiche Verbesserungen erhalten: Die Engine unterstützt nun zum Vorladen von Ressourcen, und für bessere Kontrolle beim Seitenaufbau sowie und . Die Rust-basierte CSS-Engine Stylo wurde auf den Stand von Januar 2026 aktualisiert und beherrscht damit color-mix() sowie verbesserte Animationen für Borders und Overflow.

Performance und Stabilität

Servo 0.0.5 soll spürbare Performance-Verbesserungen bringen: Die IPC-Kanäle arbeiten effizienter, was besonders im Single-Process-Modus Geschwindigkeitsvorteile bringt. Der Socket-Timeout wurde auf 15 Sekunden gesetzt und jede Instanz benötigt vier Threads weniger als zuvor. Verbessertes Caching für SVG und animierte Bilder sowie Garbage-Collection-Optimierungen für Canvas und WebGPU beschleunigen die Darstellung. Die Verarbeitung von Nicht-ASCII-Text wurde sowohl bei Zeit als auch Speicherbedarf optimiert.

Zahlreiche Fixes erhöhen die Stabilität in den Bereichen Layout, WebGPU, Text-Input und IndexedDB. Das Block-Layout wurde überarbeitet und die JavaScript-Unterstützung erweitert: Cyclic Imports, Import Attributes und JSON Modules funktionieren nun korrekt. Die Origin API, MouseEvent.detail und Request.keepalive stehen ebenfalls zur Verfügung. IndexedDB macht Fortschritte bei Connection-Queues und Request-Granularity, muss aber weiterhin per --pref dom_indexeddb_enabled aktiviert werden.

Embedding und Plattformen

Weiterlesen nach der Anzeige

Für Entwickler, die Servo in eigene Anwendungen einbetten möchten, bringt Version 0.0.5 wichtige Verbesserungen: Cross-Compilation von einem Windows-Host ist nun möglich und SiteDataManager::clear_site_data() erlaubt DSGVO-konformes Löschen von gespeicherten Daten pro Host. Git-Abhängigkeiten sind jetzt gepinnt, um Reproduzierbarkeit zu gewährleisten. Die Grundlage für einen Accessibility Tree wurde gelegt, der künftig Technik rund um die Barrierefreiheit unterstützen soll.

Servo 0.0.5 ist für Windows, macOS (x86 und ARM, unsigned), Linux (mit geteilten Bibliotheken), Android und OpenHarmony verfügbar. Bei macOS ist wegen der fehlenden Signatur eine manuelle Freigabe nötig. Die Engine unterstützt nun auch HTTPS_PROXY und NO_PROXY für Netzwerk-Konfigurationen. Die vollständigen Release Notes stehen bei GitHub bereit.

Hintergrund des Projekts

Servo ist eine experimentelle Browser-Engine, die Mozilla ursprünglich 2012 startete, um moderne Webtechnologien in der Programmiersprache Rust zu implementieren. Nach einer längeren Unterbrechung gab es für das Projekt 2023 einen Neustart unter der Linux Foundation Europe mit Unterstützung von Igalia. Seit Oktober 2025 erscheinen monatliche Releases, die auf Nightly-Builds aufbauen und durch manuelle Tests ergänzt werden. Die Engine zielt darauf ab, Entwicklern eine leichtgewichtige, performante Alternative für die Einbettung von Web-Technologien in Anwendungen zu bieten.

Das erste offizielle Release 0.0.1 brachte im Oktober 2025 erstmals vorkompilierte Binaries für ARM-Macs. Die CSS-Engine Stylo, die Servo und Firefox gemeinsam nutzen, hat sich als stabil erwiesen und zeigt, wie Rust-Code in produktiven Browser-Umgebungen eingesetzt werden kann.


(fo)



Source link

Weiterlesen

Beliebt