Logo des Repositoriums
 

Quicksort mit zwei Pivots und mehr: Eine mathematische Analyse von Mehrwege-Partitionierungsverfahren und der Frage, wie Quicksort dadurch schneller wird

dc.contributor.authorWild, Sebastian
dc.contributor.editorHölldobler, Steffen
dc.date.accessioned2019-01-23T14:30:42Z
dc.date.available2019-01-23T14:30:42Z
dc.date.issued2017
dc.description.abstractSeit 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.de
dc.identifier.isbn978-3-88579-976-4
dc.identifier.urihttps://dl.gi.de/handle/20.500.12116/19952
dc.language.isode
dc.publisherGesellschaft für Informatik e.V.
dc.relation.ispartofAusgezeichnete Informatikdissertationen 2016
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Proceedings, Volume D-17
dc.titleQuicksort mit zwei Pivots und mehr: Eine mathematische Analyse von Mehrwege-Partitionierungsverfahren und der Frage, wie Quicksort dadurch schneller wirdde
dc.typeText/Conference Paper
gi.citation.endPage328
gi.citation.publisherPlaceBonn
gi.citation.startPage319
gi.conference.date21.-24. Mai 2017
gi.conference.locationSchoss Dagstuhl, Deutschland

Dateien

Originalbündel
1 - 1 von 1
Lade...
Vorschaubild
Name:
invited_paper_32.pdf
Größe:
3.21 MB
Format:
Adobe Portable Document Format