HPI Kolloquium: Prof. Sebastian Wild

Quicksort, Timsort, Powersort - Algorithmic ideas, engineering tricks, and trivia behind CPython’s new sorting algorithm

• Dozent: Prof. Dr. Sebastian Wild, AG Algorithmik, Fachbereich Mathematik und Informatik, Philipps-Universität Marburg
• Gastgeber: Prof. Tobias Friedrich, HPI-Geschäftsführer und Fachgebietsleiter “Algorithm Engineering”

Online-Teilnahme 

Zusammenfassung

Im Jahr 2002 erfand Tim Peters Timsort, eine clevere Variante des Mergesort-Algorithmus, für die CPython-Referenzimplementierung der Programmiersprache Python. Timsort ist sowohl in Python effektiv als auch ein beliebtes Exportprodukt: Es wird in vielen Sprachen und Frameworks verwendet, insbesondere in Open-JDK, der Android-Laufzeitumgebung und der V8-JavaScript-Engine. Trotz seiner weit verbreiteten Verwendung entdeckten Forschende schließlich zwei Mängel im zugrunde liegenden Algorithmus von Timsort: Der erste konnte zu einem Stapelüberlauf in CPython und Java führen. Obwohl er inzwischen behoben wurde, legte er konzeptionelle Feinheiten des Algorithmus offen. Der zweite Mangel betrifft seine Leistung: Die Reihenfolge, in der erkannte sortierte Segmente, die “Läufe” der Eingabe, zusammengeführt werden, kann 50 % mehr Aufwand erfordern als nötig. Basierend auf Ideen aus optimalen alphabetischen Bäumen findet unsere Powersort-Merge-Richtlinie nahezu optimale Merge-Reihenfolgen mit vernachlässigbarem Overhead und unter Verwendung einer viel transparenteren Regel. Seit Python 3.11 ist sie Teil der CPython-Referenzimplementierung. Der Vortrag beschreibt die beteiligten Algorithmen ohne Vorkenntnisse.

Über Prof. Dr. Sebastian Wild

Sebastian Wild leitet die Arbeitsgruppe Algorithmik am Fachbereich Informatik der Universität Marburg und ist Senior Lecturer an der Universität Liverpool. Seine Forschungsinteressen umfassen platzsparende Datenstrukturen, die Analyse von Algorithmen und die Entwicklung grundlegender Algorithmen. Bevor er nach Marburg kam, war er Dozent an der Universität Liverpool und davor Postdoktorand an der University of Waterloo. Prof. Wild hat an der Universität Kaiserslautern promoviert. Seine Doktorarbeit über die Analyse von Multiway-Quicksort wurde mit dem GI-Dissertationspreis 2016 ausgezeichnet. Mehr Infos