In diesem interaktiven Workshop behandeln wir mehrere Schlüsseltechniken der Optimierung von Algorithmen und zeigen, wie diese in Python (oder Java) umgesetzt werden können.
Einstieg und Big-O
Wir lernen ein paar theoretische Grundlagen zu Optimierungen kennen und insbesondere auch den Einfluss der Menge zu verarbeitenden Daten.
Berechnungen Pair Sum
Am Beispiel einfacher Berechnungen, die oftmals quadratische Laufzeit besitzen, lernen wir, die Optimierungen «Two-Pointers», «HashMap» und «Sortierung» kennen.
Prefix-Summen
Die Prefixsummen-Technik ermöglicht extrem schnelle Berechnungen auf kumulierten Werten in Arrays bzw. Listen. Dies ist eine essenzielle Methode, um Probleme wie das Berechnen von Teilsummen oder das Lösen von Bereichsproblemen effizient zu lösen.
Rekursion und Memoization
Rekursion erlaubt es, Probleme elegant zu lösen. Zum Einstieg lernen wir den Vorteil durch Sortierung kennen und implementieren die klassische Binärsuche, einmal rekursiv und iterativ. Als Schmankerl schauen wir uns die Varianten «Lower und Upper Binary Search» zum Finden des ersten und letzten Werts bei mehreren gleichen Werten an. Die Eleganz von Rekursion kommt allerdings in der Praxis oftmals mit dem unschönen Nebeneffekt einer langen Laufzeit, etwa bei der Berechnung von Fibonacci-Zahlen. Als Abhilfe lernen wir Memoization als Technik kennen, die Zwischenergebnisse speichert, um wiederholte Berechnungen zu vermeiden. Damit lassen sich dramatische Performance-Verbesserungen erzielen.
Sortieralgorithmen
Eine sorgfältige Auswahl des richtigen Sortieralgorithmus kann einen signifikanten Einfluss auf die Performance haben. Wir schauen uns einführend Selection und Insertion Sort an, um dann QuickSort und MergeSort zu verstehen. Aber es geht mit BucketSort nochmals schneller, nämlich in linearer Zeit.
Clevere Datenstrukturen: Tries — Build your own Auto-Completion
Wollten Sie schon immer einmal wissen, wie man eine Auto Completion implementiert und dies zudem extrem schnell und gut macht? Hier erhalten Sie eine Einführung in Tries als unbekannte Datenstruktur und lernen grundlegende Aktionen damit kennen. Danach implementieren wie eine rasend schnell arbeitende Auto Completion.
Theorie trifft Praxis
Theorie ist wichtig, doch entscheidend für den Lernerfolg sind praxisorientierte Übungen, bei denen die Teilnehmer:innen aktiv an der Optimierung von Algorithmen arbeiten. In diesem Workshop haben Sie die Möglichkeit, die vorgestellten Techniken direkt anzuwenden, eigene Lösungen zu entwickeln und von den Feedbacks des Trainers zu profitieren.
