Beschränkte Felder (Bounded Arrays) Unbeschränkte Felder

Felder (Arrays)
A[ i ] = a i
falls
A = ha0 , . . . , an−1 i
Beschränkte Felder (Bounded Arrays)
Eingebaute Datenstruktur: Ein Stück Hauptspeicher
+
Adressrechnung
Gröÿe muss von Anfang an bekannt sein
Unbeschränkte Felder (Unbounded Arrays)
he0 , . . . , en i.pushBack(e)
he0 , . . . , en , e i,
he0 , . . . , en i.popBack
he0 , . . . , en−1 i,
e
size(h 0 , . . . ,
en−1 i) = n .
108
Unbeschränkte Felder Anwendungen
wenn man nicht weiÿ, wie lang das Feld wird.
Beispiele:
I Datei zeilenweise einlesen
I später: Stacks, Queues, Prioritätslisten, . . .
109
Unbeschränkte Felder Grundidee
wie beschränkte Felder: Ein Stück Hauptspeicher
pushBack: Element anhängen, size + +
Kein Platz?: umkopieren und (gröÿer) neu anlegen
popBack: size − −
Zuviel Platz?: umkopieren und (kleiner) neu anlegen
Immer passender Platzverbrauch?
n
pushBack Operationen brauchen Zeit
O(∑ni=1 i ) = O n2
Geht es schneller?
110
Unbeschränkte Felder
mit teilweise ungenutztem Speicher
Class
UArray
w =1 : N
n=0 : N
of
Element
invariant n ≤ w < α n or n = 0 and w ≤ 2
b : Array [0..w − 1] of Element
n
w
···
// b → e0 · · · en−1
Operator [i : N] : Element
assert 0 ≤ i < n
return b[i ]
Function size : N return n
// allocated size
// current size
// e.g., α = 4
111
Procedure pushBack(e : Element)
if n = w then
reallocate(2
b[n]:= e
n++
Procedure
w0
n)
Array [0..w 0 − 1] of
(b0 [0], . . . , b0 [n − 1]):=
(b[0], . . . , b[n − 1])
dispose b
b:= b0
// Example for w = 4, w 0 = 8:
// b → 0 1 2 3
w 0 : N)
reallocate(
w :=
b0 := allocate
// Example for n = w = 4:
// b → 0 1 2 3
// b → 0 1 2 3
// b → 0 1 2 3 e
// b → 0 1 2 3 e
Element
// b0 →
// b0 → 0 1 2 3
// b → 0 1 2 3
// pointer assignment b → 0 1 2 3
112
Kürzen
Procedure popBack
assert n > 0
// Example for n = 5, w = 16:
// b → 0 1 2 3 4
n−−
// b → 0 1 2 3 4
if 4n ≤ w ∧ n > 0 then
// reduce waste of space
reallocate(2n )
// b → 0 1 2 3
Was geht schief, wenn man auf passende Gröÿe kürzt?
113
Amortisierte Komplexität unbeschr. Felder
Sei
u
ein anfangs leeres, unbeschränktes Feld.
Jede Operationenfolge
σ = hσ1 , . . . , σm i
von pushBack oder popBack Operationen auf
wird in Zeit
O(m)
u
ausgeführt.
Sprechweise:
pushBack und popBack haben amortisiert konstante Ausführungszeit 

Gesamtzeit
z}|{
m  = O(1) .
O c · m / |{z}
#Ops
114
Beweis: Konto-Methode (oder Versicherung)
Operation
Kosten
pushBack
◦◦
◦
n×◦
popBack
reallocate(2
n)
Typ
(2 Token)
einzahlen
(1 Token)
einzahlen
n
(
Token)
abheben
Zu zeigen: keine Überziehungen
Erster Aufruf von reallocate: kein Problem
(
n = 2, ≥
2tes pushBack)
115
Beweis: Konto-Methode (oder Versicherung)
Operation
Kosten
pushBack
◦◦
◦
n×◦
popBack
reallocate(2
n)
Typ
(2 Token)
einzahlen
(1 Token)
einzahlen
n
(
Token)
abheben
Weitere Aufrufe von reallocate:
rauf: reallocate(2
runter: reallocate(2
≥n×pushBack
n) |
{z
≥n×◦◦
} reallocate(4n)
≥n/2×popBack
n) |
{z
≥n/2×◦
} reallocate(n)
116
Amortisierte Analyse allgemeiner
I
I
I
I
O:
Menge von Operationen, z. B.
{pushBack, popBack}
s (für state): Zustand der Datenstruktur
AOp (s ): amortisierte Kosten von Operation Op ∈ O
TOp (s ): tatsächliche Kosten von Operation Op ∈ O
I Berechnung: s0
Op
Op
Op
s
Zustand s
in Zustand
in
Op
−→1 s1 −→2 s2 −→3 · · · −→n sn
Die angenommenen amortisierten Kosten sind korrekt, wenn
∑
1≤i ≤n
|
TOpi (si −1 )
{z
}
tatsächliche Gesamtkosten
für eine Konstante
≤c+
∑
1≤i ≤n
|
AOpi (si −1 )
{z
}
amortisierte Gesamtkosten
c
117
Amortisierte Analyse Diskussion
I Amortisierte Laufzeiten sind leichter zu garantieren als
tatsächliche.
I Der Gesamtlaufzeit tut das keinen Abbruch.
I Deamortisierung oft möglich, aber kompliziert und teuer
I
I
I
Wie geht das mit unbeschränkten Feldern?
Anwendung: Echtzeitsysteme
Anwendung: Parallelverarbeitung
118

Download Report