Logo des Repositoriums

Auflistung nach Autor:in "Wild, Sebastian"

1 - 2 von 2
  • Zeitschriftenartikel
    Dual-pivot and beyond: The potential of multiway partitioning in quicksort
    (it - Information Technology: Vol. 60, No. 3, 2018) Wild, Sebastian
    Since 2011 the Java runtime library uses a Quicksort variant with two pivot elements. For reasons that remained unclear for years it is faster than the previous Quicksort implementation by more than 10 %; this is not only surprising because the previous code was highly-tuned and is used in many programming libraries, but also since earlier theoretical investigations suggested that using several pivots in Quicksort is not helpful. In my dissertation I proved by a comprehensive mathematical analysis of all sensible Quicksort partitioning variants that (a) indeed there is hardly any advantage to be gained from multiway partitioning in terms of the number of comparisons (and more generally in terms of CPU costs), but (b) multiway partitioning does significantly reduce the amount of data to be moved between CPU and main memory. Moreover, this more efficient use of the memory hierarchy is not achieved by any of the other well-known optimizations of Quicksort, but only through the use of several pivots.
  • Konferenzbeitrag
    Quicksort mit zwei Pivots und mehr: Eine mathematische Analyse von Mehrwege-Partitionierungsverfahren und der Frage, wie Quicksort dadurch schneller wird
    (Ausgezeichnete Informatikdissertationen 2016, 2017) Wild, Sebastian
    Seit 2011 kommt in der Java runtime library eine Quicksort-Variante mit zwei Pivots zum Einsatz, von der lange unklar war, warum sie gegenüber der vorherigen, ausoptimierten Quicksort-Implementierung nochmals über 10% Laufzeit einsparen kann. Das verwundert umso mehr, da frühere Untersuchungen keinen Vorteil in der Verwendung mehrerer Pivots erwarten ließen. Durch eine umfassende mathematische Analyse aller sinnvollen Quicksort-Varianten konnte ich beweisen, dass durch die Verwendung mehrerer Pivots tatsächlich keine wesentliche Ersparnis bei der Anzahl an Vergleichen, und allgemeiner dem Aufwand innerhalb der CPU, zu erwarten ist, wohl aber eine deutliche Reduktion des Datenvolumens, das zwischen Hauptspeicher und CPU transferiert werden muss. Diese effizientere Nutzung der Speicherhierarchie ist dabei nur durch den Einsatz mehrerer Pivots, und durch keine andere der vielen bekannten Optimierungen von Quicksort zu erreichen.