Grundlagen der Algorithmen und Datenstrukturen Kapitel 2seidl/Courses/SS2009/gad-2.pdf · 1 3 10 14 19 insert(5) 1 3 5 10 14 19 remove(14) 1 3 5 10 19. 02.04.09 Kapitel 3 44 >) 2

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


• 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


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


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


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


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


Einfache Verwaltung:

durch „Dummy“-Element mit Inhalt null:

Anfangs:

e1?

…e2 en

?

02.04.09 Kapitel 3 27


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


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


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


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


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


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


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


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


• 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


Kann man insert und remove besser mit einem Feld realisieren?

• folge Beispiel der Bibliothek!

• verwende Hashtabellen (Kapitel 4)

02.04.09 Kapitel 3 48


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


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


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

Documents

Grundlagen der Algorithmen und Datenstrukturen Kapitel 2seidl/Courses/SS2009/gad-2.pdf · 1 3 10 14 19 insert(5) 1 3 5 10 14 19 remove(14) 1 3 5 10 19. 02.04.09 Kapitel 3 44 >) 2