Office2000

 Documents

 28 views
of 25
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Kap. 7 Sortierverfahren Kap. 7.0 Darstellung, Vorüberlegungen  = {(x,)} mit internes Sortieren externes Sortieren  pat  pat nicht in AS…
Share
Transcript
Kap. 7 Sortierverfahren Kap. 7.0 Darstellung, Vorüberlegungen  = {(x,)} mit < internes Sortieren externes Sortieren  pat  pat nicht in AS Darstellung von <: 3 6 1 7 ungeordnet, < berechnen 1 3 6 7 <  phys. Reihung 3 6 1 7 Liste verkettet sortierter Baum mit Inordnung - mit Zeigern - Adrerechnung 1 1. Einfache Feldorganisation: S[1], ..., S[n] Für Sortieren am Platz: Tausch-Operation! 2. Doppelfeld: S[1], ..., S[n] T[1], ..., T[n] für Misch-Verfahren: Speicher: 2n; Zeit: (n log n) Sätze variabler Länge? 2 3. Listenorganisation: (x, ) erweitern um Verweis v auf Nachfolger Tauschoperation? Anpassung von Quicksort? 4. Zeigerfeld: für lange Sätze und Sätze variabler Länge. Sortiere Zeiger! vx (x, ) vx gespeichert in Feld V[1] ... V[n] vx < vy  x < y sortiere V nach < , kopiere S nach < 3 5. Feld von Paaren: ( x, vx) falls  variabel lang x feste Länge speichere (x ,vx ) in V, sortiere V nach < auf X. Auch o.k. falls  nicht in AS pat, aber v = {(x, vx)} pat Problem: gut für random Zugriff auf , aber sequentielle Verarbeitung von  nach < problematisch: 1 Plattenzugriff pro Element von . 4 Kap. 7.1 Zu internen Sortierverfahren Einfache Verfahren mit O(n 2 ) - Auswahl - Einfüge (bubble) - Austausch Quicksort: Zeit? Speicher: Kaskadenrekursion erfordert Rückstellung einer Partitionsklasse für Laufzeitkeller n zurückgestellt, Kellertiefe? ? 2n ? n log n 5 Baumsortierung: Heapsort (Stadelsort) Speicher: am Platz, schichtenweise sequentielle Darstellung des Binär-Baums O(n log n) Zeit: garantiert Zentral für externe Sortierverfahren Umwandlung heap in sortiertes Feld: M [1:n] Baum  M [1:i] mit i  n ist Baum mit denselben Vater-Sohn Beziehungen 6 Lemma: Falls M[1:n] Stadel ist, ist auch M[1:i] und M[j:n] Stadel für alle i, j. j ... Sort – Merge intern: Zeit: O(n log n) Speicher: 2n bzw. 1.5 n 7 Kap. 7.2 Externes Sortieren Phase 1: Initialläufe: sortierte Teilmengen durch internes Sortieren   A  a1 , a2 ,...ae1 ; i  j  ai  a B  b , b ,..., b  1 2 e1 C  AB durch Mischung (merge) von A und B Seien a j , bi kleinste, ungemischte Elementen von A, B ck 1 : min a j , bi  Bei Mischung von m Initialläufen z.B. m = 5000 ck 1 : min ai  i 1... 5000 verwende Heap! 8 Phase 2: Reines Mischen: Datei mit N Elementen 0. Läufe der Länge 1  20vorhanden 1. Läufe der Länge 2  21 ... d. Läufe der Länge 2d für kleinstes d mit 2d  N  d  log 2 N  Ziel: bei 1. Durchgang möglichst lange Initialläufe durch internes Sortieren Bei S Speicher: Länge S: in place Verfahren, feste Satzlänge Länge S/2: internes Mischen Länge 2S: Stadelsort, erspart bis zu 2 externe Mischdurchgänge 9 Mit Auswahlverfahren: M [1] ... M [s] 1. min. suchen i 2. Ausgabe: y := M[i] min M i , M i   y 3. Eingabe: M[i] := x i x kann an nächster min-Suche teilnehmen, falls x  y i  A 2 3 Problem: min-Suche in M von (S) 10 Mit Heap: 1 .... i ... s 1 Stadel für viele Stadel für zu kleine Ausgabekandidaten Schlüssel 11 Algorithmus für Initialläufe: 12 var L: {für letzten ausgegebenen Schlüssel} H: {für neue Eingabe von } {Stadel in M[1:S]} starte neuen Initiallauf: i := S ; while i > 0 do {Ausgabestadel M [1:i]  } begin L := M [1]; gebe L aus; H := Eingabe vom ; if H  L then {H noch zu Initiallauf} begin M[1] := H; SENKE (1,i) end else begin M[1] = M[i]; M[i] = H; SENKE (i,S); i := i-1; SENKE (1,i) end end {keine E/A Stockung!!!} Externes Mischen mit Bändern 2 Wege, 3 Bänder: U  A1 , A2 , A3 V  B1 , B2 , B3 W  C1  A1B1 , C2  A2 B2 , C3  A3 B3 Merge von C1 , C2 , C?3 1. Symetrisches Mischen, vollständiges Kopieren W  C1 , C2 , C3  U  C1C2 U  C1 , C3 V  C3 V  C2 ,  W  C1C2C 3 W  C1C2 , C3 => 6 Durchgänge Kopiervorgänge fur C3 ? 13 Aufwand für N Initialläufe: log 2 N  Mischdurchgänge log m N  log 2 N   1 Kopierdurchgänge log m N   1 1 Initiallauf-Durchgang 1 gesamt: 2·log m N  Durchgänge 1 Durchg. = 1 x lesen ganz Σ 1 x schreiben für m–Wege Mischen, m+1 Bänder 14 2. Symmetrisches Mischen, unvollständiges Kopieren nach 1. Mischdurchgang: W  C1 , C2 , C3  U  C1 V  C1C2 U  C1C2C 3 => 4 Durchgänge statt 6 15 Mischbaum nach Knuth U 1 V 2 C1C 2 U W 3 C1 W W 6 C1 5 C2 4 C3 U V U V U V A1 12 11 B1 A2 10 9 B2 A3 8 7 A3 4 4 3 3 2 2 16 Symmetrisches Mischen, 2m Bänder fast ohne Kopieren, je m Bänder alternierend als Eingabe und Ausgabe Baum für vorherige Initialläufe, 4 Bänder, symm. Mischen Kosten? Mehrphasen Mischen (polyphase): Sortieren ohne zu kopieren? letzter Mischdurchgang, Zustände vorher? 1 Rekursionsgleichung für Anzahl Läufe auf Band 0 Ci Ci 1 2 3 U V W Ci 1 (Ci 1  Ci ) 0 0 0 1 1 1 0  Ci  2 2 0 1 i.e Fibonacci 17 0 2 3 Problem: Länge der entstehenden Zwischenläufe: z.B. 5-Wege, 65 Läufe 0 0 0 0 0 165 65 11 15 19 117 133 0 33 21 25 29 217 0 11 34 41 45 49 0 21 31 36 81 85 0 41 61 71 40 161 0 81 121 141 151 65 273 18 Ohne Rückspulung: Bänder vorwärts schreiben,  rückwärts lesen:  0 0 1 1 1 0 2  0 1 0 2  3  19 Allg. Fall.: m+1 Bänder m Wege m-1 Fib. Zahlen für nächste Phase Ck m 1 ... Ck  m  i ... Ck 0 Ck m1  Ck  ... Ck mi  Ck  ... 0 Ck i.e. Ck mi  Ck  Ck i für i = 1 , ... , m-1 m-1 neue Fib.-Zahlen der Ordnung m-1 20 Kap. 7.3 Sortieren, Platten, Parallelität n Annahme: AS mit 10Bytes, 3 Seitengröße 10Bytes i.e. 10 n Seiten 3 Länge Initialläufe: 2·10 nBytes Heap zum Mischen Mischgrad: ½ •10n-3= 5000 Wechsel-Puffer ... bei AS = 10MB 1 Mischlauf: ½ •10n-3• 2 • 104 = 10 2n-3 Bytes 21 Workstations: n=7 d.h. 1011 B = 100 GB in1 Lauf sortiert Problem: UNIX File-System Mainframes: n=8 d.h. 1013 B = 10 TB in 1 Lauf sortiert Fazit: Bei heutiger Rechner-Technologie ist Sortieren ein linearer Algorithmus! CPU-Last: AS = 10n B 1 Element sei z.B. 100 Bytes  Heap hat 10n-2 Knoten, z.B. Bei n=7: 105 Knoten 22 Heap Höhe: log2105 ≈ 17 SENKE Aufrufe pro Element mit je 4 Vergleichen: string-Vergleich: - extrahiere Attribut aus Tupel, Additionen, ≈ 500 Multiplikationen Befehle - Adressrechnung für M[k], M[2k], M[2k+1]  Pro El. ≈ 104 Befehle? Festplatte: 500 KB/s Nutzleistung ∼ ~ 5000 El/s CPU: 5000 El/s * 104 Befehle/El = 50 MIPS oder mehr  Potential für paralleles Sortieren! 1991: CPU bremst um Faktor 5!! 2000: CPU bremst bei RAID 23 Beispiel: Sortiere 100 MB auf SUN 4 Initialläufe: 1 x lesen ≈ 200 s 1 x schreiben≈ 200 s 400 s Beim Einlesen Bremsfaktor 5 wegen langsamer CPU: 1000 s Prozessor-Engpass!! Mischlauf: 1 x lesen random Zugriff 1 x schreiben zur Platte ≤ 50 Seiten/s, d.h. Plattenleistung: ≤  50 KB/s bei 1KB/Seite ≤  200 KB/s bei 4 KB/Seite 24 1 KB/Seite: 1 x lesen ∼ 2000 s 1 x schreiben ∼ 2000 s für Mischen 4000 s 4 KB/Seite: 1 x lesen ∼ 500 s 1 x schreiben ∼ 500 s für Mischen 1000 s Mischgrad 5 bis 20, kleiner Heap, CPU bremst nicht! Mischphase ist Plattenengpass!! Gesamtzeit: 2000 s mit 4 KB/Seite 5000 s mit 1 KB/Seite 5000 s = 83 min Hinweis: bei niedrigem Mischgrad, z.B. 10, verwende maximale E/A-Pufferung, mehrere Seiten pro Wechselpuffer: 25
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks