Post on 18-Oct-2020
transcript
02.04.09 Kapitel 3 1
Grundlagen der Algorithmen und Datenstrukturen
Kapitel 2
Christian Scheideler + Helmut Seidl
SS 2009
02.04.09 Kapitel 3 2
Grundlegende Laufzeitanalyse
Eingabe(z.B. unsortierte Liste)
Algorithmus
(z.B. Bubblesort)
Ausgabe(z.B. sortierte Liste)
Eingabe(z.B. Such-Operationen)
Datenstrukturoperationen
(z.B. Move-to-Front)
Ausgabe(z.B. Such-Liste)
Kapitel 3Kapitel 2
02.04.09 Kapitel 3 3
Übersicht
Thema: Repräsentation von Sequenzen als Felder und verkettete Listen
• Was ist eine Sequenz?
• Repräsentation als Feld und amortisierte Analyse
• Repräsentation als verkettete Liste• Stapel (Stacks) und Schlangen (Queues)
02.04.09 Kapitel 3 4
Sequenzen
Sequenz: s = <e0,…,en-1>
Arten, auf Element zuzugreifen:• Feldrepräsentation: direkter Zugriff über s[i]
• Listenrepräsentation: indirekter Zugriff über Nachfolger und/oder Vorgänger (Schnitzeljagd durch Speicher)
s[0]: e0 s[1] s[2] s[3] s[4] s[5] ….
e0 e1
Nachf.
Vorg.e2
Nachf.
Vorg.e3
Nachf.
Vorg.
Nachf.
Vorg.
….s
02.04.09 Kapitel 3 5
Sequenz als Feld
Operationen: <e0,…,en>.get(i) = ei (analog set(i,e))
• <e0,…,en>.pushBack(e) = <e0,…,en,e>
• <e0,…,en>.popBack() = <e0,…,en-1>
• (<e0,…,en-1>).size() = n
e0 e1 e2 … en e ….
e0 e1 e2 … en-1 ….
02.04.09 Kapitel 3 6
Sequenz als Feld
Problem: s sei Feld mit 8 Einträgen
• pushback(1), pushback(5), pushback(2)
• pushback(6): voll!!
8 3 9 7 4andere Daten andere Daten
s-Feld
8 3 9 7 4 1 5 2andere Daten andere Daten
02.04.09 Kapitel 3 7
Sequenz als Feld
Problem:
• Im vornherein nicht bekannt, wieviele Elemente das Feld enthalten wird
• Nur Anlegen von statischen Feldern möglich(s = new Elem [w])
Lösung: Datenstruktur für dynamisches Feld
02.04.09 Kapitel 3 8
3.1 Dynamisches Feld
Erste Idee:
• Jedesmal, wenn Feld s nicht mehr ausreicht (n>w-1), generiere neues Feld der Größe w+c für ein festes c.
s[0] s[1] s[2] s[3] s[w-1]….
s[0] s[1] s[2] s[3] s[w]…. s[w+1] s[w+c-1]….
Neues Feld und Umkopieren
andere Objekte
02.04.09 Kapitel 3 9
Dynamisches Feld
Zeitaufwand für Erweiterung ist O(w):
Zeitaufwand für n pushBack Operationen:• Aufwand von O(w) je c Operationen• Gesamtaufwand: O(∑i=1
n/c c¢ i) = O(n2)
s[0] s[1] s[2] s[3] s[w-1]….
s[0] s[1] s[2] s[3] s[w]…. s[w+1] s[w+c-1]….
Neues allocate und Umkopieren
02.04.09 Kapitel 3 10
Dynamisches Feld
Bessere Idee:• Jedesmal, wenn Feld s nicht mehr ausreicht
(n>w-1), generiere neues Feld der doppelten Größe 2w.
• Jedesmal, wenn Feld s zu groß ist (n<w/4), generiere neues Feld der halben Größe w/2.
s[0] s[1] s[2] s[3] s[w-1]….
s[0] s[1] s[2] s[3] s[w]…. s[w-1] s[2w-1]….
02.04.09 Kapitel 3 11
Dynamisches Feld
Implementierung als Klasse UArray mit
• Methode Element get (int i)
• Methode int size()• Methode void pushBack(Elem e)
• Methode void popBack()
• Methode void increase(int w)
02.04.09 Kapitel 3 12
Dynamisches Feld
Variablen in Klasse UArray:
• β = 2; Wachstumsfaktor
• α = 4; max. Speicheroverhead• w=1; momentane Feldgröße
• n=0; momentane # Elemente
• b = new Elem [w];
b[0] b[1] b[2] b[3] b[w-1]….
02.04.09 Kapitel 3 13
Dynamisches Feld
Elem get (int i) {
assert (0<=i && i<n);
return b[i];
}
int size() {
return n;
}
02.04.09 Kapitel 3 14
Dynamisches Feld
void pushBack(Elem e) {
if (n==w)
reallocate(β ∗n);
b[n]=e;
n=n+1;
}
0 1 2 3b
0 1 2 3b
0 1 2 eb 3
n=w=4:
02.04.09 Kapitel 3 15
Dynamisches Feld
void popBack() {
assert (n>0);
n=n-1;
if (α ∗n<=w && n>0)
reallocate(β ∗n);
}
0 1 2 4b
0 1 2b 3
3
n=5, w=16:
02.04.09 Kapitel 3 16
Dynamisches Feld
void reallocate (int w) {
this.w=w;
Elem [] b0 = new Elem [w];
for (i=0; i<n; i++)
b0[i]=b[i];
b=b0;
}
Umkopieren}
02.04.09 Kapitel 3 17
Dynamisches Feld
Lemma 3.1: Betrachte ein anfangs leeres dynamisches Feld s. Jede Folge σ =<σ 1,…,σ n> von pushBack und popBack Operationen kann auf s in Zeit O(n) bearbeitet werden.
• Erste Idee: Laufzeit O(n2)• Nur durchschnittlich konstante Laufzeit pro
Operation(Fachbegriff für „durchschnittlich“: amortisiert)
02.04.09 Kapitel 3 18
Dynamisches Feld - Analyse
• Feldverdopplung:
• Feldhalbierung:
• Von – Nächste Verdopplung: ≥ n pushBack Ops– Nächste Halbierung: ≥ n/2 popBack Ops
0 1 2 3b 0 1 2 3b
0 1 2 4b 3
0 1 2 3b
02.04.09 Kapitel 3 19
Dynamisches Feld - Analyse
• Von – Nächste Verdopplung: ≥ n pushBack Ops– Nächste Halbierung: ≥ n/2 popBack Ops
• Idee: verrechne reallocate-Kosten mit pushBack/popBack Kosten (ohne realloc)– Kosten für pushBack/popBack: O(1)– Kosten für reallocate(β ∗n): O(n)
0 1 2 3b
02.04.09 Kapitel 3 20
Dynamisches Feld - Analyse
Idee:
verrechne reallocate-Kosten mit pushBack / popBack Kosten
Kontenmethode:
Günstige Operationen zahlen Tokens ein.
Teure Operationen entnehmen Tokens.
Tokenkonto darf nie negativ werden!
02.04.09 Kapitel 3 21
Dynamisches Feld - Analyse
Kontenmethode:
• Günstige Operationen zahlen Tokens ein! pro pushBack 2 Tokens! pro popBack 1 Token
• Teure Operationen entnehmen Tokens! pro reallocate(β ∗n) –n Tokens
• Tokenkonto darf nie negativ werden!! erfüllt über Zeugenargument
02.04.09 Kapitel 3 22
Dynamisches Feld - Analyse
Tokenlaufzeit:• Ausführung von push/popBack kostet 1 Token! Tokenkosten für pushBack: 1+2 = 3! Tokenkosten für popBack: 1+1 = 2
• Ausführung von reallocate(β ∗n) kostet n Tokens! Tokenkosten für reallocate(β ∗n): n-n=0
Gesamtlaufzeit = O(Summe der Tokenlaufzeiten)
pushB pushB pushB pushB reallocate
02.04.09 Kapitel 3 23
Sequenzen
Sequenz: s = <e0,…,en-1>
Arten, auf Element zuzugreifen:• Feldrepräsentation: direkter Zugriff über s[i]
• Listenrepräsentation: indirekter Zugriff über Nachfolger und/oder Vorgänger
s[0]: e0 s[1] s[2] s[3] s[4] s[5] ….
e0 e1
Nachf.
Vorg.e2
Nachf.
Vorg.e3
Nachf.
Vorg.
Nachf.
Vorg.
….s
02.04.09 Kapitel 3 24
Doppelt verkettete Liste
Interne Speicherung (3 Elemente):
Wie Schnitzeljagd im Speicher.
e0 V Ns e1 V Ne2 V N
Variable s speichert Startpunkt der Liste
02.04.09 Kapitel 3 25
Doppelt verkettete Liste
class Item<Elem> { Elem e; Item<Elem> next; Item<Elem> prev;}
class List<Elem> { Item<Elem> h; …weitere Variablen und Methoden…
Invariante: (this: Zeiger auf aktuelles Element)next.prev == prev.next == this
ee e
… …
02.04.09 Kapitel 3 26
Doppelt verkettete Liste
Einfache Verwaltung:
durch „Dummy“-Element mit Inhalt null:
Anfangs:
e1?
…e2 en
?
02.04.09 Kapitel 3 27
Doppelt verkettete Liste
Zentrale statische Methode: splice• splice entfernt <a,…,b> aus Sequenz und
fügt sie hinter einem t an.• Bedingung: <a,…,b> muss eine Teilse-
quenz sein, b ist nicht vor a, und t darf nicht in <a,…,b> stehen.
Für <e1,…,a´,a,…,b,b´,…,t,t‘…,en> liefert
splice (a, b, t) = <e1,…,a´,b´,…,t,a,…,b,t´,…,en>
02.04.09 Kapitel 3 28
Doppelt verkettete Listestatic void splice(Item<Elem> a, Item<Elem> b,Item<Elem> t) { // schneide <a,…,b> heraus Item<Elem> a' = a.prev; Item<Elem> b' = b.next; a'.next = b´; b'.prev = a';
// füge <a,…,b> hinter t ein Item<Elem> t' = t.next; b.next = t'; a.prev = t; t.next = a; t'.prev = b;}
……
……
a´ a b b´
……
t a b t´
……
02.04.09 Kapitel 3 29
Doppelt verkettete Liste
h: Item mit null
Methoden:Item<Elem> head() {
return h;}boolean isEmpty() {
return h.next == h;}Item<Elem> first() {
return h.next;}Item<Elem> last() {
return h.prev;}
e1?…
en
?
Kann evtl. auf ?-Element zeigen!
Kann evtl. auf ?-Element zeigen!
02.04.09 Kapitel 3 30
Doppelt verkettete Liste
h: Item mit null Methoden:
static void moveAfter(Item<Elem> b, Item<Elem> a) {splice(b,b,a);
} // schiebe b nach avoid moveToFront(Item<Elem> b) {
moveAfter(b, head());} // schiebe b nach vorn // analog moveToEnd
e1?…
en
02.04.09 Kapitel 3 31
Doppelt verkettete Liste
Löschen und Einfügen von Elementen:mittels extra Liste freeList
static void remove(Item<Elem b) {moveAfter(b, freeList.head());
}void popFront() {
remove(first());}void popBack() {
remove(last());}
……
h b
…
……
freeList
freeList: gut für Lauf-zeit, da Speicher-allokation teuer
02.04.09 Kapitel 3 32
Doppelt verkettete Listestatic Item<Elem> insertAfter(Elem x, Item<Elem> a){
Item<Elem> a'; if (freeList.isEmpty()) a' = new Item<Elem>();
else a' = freeList.first();moveAfter(a', a);a'.e = x;return a';
}static Item<Elem> insertBefore(Elem e, Item<Elem> b) {
return insertAfter(e, b.prev);}void pushFront(Elem e) {insertAfter(e, head());}void pushBack(Elem e) { insertAfter(e, last()); }
……
h a
…
a´x
02.04.09 Kapitel 3 33
Doppelt verkettete Liste
Manipulation ganzer Listen:
void concat(List<Elem> l) {if (! l.isEmpty()) splice(l.first(), l.last(), last());
}
……
h last
……
l
02.04.09 Kapitel 3 34
Doppelt verkettete Liste
Suche nach einem Element:Trick: verwende „Dummy“-Element
Item<Elem> findNext (Elem x, Item<Elem> from) {h.e = x;while (from.e != x) from = from.next;h.e = null; return from;
}
e1x
…en
02.04.09 Kapitel 3 35
Einfach verkettete Liste
class Sitem <Elem> { Elem e; Sitem<Elem> next;}
class Slist<Elem> { Sitem<Elem> h; …weitere Variablen und Methoden…}
? e e
…
02.04.09 Kapitel 3 36
Einfach verkettete Liste
static void splice(Sitem a', Sitem b, Sitem t) {Sitem a = a'.next;a'.next = b.next;b.next = t.next;t.next = a;
}a´ … b b´a
t t´
02.04.09 Kapitel 3 37
Stacks und Queues
Grundlegende Datenstrukturen für Sequenzen:
• Stack
• FIFO-Queue:
02.04.09 Kapitel 3 38
Stack
Methoden:
• pushBack: <e0,…,en>.pushBack(e) = <e0,…,en,e>
• popBack: <e0,…,en>.popBack() = <e0,…,en-1>
• last: <e0,…,en>.last() = en
Implementierungen auf vorherigen Folien.
02.04.09 Kapitel 3 39
FIFO-Queue
Methoden:
• pushBack: <e0,…,en>.pushBack(e) = <e0,…,en,e>
• popFront: <e0,…,en>.popFront() = <e1,…,en>
• first: <e0,…,en>.first() = e0
Implementierungen auf vorherigen Folien
02.04.09 Kapitel 3 40
Beschränkte FIFO-Queue
class BoundedFIFO <Elem> {Elem[] b;int h=0; // Index des ersten Elementsint t=0; // Index des ersten freien Eintrags
}boolean isEmpty() {
return h == t;}Elem first() {
return b[h];}int size() {
return (t-h+n+1) % (n+1);}
0n 12
3...
h t
b
pop push
02.04.09 Kapitel 3 41
Beschränkte FIFO-Queue
class BoundedFIFO<Elem> {Elem[] b;int h=0; // Index des ersten Elementsint t=0; // Index des ersten freien Eintrags
...void pushBack(Elem x) {
assert (size() < n);b[t] = x;t = (t+1) % (n+1);
}void popFront() {
assert (!isEmpty());h = (h+1) % (n+1);
}
0n 12
3...
h t
b
pop push
02.04.09 Kapitel 3 42
Fazit
• Listen sind sehr flexibel, wenn es darum geht, Elemente in der Mitte einzufügen
• Felder können in konstanter Zeit auf jedes Element zugreifen
• Listen haben kein Reallokationsproblem bei unbeschränkten Größen
! beide Datenstrukturen einfach, aber oft nicht wirklich zufriedenstellend
02.04.09 Kapitel 3 43
Beispiel: Sortierte Sequenz
Problem: bewahre nach jeder Einfügung und Löschung eine sortierte Sequenz
1 3 10 14 19
insert(5)
1 3 10 14 195
remove(14)
1 3 10 195
02.04.09 Kapitel 3 44
Beispiel: Sortierte Sequenz
Warum sortierte Sequenz?
Mit Feld binäre Suche möglich (Kapitel 2).
find(23):
In n-elementiger Folge kann jedes Element
in max. log n Schritten gefunden.
1 15 23 27 31 39 42 55 58 62 84 85 90 91 98
02.04.09 Kapitel 3 45
Beispiel: Sortierte Sequenz
S: sortierte Sequenz
Jedes Element e identifiziert über key(e).
Operationen:
• <e0,…,en>.insert(e) = <e0,…,ei,e,ei+1,…,en>für das i mit key(ei) < key(e) < key(ei+1)
• <e0,…,en>.remove(k) = <e0,…,ei-1,ei+1,…,en> für das i mit key(ei)=k
• <e0,…,en>.find(k) = ei für das i mit key(ei)=k
02.04.09 Kapitel 3 46
Beispiel: Sortierte Sequenz
• Realisierung als Liste:– insert, remove und find auf Sequenz der
Länge n kosten im worst case Θ (n) Zeit
• Realisierung als Feld:– insert und remove kosten im worst case
Θ (n) Zeit– find kann so realisiert werden, dass es im
worst case nur O(log n) Zeit benötigt(! binäre Suche!)
02.04.09 Kapitel 3 47
Beispiel: Sortierte Sequenz
Kann man insert und remove besser mit einem Feld realisieren?
• folge Beispiel der Bibliothek!
• verwende Hashtabellen (Kapitel 4)
02.04.09 Kapitel 3 48
Beispiel: Sortierte Sequenz
Bibliotheksprinzip: lass Lücken!
Angewandt auf sortiertes Feld:
1 3 10 14 19
insert(5)
remove(14)
1 3 5 14 1910
1 3 5 1910
02.04.09 Kapitel 3 49
Beispiel: Sortierte Sequenz
Durch geschickte Verteilung der Lücken:
amortierte Kosten für insert und remove Θ (log2 n)
1 3 10 14 19
insert(5)
remove(14)
1 3 5 14 1910
1 3 5 1910
02.04.09 Kapitel 3 50
Beispiel: Sortierte Sequenz
Insert, delete und find noch viel effizienter
umsetzbar, wie wir sehen werden!
02.04.09 Kapitel 3 51
Nächstes Kapitel
• Wörterbuchproblem
• Hashing
• Statische Wörterbücher• Dynamische Wörterbücher