On the Analysis of Two Fundamental Randomized Algorithms - Multi-Pivot Quicksort and Efficient Hash Functions
Martin Dr.rer.nat. Aumüller · Common Library Network (Der Gemeinsame Bibliotheksverbund) · 2015
Im ersten Teil der vorliegenden Arbeit werden Multi-Pivot-Quicksort-Algorithmenbetrachtet. Die Idee mehr als ein Pivotelement im Quicksort-Algorithmus zunutzen, erschien über viele Jahre als unpraktikabel. Dies änderte sich, als imJahr 2009 ein Dual-Pivot-Algorithmus von V. Yaroslavskiy zumStandard-Sortierverfahren in Java 7 wurde. Die vorliegende Arbeit stellt eineStudie von Multi-Pivot-Quicksort-Algorithmen dar, also Quicksort-Varianten, diemit mehr als einem Pivotelement arbeiten. Sie beschreibt dieKonstruktionsprinzipien von 2-Pivot-Algorithmen in Bezug auf die bei derSortierung notwendigen Schlüsselvergleiche. Ein Ergebnis dieser Untersuchungsind zwei optimale und leicht zu implementierende 2-Pivot-Algorithmen. DieVerallgemeinerung auf >= 3 Pivotelemente benötigt nur kleine Anpassungen. DieseArbeit betrachtet außerdem die theoretische Analyse von Kostenmaßen, die esermöglichen, Multi-Pivot-Quicksort-Algorithmen hinsichtlich ihres Speicher- undCacheverhaltens zu vergleichen. Sie schließt mit einer Laufzeitstudie derbesprochenen Algorithmen. Der zweite Teil der Arbeit beschäftigt sich mit dem Einsatz von Hashfunktionenin Algorithmen und Datenstrukturen. Hashfunktionen bilden eine Kernkomponente,z.B. beim Aufbau einer Hashtabelle oder bei Lastbalancierung. Oft wird dabeieine unrealistische Annahme getätigt: Die Hashwerte seien voll zufällig. DieSpeicherplatzkomplexität einer solchen Funktion ist für den praktischen Einsatzfür unverhältnismäßig hoch. Das Ziel ist, einfache Konstruktionen zu finden,deren Zufallseigenschaften beweisbar gut sind. Diese Arbeit beschreibt einesolche einfache Konstruktion von Hashfunktionen, die in einer Vielzahl vonAnwendungen beweisbar gut ist. Zu diesen Anwendungen zählen Cuckoo Hashing miteinem sogenannten Stash, die Konstruktion einer perfekten Hashfunktion, dieSimulation einer uniformen Hashfunktion, verschiedene Algorithmen zurLastbalancierung und verallgemeinertes Cuckoo Hashing in einer leichtabgeschwächten Variante mit verschiedenen Einfügealgorithmen. Der zentraleBeitrag dieser Dissertation ist ein einheitliches Analysekonzept. Diesesermöglicht es, eine auf Hashfunktionen basierende Datenstruktur oder einen aufHashfunktionen basierenden Algorithmus nur mit Mitteln der Theorie vonZufallsgraphen zu analysieren, ohne Details der Hashfunktion offenzulegen.