External Quicksort Optimierung des Quicksort-Verfahrens für Speicherhierarchien Martin Gronemann, Bernd Zey.
Veröffentlicht von:Adalstan Bork Geändert vor über 4 Jahren
Präsentation zum Thema: "External Quicksort Optimierung des Quicksort-Verfahrens für Speicherhierarchien Martin Gronemann, Bernd Zey."— Präsentation transkript:
1 External Quicksort Optimierung des Quicksort-Verfahrens für Speicherhierarchien Martin Gronemann, Bernd Zey
2 Überblick Quicksort - Erinnerung Intuitive Lösung
Distribution-Sort (external Quicksort)
3 Quicksort - Erinnerung
Pivot-Element: 23 R L 12 5 23 1 60 17 55 22 42 L 42 12 L L 22 1 L 1 60 55 23 17 R 23 17 R 60 55 R 12 5 22 1 60 17 55 42 23 12 5 22 1 60 23 55 42 17 12 5 23 1 60 17 55 22 42 12 5 23 1 60 17 55 22 42 12 12 5 42 23 1 60 17 55 22 5 12 5 22 1 17 55 42 60 23 1 5 22 17 42 60 12 23 55 1 5 17 22 42 60 12 23 55
4 Intuitive Lösung Lade den Wert des Pivot-Elements und die ersten und letzen B Array-Elemente in den Main Memory Starte normalen Quicksort Laden und Schreiben bei Bedarf
5 Intuitive Lösung: Beispiel
EM: L R L R L R L R L R L R MM: L R L R L R L R Pivot
6 Analyse: Intuitive Lösung
Analyse der I/O‘s äquivalent zur Laufzeitanalyse von Quicksort Pro Rekursionstiefe: O(N/B) I/O‘s benötigt Im average case beträgt die Rekursionstiefe O(log2 N) I/O-Anzahl O(N/B log2 N/B) interne Laufzeit O(N log2 N) Im worst case (N2)
7 Distribution Sort Mit mehreren Pivot-Elementen arbeiten
Pivot-Elemente definieren „Buckets“ Element muss in „Bucket“ einsortiert werden Jeden „Bucket“ rekursiv sortieren bis Blockgröße B erreicht ist
8 Berechnung der Pivot-Elemente (1)
Unterteile Eingabemenge in N/M Chunks Sortiere jeden Chunk Nehme jedes a-te Element aus jedem Chunk in Array U auf (|U| = N/a) Sortiere U Berechne µ-1 äquidistante Pivot-Elemente aus dem Array U mit BFPRT (Blum-Floyd-Pratt-Rivest-Tarjan)
Chunks (sortiert) Array U (sortiert) BFPRT µ-1 Pivot-Elemente
10 Analyse: Berechnung der Pivot-Elemente
U kann mit O(N/B) I/O‘s erzeugt werden. BFPRT benötigt O((|U|/B) lg µ) = O((N/aB) lg µ) I/O‘s Für a ≥ lg µ: O(N/B) Insgesamt O(N/B) I/O‘s für die Berechnung der Pivot-Elemente
11 Rekursion Sortiere jedes Element in den richtigen „Bucket“ (Distribution) Bi := {x | pi ≤ x < pi+1} Starte Rekursion auf jedem „Bucket“ Wenn „Bucket“ Blockgröße erreicht hat dann intern sortieren
12 Beispiel µ=4 Pivot 1 Pivot 2 Pivot 3 -∞ ∞ Blockgröße
Rekursionstiefe: O(logµN/B)
13 Analyse Rekursionstiefe bis zur Blockgröße: O(logµ N/B) I/O‘s
Einsortieren kostet pro Rekursionstiefe O(N/B) I/O‘s Gesamt: O(N/B logµ N/B) I/O‘s
14 Literatur Alok Aggarwal and Jerey Scott Vitter, 1988:
„The Input/Output Complexity of Sorting and Related Problems“ Jeff Erickson - Prof. an der University of Illinois: „Introduction: the standard external-memory model; upper and lower bounds for scanning (Θ(n)), searching (Θ(logB n) via B-trees), and sorting (Θ(n logm n) via mergesort); external comparison trees“
Herunterladen ppt "External Quicksort Optimierung des Quicksort-Verfahrens für Speicherhierarchien Martin Gronemann, Bernd Zey."
DNA-Array oder DNA-Chip
Algorithmen und Komplexität Teil 1: Grundlegende Algorithmen
WS 03/041 Algorithmentheorie 01 - Einleitung Prof. Dr. S. Albers Prof. Dr. Th. Ottmann.
Kapitel 6: Klassifizierung von Sortiertechniken Kapitel 7. Sortier-Algorithmen
5. Sortier-Algorithmen Vorbemerkungen:
Sortierverfahren Richard Göbel.
Vorlesung 15. Januar 2009.
WS 03/04 Algorithmentheorie 03 - Randomisierung Prof. Dr. S. Albers Prof. Dr. Th. Ottmann.
1 Vorlesung Informatik 2 Algorithmen und Datenstrukturen (03 – Verschiedene Algorithmen für dasselbe Problem) Prof. Dr. Th. Ottmann.
Vorlesung Informatik 2 Algorithmen und Datenstrukturen (08 - Einfache Sortierverfahren) Prof. Th. Ottmann.
WS Algorithmentheorie 01 – Divide and Conquer (Segmentschnitt) Prof. Dr. Th. Ottmann.
Vorlesung Informatik 2 Algorithmen und Datenstrukturen (10 - Suchverfahren) T. Lauer.
Vorlesung Informatik 2 Algorithmen und Datenstrukturen Halbzeit: Was haben wir bisher gelernt? Prof. Th. Ottmann.
Informatik II, SS 2008 Algorithmen und Datenstrukturen Vorlesung 4 Prof. Dr. Thomas Ottmann Algorithmen & Datenstrukturen, Institut für Informatik Fakultät.
Entwicklung epistemologischer Überzeugungen