next up previous contents
Next: Sich selbst organisierende Binary Up: Sich selbst organisierende Datenstrukturen Previous: Motivation

Sich selbst organisierende lineare Listen

Beim sog. ``Wörterbuchproblem`` ist auf möglichst effiziente Weise eine Menge von bis zu n Elementen zu organisieren: Dabei soll die Effizienz der Implementierung bei beliebigen Sequenzen von m Operationen untersucht werden. Die Menge wird als unsortierte Liste dargestellt.


\begin{picture} (115,15) \qbezier(0,11)(10,11)(10,7.4) \put(9.8,7.3){\vector... ...ltiput(70,5)(1,0){18}{\circle*{0.2}} \put(90,5){\vector(1,0){18}}\end{picture}

Operationen:
1.
Access(i) : Suchen des Elements i:
Die Liste wird von Anfang an durchsucht, bis das gesuchte Element gefunden ist. Für das i-te Element betragen die tatsächlichen Kosten i Einheiten.
2.
Insert(i) : Einfügen des Elements i:
Die Liste wird von Anfang an durchsucht, und wenn sie vollständig durchsucht wurde und das Element nicht enthalten ist, so wird es hinten angefügt. Diese erfordet (i+1) Schritte, wenn die Länge der Liste i ist.
3.
Delete(i) : Löschen des Elements i:
Wie bei Access wird die Liste zuerst durchsucht und dann das betreffende Element gelöscht. Diese kostet im Falle des i-ten Elements i Schritte.
Nach Abschluß einer jeden Operation können gewisse Umordnungsschritte stattfinden, die spätere Operationen beschleunigen.

Annahme: Wir nehmen an, daß nach Ausführung jeder Access - oder Insert -Operation, die auf Element i angewandt wird, dieses Element kostenlos um beliebig viele Positionen in Richtung Listenanfang geschoben werden kann. Wir nennen jede daran beteiligte Elementenvertauschung einen kostenlosen Tausch. Jeder andere Tausch zweier Elemente ist ein bezahlter Tausch und kostet eine Zeiteinheit.

Ziel: Es soll eine einfache Regel gefunden werden, durch die mittels obiger Vertauschungen die Liste so organisiert wird, daß die Gesamtkosten einer Folge von Operationen minimiert werden. Wir sprechen von ``selbstorganisierenden linearen Listen`` und untersuchen hierzu folgende Regeln: Bemerkung:
-
Die MFR erlaubt die Ausführung einer Sequenz von Operationen Access ,

Insert und Delete mit einer amortisierten Laufzeit, die um höchstens den konstanten Faktor 2 schlechter ist als ein optimaler Listenalgorithmus.

-
Für die TR dagegen gibt es keinen solchen konstanten Faktor. Sie kann verglichen mit MTR bzw. einem optimalen Algorithmus beliebig schlecht sein.
Für die Algorithmen nehmen wir an:
1.
Kosten für Access(xi) und Delete(xi) sind gleich der Position von xi in der Liste (von Anfang an gezählt).
2.
Kosten für Insert(x) (x nicht in Liste) ist der Länge der Liste nach der Insert -Operation (d.h. neue Elemente werden zunächst an Listenende) angehängt
3.
Ein Algorithmus kann die Liste jederzeit umorganisieren (die Reihenfolge ändern).
(a)
kostenlose Vertauschung: nach einer Access(x) - oder Insert(x) -Operation kann x beliebig näher an den Anfang der Liste verschoben werden.
(b)
bezahlte Vertauschung: jede andere Vertauschung benachbarter Listenelemente kostet eine Einheit.
Bemerkung: MFR (und auch Transpose) benutzen nur kostenlose Vertauschungen. 3a ist pessimistisch für MFR.

\fbox {\parbox[c]{12.45cm}{\textbf{Satz:} Sei $s$\space eine beliebige Folge von... ...t{A}}(s) + \text{X}_{\text{A}}(s) - \text{F}_{\text{A}}(s) - m$ \end{center}}}


Beweis: Potentialfunktion: $L_{\text{A}}$ bzw. $L_{\text{MFR}}$ seien die Listen, A bzw. MFR (führt bei Eingabesequenz s) sind die Algorithmen.
Potential := Anzahl der Inversionen in $L_{\text{MFR}}$ im Vergleich zu $L_{\text{A}}$
D.h. sei o.B.d.A. $L_{\text{A}} = (x_1,x_2,\dots,x_n)$.
Dann ist die Potential:

\begin{displaymath} bal(L_{\text{MFR}},L_{\text{A}}) = \sum_{j=1}^n \vert \{\ i\... ...j \text{ ist in } L_{\text{MFR}} \text{ vor } x_i \} \vert \ \ \end{displaymath}




Wir betrachten im folgenden Insert(x) als ein Access auf ein (fiktives) (n+1)-tes Element. Eine Operation ( Access(xi) bzw. Delete(xi) ) kostet für A dann i Einheiten und für MFR t Einheiten, wobei t die Position von xi in $L_{\text{MFR}}$ ist.
i)
A ändert (bei Access bzw. Delete ) $L_{\text{A}}$ in kanonischer Weise. Für Element xi sind die Kosten i-Einheiten.
ii)
Die amortisierten Kosten einer Operation ( Access(xi) oder Delete(xi) ) für MFR sind $\leq 2i-1$

\includegraphics {eps/1_ws99_T1.eps} 

Sei k die Anzahl der Elemente (wie xj), j>i, die im $L_{\text{MFR}}$ vor xi stehen.
t ist die Position xi im $L_{\text{MFR}}$: 
  $t\leq i+k$ ; $\Rightarrow k\geq t-i$  $\Delta bal \leq -k + (i-1) \leq i-t + i -1 \leq 2i-1-t$ (bei    Access)
  $\Delta bal = -k \leq i-t$ (bei    Delete)
 
Amortisierte Kosten $\leq t+ \Delta bal \leq 2i-1$.

iii)
Die amortisierten Kosten einer kostenlosen Vertauschung durch Algorithmus A sind $\leq -1$
\includegraphics {eps/1_ws99_T2.eps}

iv)
Die amortisierten Kosten einer bezahlten Vertauschung durch Algorithmus A sind $\leq 1$
\includegraphics {eps/1_ws99_T3.eps}
Anfangspotential : 0
$\Rightarrow \text{C}_{\text{MFR}}(s) \leq \text{amort. Kosten MFR } \leq 2 \cdot \text{C}_{\text{A}}(s) + \text{X}_{\text{A}}(s) - \text{F}_{\text{A}}(s) - m$
$\Diamond$

Anmerkung: Wenn wir nicht mit einer leeren Liste (oder zwei identischen Listen, d.h. L$_{\text{A}} = \text{L}_{\text{MFR}}$) starten, ergibt sich:
$\text{C}_{\text{MFR}} \leq 2 \text{C}_{\text{A}}(s) + \text{X}_{\text{A}}(s) - \text{F}_{\text{A}}(s) - m + n^2$

Literatur:
Sleator, D.R., Tarjan: Amortized efficiency of list update and paging rules. Comm. ACM 28(2), p. 202-208 (1985).


 
next up previous contents
Next: Sich selbst organisierende Binary Up: Sich selbst organisierende Datenstrukturen Previous: Motivation
Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999