Embed Size (px)
Citation preview
Externspeicher-Algorithmen
Petra Mutzel Technische Universität Wien
Institut für Computergraphik und Algorithmen
Algorithmen und Datenstrukturen 2
Zufälliges Durchlaufen:
for (i=0; i<N; i++) A[C[i]]=A[C[i]]+1;
Durchwandern eines Arrays
for (i=0; i<N; i++) D[i]=i;
C=Permute(D)
Lineares Durchlaufen:
for (i=0; i<N; i++) A[D[i]]=A[D[i]]+1;
0,00
1,00
2,00
3,00
4,00
5,00
6,00
7,00
8,00
9,00
18 19 20 21 22 23 24 25
zufällig
linear
Größe 2k
Durchwandern eines Arrays
k
sec
223=8.388.608
1,00
10,00
18 19 20 21 22 23 24 25
zufällig
linear
Logarithmische Skalierung
Durchwandern eines Arrays
Größe 2k
sec
k
CPU Cachemain
(internal)memory
Extern-speicher
secondary memory
Faktor 100 schneller als
Faktor 1000-106 schneller als
Hierarchisches Speichermodell moderner Computer
Probleme klassischer Algorithmen
• Meist keine Lokalität bei Speicherzugriffen, und deswegen mehr Speicherzugriffe als nötig
• Ein Zugriff im Externspeicher (ein I/O) liefert jeweils einen ganzen Block von Daten zurück
• Ein Zugriff im Hauptspeicher spricht jeweils eine Speicherzelle an und liefert jeweils eine Einheit zurück
Problem ist aktueller denn je, denn
• Geschwindigkeit der Prozessoren verbessert sich zwischen 30%-50% im Jahr;
• Geschwindigkeit des Speichers nur um 7%-10% pro Jahr
• „One of the few resources increasing faster than the speed of computer hardware is the amount of data to be processed.“
Das Theoretische Sekundärspeichermodell (Parallel Disk Modell)
CPU
main(internal)memory
Extern-speicher
M = Anzahl der Elemente im Haupt-speicher
B = Anzahl der Elemente, die in einen Block passen
Annahme: B<=M/2
voneinander unabhängig
Rechenoperationen können nur mit Daten im Haupt-speicher getätigt werden
Modell von Vitter und Shriver 1994
Analyse von Externen Algorithmen
• Anzahl der ausgeführten I/O-Operationen
• Anzahl der ausgeführten CPU-Operationen im RAM-Modell
• Anzahl der belegten Blöcke auf dem Sekundärspeicher
Untere Schranken im EM-Modell
• Einlesen einer Menge von N Elementen benötigt mindestens Θ(N/B) I/O‘s
• Sortieren einer Menge von N Elementen benötigt mindestens
Θ(N/B log1+M/B (1+N/B)) (o.Bw.)
• Suche in dynamischen Daten von N Elementen benötigt mindestens Zeit
Θ(log N / log B) I/O-Operationen
Externspeicherdatenstruktur für Prioritätswarteschlangen
• Dynamische Datenstruktur für Elemente: Schlüssel + Information
• Operationen:– Get_Min: Ausgabe der Elemente mit
kleinstem Schlüssel– Del_Min: Ausgabe und Entfernung des
kleinsten Elements– Insert: Einfügen eines neuen Elements
Welche Datenstrukturen kennen Sie dafür?
Externe Array-Heaps
• Im internen Arbeitsspeicher: Heap
• Im externen Speicher: Menge von sortierten Feldern unterschiedlicher Länge
Externe Array-Heaps
Lemma 1: li+1=li (μ+1)
μ=(cM/B)-1
L1
L2
L3
l2
l3=l2(μ+1)
li=(cM)i/Bi-1
μ μ
L Schichten Li
Slots:enthaltensortierte Folgeoder sind leer
Die Anzahl der Plätze in einem Slot von Li+1 entspricht der Anzahl aller Plätze in Li
c=1/7L<=4
Operation Insert
• Fügt neue Elemente immer in den internen Heap H ein
• Falls kein Platz mehr in H ist, dann werden vorher l1=cM dieser Elemente in den Sekundärspeicher bewegt:– Falls freier Slot in L1 existiert, dann werden diese
Elemente in sortierter Folge dorthin bewegt– Sonst: Alle Elemente in L1 werden mit den neuen
Elementen aus H zu einer sortierten Liste gemischt, die dann in einen freien Slot von L2 geschrieben werden.
– Falls L2 auch kein freier Slot, wiederhole L3,...bis frei.
Operation Del_Min
• Invariante: Das kleinste Element befindet sich immer in H
• Dazu: Heap wird in zwei Heaps geteilt: H1 und H2:– H1 enthält immer die neu eingefügten Elemente,
maximal 2cM– H2 speichert maximal die kleinsten B Elemente in
jedem belegten Slot j in jeder Schicht Li
• Lemma 2: Es befinden sich maximal cM(2+L) Elemente im Hauptspeicher
• Zusätzlich wird (μ+1)B=cM gebraucht, um die μ Slots plus eine Overflow Folge zu mischen
Operation Del_Min
• Invariante: Das kleinste Element befindet sich immer in H
• Dazu: Heap wird in zwei Heaps geteilt: H1 und H2:– H1 enthält immer die neu eingefügten Elemente,
maximal 2cM– H2 speichert maximal die kleinsten B Elemente in
jedem belegten Slot in L
• Lemma 2: Es befinden sich maximal cM(2+L) Elemente im Hauptspeicher
• Zusätzlich wird (μ+1)B=cM gebraucht, um die μ Slots plus eine Overflow Folge zu mischen
Es muss gelten: M>=cM(3+L);Daraus folgt: bei c=1/7 => L<=4
Operationen (1)
• Merge-Level (i,S,S´): – produziert eine sortierte Folge S´ durch das
Mischen der sortierten Folge der μ Slots in Li (inkl. der ersten Blocks in H2) und die sortierte Sequenz S.
– Analyse: O(li+1/B) I/O´s
• Store(i;S):– Annahme: Li enthält einen leeren Slot und die
Folge S besitzt Länge im Bereich [li/2 , li]
– S wird in einen leeren Slot von Li gespeichert und seine kleinsten B Elemente werden nach H bewegt.
– Analyse: O(li/B) I/O´s
• Load (i,j): – Holt die nächsten B kleinsten Elemente vom j-ten
Slot aus Li in den internen Heap H2.– Analyse: O(1) I/O´s
• Compact(i):– Annahme: es existieren mind. 2 Slots in Li, mit
Gesamtzahl an Elementen (inkl. H), höchstens li.– Diese beiden Slots werden gemischt, und in einen
freien Slot von Li eingetragen. Damit wird ein Slot in Li frei.
– S wird zu diesem freien Slot bewegt (kleinste B Elemente nach H).
– Analyse: O(li/B) I/O´s
Operationen (2)
Operation Insert• Fügt neue Elemente immer in den internen Heap
H ein
• Falls kein Platz mehr in H1 ist, dann werden die größten l1=cM Elemente nach L1 bewegt (und die kleinsten B davon nach H2):– Falls freier Slot in L1 existiert, dann wird Store(1,S)
aufgerufen– Sonst: Alle Elemente in L1 enthalten mindestens li/2
Elemente: Merge-Level(i,S,S´)– Falls freier Slot in L2 existiert, dann: Store(2,S)– Sonst: wiederhole L3,...bis frei.
Operation Del_Min
• Das kleinste Element wird vom internen Heap entfernt (H1 oder H2).
• Falls in H2: dann korrespondiert dieses zu Slot j einer Schicht Li.
• Falls es das letzte Element in H2 ist, das zu j gehört, dann werden die nächsten B Elemente von Slot j nach H2 mittels Load(i,j) bewegt.
• Nach jedem Load(i,j) wird Compact(i) bei Bedarf aufgerufen
Korrektheit
• Lemma 3: Das kleinste Element ist immer in H
(H1 oder H2).
• Lemma 4: Es ist immer ein freier Platz für neue
Elemente vorhanden.
I/O Schranken
• Annahme: cM>3B
• Lemma 5: Nach N Operationen existieren
höchstens L<=logcM/B(N/B) Schichten.
• Lemma 6: Store(i,S) benötigt höchstens 3li/B I/O
´s. Compact(i+1) und Merge-Level(i,S,S´)
benötigen höchstens 3li+1/B I/O´s.
I/O Schranken
Theorem:
Annahme: cM>3B und 0<c<1/3 und N<=B(cM/B)1/c-3
In einer Folge von N Operationen der Art Insert und Del_Min
benötigt
– Insert amortisiert 18/B(log cM/B(N/B)) I/O´s und
– Del_Min 7/B amortisierte I/O´s.
Speicherplatzbedarf
Lemma 7: Jede Schicht enthält höchstens einen Slot, der
nicht-leer und aus weniger als li/2 Elementen besitzt.
Theorem 2: Die Gesamtanzahl der benützten Blöcke ist
höchstens 2(X/B)+2, wobei X die Anzahl der Elemente im
Heap H ist. Der Gesamtspeicherplatz im Arbeitsspeicher
beträgt cM(3+L).
1
10
100
1000
10000
100000
1 5 10 25 50 75 100 150 200
radix heap
array heap
buffer tree
B-tree
Insert: zuerst Insert, dann Del_Min
*106
1
10
100
1000
10000
100000
1 5 10 25 50 75 100 150 200
radix heap
array heap
buffer tree
B-tree
Del_Min: zuerst Insert, dann Del_Min
*106
1
10
100
1000
10000
100000
1000000
1 5 10 25 50 75 100 150 200
radix heap
array heap
buffer tree
Insert: Zufällige Folge
*106
1
10
100
1000
10000
100000
1000000
1 5 10 25 50 75 100 150 200
radix heap
array heap
buffer tree
Del_Min: Zufällige Folge
*106
Literatur
Andreas Crauser: LEDA-SM: External Memory Algorithms and Data
Structures in Theory and Praxis. Dissertation, Max-Planck-Institut für
Informatik, Saarbrücken, 2001. Kapitel 4: Priority Queues;
http://www.mpi-sb.mpg.de/~crauser/degrees.html
Klaus Brengel, Andreas Crauser, Paolo Ferragina, Ulrich Meyer: An
Experimental Study of Priority Queues in External Memory, Proc. of
the Workshop on Algorithmic Engineering (WAE ´99), Lecture Notes in
Computer Science 1668, 345-359, Springer-Verlag, 1999
Die Vorlesung hält sich eng an:
Vielen Dank
