Container

Abstrakte Datentypen

Bei einem abstrakten Datentyp wird die Datenstruktur definiert, indem man die Menge der erlaubten Operationen und deren Bedeutung in abstrakter Form (d.h. unabhängig von einer bestimmten Implementation) angibt. Dazu verwendet man im allgemeinen die algebraische Spezifikation, die zunächst die Operationen auflistet und danach deren Eigenschaften in Form von Axiomen beschreibt, die nach der Ausführung einer Operation jeweils gelten müssen.

Wir unterscheiden folgende Arten von Operationen:

1. Observer: geben Informationen über den Zustand eines Objekts
2. Modifier:
   beim funktionalen Programmierstil: erzeugen ein neues, verändertes Objekt
   beim prozeduralen und objekt-orientierten Programmierstil: verändern ein vorhandenes Objekt
3. Konstruktoren: erzeugen ein neues Objekt (bei funktionaler Programmierung sind Konstruktoren nur ein Spezialfall der Modifier).

Wird ein Objekt a modifiziert, ist sein alter Wert in der Spezifikation unter dem formalen Namen a_old zugreifbar. Dies ermöglicht es, in den Axiomen den alten mit dem neuen Zustand zu vergleichen.

Im folgenden beschreiben wir die algebraische Spezifikation am Beispiel der Container-Datenstrukturen. Container dienen, wie in der Schifffahrt, zum Aufbewahren anderer Datenobjekte und sind damit grundlegend für die Programmierung.

Array

In einem Array erhalten alle Elemente einen Index, d.h. eine nicht-negative laufende Nummer, die bei Null ("zero-based indexing", z.B. C++, Python) oder bei Eins ("one-based indexing", z.B. Fortran, Matlab) startet. Auf die Elemente des Arrays wird zugegriffen, indem man den jeweiligen Index angibt. Wir definieren das Array hier mit zero-based indexing.

Seien a ∈ Array, i ∈ <math>\mathbb{N}_0</math> (ein nicht-negativer Index) und v ∈ Object (ein beliebiges Objekt).

Operationen:

erzeuge ein neues Array:	new_array(size ∈ <math>\mathbb{N}_0</math>, initial ∈ Object) → Array
erfrage die Anzahl der Arrayelemente:	len(a) → <math>\mathbb{N}_0</math>
erfrage das Element beim Index i:	get(a, i) → Object
setze das Objekt beim Index i:	set(a, i, v) → Array

Axiome:

Ein neues Array enthält so viele Elemente, wie in size angegeben waren. Alle Elemente haben den gegebenen Initialwert initial.	a = new_array(size, initial) assert(len(a) == size) für alle i ∈ 0, ..., size-1 gilt:    assert(get(a, i) == initial)
Nach der Zuweisung von v beim Index i gilt: (i) die Größe bleibt unverändert, (ii) Index i enthält das Element v, (iii) die übrigen Elemente haben sich nicht verändert.	a = set(a, i, v) assert(len(a) == len(aold)) assert(get(a, i) == v) für alle k ≠ i gilt:    assert(get(a, k) == get(aold, k))

in Python:

Der Array-Typ heißt list (aus historischen Gründen, das hat nichts mit verketteten Listen zu tun):

• get und set heißen __getitem__ bzw. __setitem__
• rufe Funktionen mit Punktsyntax auf:
  statt get(a, i) schreibe a.__getitem__(i)
• Indexschreibweise:
  v = a[i] ist äquivalent zu v = a.__getitem__(i)
  a[i] = v ist äquivalent zu a.__setitem__(i, v)
• Konstruktoren:
  a = list() ist äquivalent zu a = [] und entspricht a = new_array(0, 0) (erzeugt ein leeres Array)
  a = [initial]*size entspricht a = new_array(size, initial) (erzeugt ein Array der gewünschten Größe mit Initialwert)
  

a = [1, 3, 2, 0, 5] initialisiert ein Array mit den gegebenen Elementen.

Stack

Ein Stack verhält sich wie ein Stapel (z.B. von Büchern oder Bierkästen) in der realen Welt: nur das jeweils oberste Element ist einfach zugänglich (Funktion top), die darunterliegenden sind blockiert. Ein neues Element wird immer oben auf den Stapel gelegt (Funktion push), und das zuletzt eingefügte Element wird als erstes wieder entfernt (Funktion pop). Dies bezeichnet man als "last in - first out"-Verhalten (LIFO).

Seien s ∈ Stack und v ∈ Object (ein beliebiges Objekt).

Operationen:

erzeuge einen leeren Stack:	new_stack() → Stack
erfrage die Anzahl der Stackelemente:	len(s) → <math>\mathbb{N}_0</math>
hänge ein neues Element am Ende an:	push(s, v) → Stack
erfrage das letzte Element:	top(s) → Object
entferne das letzte Element:	pop(s) → Stack

Axiome:

Ein neuer Stack ist leer.	s = new_stack() assert(len(s) == 0)
Nach einem push gilt: (i) die Größe hat sich um eins erhöht, (ii) das gerade eingefügte Element ist jetzt das letzte.	s = push(s, v) assert(len(s) == len(sold)+1) assert(top(s) == v)
push gefolgt von pop reproduziert den Stack vor dem push.	s = pop(push(s, v)) assert(s == sold)

in Python:

Der Typ list ist gleichzeitig ein Stack:

• push(s, v) heißt s.append(v)
• pop(s) heißt s.pop()
• top(s) heißt s[-1] (Python unterstützt negative Indizes i und interpretiert sie als s[len(s)-abs(i)], hier also s[len(s)-1])

Queue

Ein Queue realisiert das Verhalten einer Warteschlange (wie z.B. im Supermarkt): das aktuell vorderste Element ist einfach zugänglich (Funktion first), die dahinterliegenden sind blockiert. Ein neues Element wird immer am Ende der Queue angefügt (Funktion push), und das zuerst eingefügte Element wird als erstes wieder entfernt (Funktion popFirst). Dies bezeichnet man als "first in - first out"-Verhalten (FIFO).

Seien q ∈ Queue und v ∈ Object (ein beliebiges Objekt).

Operationen:

erzeuge eine leere Queue:	new_queue() → Queue
erfrage die Anzahl der Queueelemente:	len(q) → <math>\mathbb{N}_0</math>
hänge ein neues Element am Ende an:	push(q, v) → Queue
erfrage das erste Element:	first(q) → Object
entferne das erste Element:	pop(q) → Queue

Axiome:

Um die Axiome der Queue zu formulieren, brauchen wir zusätzlich die Zugriffsfunktion get des Arrays. Die Queue muss diese Funktion aber nur zum Testen und Debuggen unterstützen, beim Normalbetrieb ist sie nicht notwendig.

Eine neue Queue ist leer.	q = new_queue() assert(len(q) == 0)
Nach einem push gilt: (i) die Größe hat sich um eins erhöht, (ii) das gerade eingefügte Element ist jetzt das letzte, (iii) die übrigen Elemente haben sich nicht verändert.	q = push(q, v) assert(len(q) == len(qold)+1) assert(get(q, len(q)-1) == v) für alle k ∈ 0, ..., len(q)-2 gilt:    assert(get(q, k) == get(qold, k))
Wenn die Queue nicht leer ist, hat das erste Element den Index 0.	assert(len(q) > 0) assert(first(q) == get(q, 0))
Nach einem popFirst gilt: (i) die Größe hat sich um eins verringert, (ii) alle Elemente ab dem zweiten rücken einen Index nach vorn.	q = popFirst(q) assert(len(q) == len(qold)-1) für alle k ∈ 0, ..., len(q)-1 gilt:    assert(get(q, k) == get(qold, k+1))

in Python:

Der Typ list ist gleichzeitig eine Queue:

• push(q, v) heißt q.append(v)
• popFirst(q) heißt q.pop(0) oder del q[0] (Mit beiden Funktionen kann man allgemein das Element bei einem beliebigen Index entfernen.)
• first(q) heißt q[0]

Allerdings ist es nicht sehr effizient, das erste Element aus einem list-Objekt zu entfernen. Eine effizientere Implementation der Queue-Funktionalität bietet der Type deque aus dem Modul collections, der sowohl für das Queue-Verhalten (FIFO) als auch das Stack-Verhalten (LIFO) effizient ist (deque ist die Abkürzung für "double-ended queue").

Assoziatives Array

Ein assoziatives Array erweitert die Array-Funktionalität, indem es statt der Indizes beliebige Schlüssel unterstützt, unter denen die Elemente abgerufen werden. Typische Schlüssel sind z.B. Zahlen, die keine laufende Nummer bilden (z.B. Matrikelnummern), Strings (z.B. Namen). Auf die Elemente des assoziativen Arrays wird zugegriffen, indem man den jeweiligen Schlüsselwert angibt. Assoziative Array werden häufig auch als dictionaries bezeichnet.

Seien d ∈ Dictionary, i ∈ Object (ein Schlüsselobjekt), v ∈ Object (ein beliebiges Objekt) und error ∈ Error (ein Objekt, das einen Fehler signalisiert).

Operationen:

erzeuge ein neues Dictionary:	new_dictionary() → Dictionary
erfrage die Anzahl der Elemente:	len(d) → <math>\mathbb{N}_0</math>
erfrage die zur Zeit gültigen Schlüssel:	keys(d) → Array
teste, ob der angegebene Schlüssel gültig ist:	has_key(d, i) → Boolean
erfrage das Element zum Schlüssel i:	get(d, i) → Object
setze das Objekt zum Schlüssel i:	set(d, i, v) → Dictionary
lösche den Schlüssel i und das zugehörige Objekt:	del_key(d, i) → Dictionary

Axiome:

Ein neues Dictionary ist leer, ebenso die Liste seiner Schlüssel.	d = new_dictionary() assert(len(d) == 0) assert(len(keys(d)) == 0)
Es gilt stets: alle Elemente im Array keys sind tatsächlich Schlüssel.	k = keys(d) für alle j ∈ k gilt:    assert(has_key(d, j))
Wenn i kein Schlüssel ist, gilt: (i) has_key liefert false, (ii) Zugriffe mit get und del_key signalisieren einen Fehler.	assert(not has_key(d, i)) assert(get(d, i) == error) assert(del_key(d, i) == error)
Wenn i kein Schlüssel ist, gilt nach der Zuweisung von v an den Schlüssel i: (i) die Größe erhöht sich um eins, (ii) i ist jetzt Schlüssel und enthält das Element v, (iii) die übrigen Schlüssel und Elemente haben sich nicht verändert.	assert(not has_key(d, i)) d = set(d, i, v) assert(len(d) == len(dold)+1) assert(has_key(d, i)) assert(get(d, i) == v) für alle j ∈ keys(dold) gilt:    assert(get(d, j) == get(dold, j))
Wenn i bereits Schlüssel ist, gilt nach der Zuweisung von v an den Schlüssel i: (i) die Größe bleibt unverändert, (ii) Schlüssel i enthält das Element v, (iii) die übrigen Schlüssel und Elemente haben sich nicht verändert.	assert(has_key(d, i)) d = set(d, i, v) assert(len(d) == len(dold)) assert(get(d, i) == v) assert(keys(d) == keys(dold)) für alle j ∈ keys(d), j ≠ i gilt:    assert(get(d, j) == get(dold, j))
Wenn i ein Schlüssel ist, gilt nach dem Löschen von i: (i) die Größe verringert sich um eins, (ii) der Schlüssel ist nicht mehr vorhanden, (iii) die übrigen Schlüssel und Elemente bleiben unverändert.	assert(has_key(d, i) d = del_key(d, i) assert(len(d) == len(dold)-1) assert(not has_key(d, i)) für alle j ∈ keys(d) gilt:    assert(get(d, j) == get(dold, j))

in Python:

Der Dictionary-Typ heißt dict:

• rufe Funktionen mit Punktsyntax auf:
  statt has_key(d, i) schreibe d.has_key(i) etc.
• get und set heißen __getitem__ bzw. __setitem__
• get ist ebenfalls implementiert, aber es signalisiert keinen Fehler, wenn der Schlüssel unbekannt ist, sondern gibt ein Defaultobjekt zurück (siehe Dokumentation für Einzelheiten)
• del_key(d, i) heißt d.pop(i) oder del d[i]
• d.keys() liefert ab Python 3 kein Array, sondern ein iterable, siehe Dokumentation
• Indexschreibweise:
  v = d[i] ist äquivalent zu v = d.__getitem__(i)
  d[i] = v ist äquivalent zu d.__setitem__(i, v)
• Konstruktoren:
  d = dict() ist äquivalent zu d = {} und entspricht d = new_dictionary(): erzeugt ein leeres Dictionary
  d = {'eins': 1, 'zwei': 2, 'drei': 3} initialisiert ein Dictionary mit den angegebenen Schlüssel/Wert-Paaren (die Schlüssel sind hier Strings, die Werte Zahlen).

Mögliche Operationen

Welche Operationen hätte man denn gerne bei einer solchen Container-Datenstruktur? Was benötigen Algorithmen häufig? Wie sollten die Daten organisiert sein, damit Algorithmen effizient damit arbeiten können?
Eine solche Anforderungsanalyse ist sehr aufwendig und kann sich über Jahre erstrecken, weil Erfahrungen gesammelt werden müssen, welche Anforderungen an Datenstrukturen in vielen Algorithmen immer wieder auftreten.
Wir listen im folgenden nur das Resultat, also die wichtigsten Operationen von Container-Datenstrukturen auf.

Sei c eine Container-Datenstruktur und v ein darin gespeicherter Wert:

Lesender Zugriff

0.	c.size()	gibt die Anzahl der Elemente im Container an
1a.	v = c.get(i)	das i-te Element im Container lesen
1b.	v = c.get(pos)	das Element an Position pos lesen (pos ist ein geeignetes Hilfsobjekt, das in Abhängigkeit von der Art der Datenstruktur eine Position im Container referenziert. Im Falle 1a. v = c.get(i) ist pos eine natürliche Zahl, aber es gibt auch andere Möglichkeiten, die Position zu kodieren.)
1c.	v = c.get(key)	das Element mit dem Schlüssel key lesen (Beachte den Unterschied zu 1b: In 1b markiert pos eine Position im Container, hier in 1c bezieht sich key auf eine Eigenschaft der Datenelemente, die von der Position im Container unabhängig ist.)
2a.	v = c.first()	erstes Element lesen (äquivalent zu v = c.get(0))
2b.	v = c.last()	letztes Element lesen (äquivalent zu v = c.get(c.size()-1))
3a.	v = c.smallest()	das kleinste Element lesen (dies bezieht sich auf eine Eigenschaft der Datenelemente bzw. Schlüssel, im Unterschied zu 2a, wo es um die Position im Container geht.)
3b.	v = c.largest()	das größte Element lesen (dies bezieht sich auf eine Eigenschaft der Datenelemente bzw. Schlüssel, im Unterschied zu 2b, wo es um die Position im Container geht.)

Schreibender Zugriff

4a.	v.set(i, v)	i-tes Element überschreiben (c.size() bleibt unverändert)
4b.	v.set(pos, v)	Element an der Stelle pos überschreiben (c.size() bleibt unverändert. Zur Bedeutung von pos siehe 1b.)
4c.	v.set(key, v)	Element mit dem Schlüssel key überschreiben (c.size() bleibt unverändert)
5a.	c.insert(i, v)	Objekt als i-tes in den Container einfügen (Werte ab i werden eine Position nach hinten verschoben, c.size() erhöht sich um 1)
5b.	c.insert(pos, v)	Objekt an Position pos in den Container einfügen (Werte ab pos werden eine Position nach hinten verschoben, c.size() erhöht sich um 1)
5c.	c.insert(key, v)	Objekt unter dem Schlüssel key in den Container einfügen (Wenn der Schlüssel schon vergeben war, wird ein Fehler signalisiert. c.size() erhöht sich um 1).
5d.	c.insert(v)	Objekt an beliebiger Stelle in den Container einfügen (Der Container bestimmt die optimale Position selbst. c.size() erhöht sich um 1).
6a.	c.prepend(v)	Objekt am Anfang einfügen (äquivalent zu c.insert(0, v), c.size() erhöht sich um 1)
6b.	c.append(v)	Objekt am Ende anhängen (äquivalent zu c.insert(c.size(), v), c.size() erhöht sich um 1)
7a.	c.remove(i)	i-tes Element aus dem Container löschen (Werte ab i werden eine Position nach vorn verschoben, c.size() verringert sich um 1)
7b.	c.remove(pos)	Objekt an Position pos aus dem Container löschen (Werte ab pos werden eine Position nach vorn verschoben, c.size() verringert sich um 1)
7c.	c.remove(key)	Objekt unter dem Schlüssel key aus dem Container löschen (Wenn der Schlüssel nicht vergeben war, wird ein Fehler signalisiert. c.size() verringert sich um 1, wenn es kein Fehler signalisiert hat.)
8a.	c.removeFirst()	das erste Element aus dem Container entfernen (äquivalent zu c.remove(0), c.size() verringert sich um 1)
8b.	c.removeLast()	das letzte Element aus dem Container entfernen (äquivalent zu c.remove(c.size()-1), c.size() verringert sich um 1)
9a.	c.removeSmallest()	das kleinste Element aus dem Container entfernen (dies bezieht sich auf eine Eigenschaft der Datenelemente bzw. Schlüssel, im Unterschied zu 8a, wo es um die Position im Container geht. c.size() verringert sich um 1)
9b.	c.removeLargest()	das größte Element aus dem Container entfernen (dies bezieht sich auf eine Eigenschaft der Datenelemente bzw. Schlüssel, im Unterschied zu 8b, wo es um die Position im Container geht. c.size() verringert sich um 1)

Facts

• Jede dieser Operationen kann sehr effizient implementiert werden.
• Keine Datenstruktur ist bekannt, die alle diese Operationen effizient implementiert.

Beispiele

Je nachdem welche Operation effizient sein soll, wird eine andere Container Datenstruktur ausgewählt. Die Operation c.size() wird von allen Containern effizient unterstützt.

Arrays

(statisches) Array [1]

Das Array ist die einfachste Datenstruktur, es kann einfach als aufeinanderfolgender Bereich von Speicherzellen implementiert werden. Jede dieser Speicherzellen nimmt ein Objekt als Datenelement auf. Die Größe ist nicht veränderbar (daher der Name statisch).
Das statische Array unterstützt die Operationen

   1a.    c.get(i)
   4a.    c.set(i, value)

Dynamisches Array [2]

Die Größe ist veränderbar, aber nur durch Anfügen oder Entfernen eines Elements am Ende des Arrays. Die unterstützen Operationen sind dieselben wie die des statischen Arrays, zusätzlich unterstützt das dynamische Array die Operationen

   6b.    c.append(v)
   8b.    c.removeLast()

Wir beschreiben im Abschnitt Amortisierte Komplexität, wie man dies effizient implementieren kann. Das Anfügen neuer Elemente am Ende ist eine sehr häufige Operation, so dass das dynamische Array eine der beliebtesten Datenstrukturen ist. In Python hat das dynamische Array den Typ list, was in diesem Fall nichts mit verketten Listen zu tun hat, sondern eher auf Listen im Sinne von Tabellen hinweist (die Namenswahl ist dennoch etwas unglücklich und kann zu Verwechslungen führen).

assoziatives Array (Dictionary) [3]

Ein Dictionary verallgemeinert das dynamische Array: Während Arrays auf ihre Elemente über Indizes (= natürliche Zahlen) zugreifen, können die Schlüssel (Keys) bei einem Dictionary einen beliebigen Typ haben. Jedes Element des Dictionary besteht aus einem Schlüssel-Wert-Paar, jeder Schlüssel bekommt somit einen Wert zugewiesen.
Das Dictionary unterstützt die Operationen

   1c.    c.get(key)
   4c.    c.set(key, value)
   5c.    c.insert(key, value)
   7c.    c.remove(key)

Wenn als Schlüssel natürliche Zahlen 0, 1, ..., N gewählt werden, sind dies im wesentlichen dieselben Operationen wie beim Array. Man wird das Dictionary also vor allem dann einsetzen, wenn die Schlüssel einen anderen Typ haben, oder wenn die Zahlen nicht aus dem zusammenhängenden Intervall 0, ..., N kommen. Das Python-Dictionary hat den Typ dict. Wir behandeln diese Datenstruktur in den Kapiteln Assoziative Arrays und Hashing und Hashtabellen.

verkettete Listen

(einfach) verkettete Liste [4]

Im Gegensatz zum Array müssen die Speicherzellen nicht nacheinenander im Speicher abgelegt sein. Statt dessen enthält jedes Element der Liste ein Feld next, das auf das nächste Element der Liste verweist. Um das i-te Element zu finden, muss man die Liste von vorn nach hinten durchlaufen. Deshalb ist die Operation c.get(i) für verkettete Listen nicht effizient. Wenn man allerdings auf ein Element zugegriffen hat, kann man ein pos-Objekt (in diesem Fall eine Referenz auf das Element) speichern, so dass ein erneuter Zugriff auf das selbe Element schnell geht. Das gleiche gilt für das folgende Element, weil man nur einmal pos = pos.next aufrufen muss. Nur wenig komplizierter (und dadurch ebenfalls effizient) ist das Einfügen eines neuen Elements an der Position pos.
Die verkette Liste unterstützt somit die Operationen:

   1b.    c.get(pos)
   2a.    c.first()
   4b.    c.set(pos, value)
   5b.    c.insert(pos, value)
   6a.    c.prepend(value)
   7b.    c.remove(pos)
   8a.    c.removeFirst(pos)

Es scheint, dass die Liste eine sehr flexible Datenstruktur ist. Allerdings ist es ein gravierender Nachteil, dass pos nur auf das jeweils nächste Element weitergesetzt werden kann. Im Gegensatz dazu können Indizes in einem Array effizient auf beliebige Positionen gesetzt werden. Man bevorzugt deshalb heute dynamische Arrays.

Doppelt verkettete Liste [5]

Im Gegensatz zur einfach verketteten Liste enthält jedes Element nicht nur einen Zeiger auf das darauffolgende, sondern auch auf das vorherige Element in der Liste. Dadurch kann ein pos-Objekt auch effizient um ein Element zurückgesetzt werden: pos = pos.previous.
Die doppelt verkette Liste unterstützt deshalb die selben Operationen wie die einfach verkettete, und zusätzlich

   2b.    c.last()
   6b.    c.append(value)
   8b.    c.removeLast()

Queues

Stack (Stapelspeicher) [6]

Speichert/Stapelt die Objekte mit push in einen Speicher. Wiederrum mit pop kann das oberste (=zuletzt eingefügte) Element herausgeholt werden: LIFO (Last In First Out)
Die Python-Datenstruktur List eignet sich beispielsweise als Stack.
Operationen:

   2b.    c.last()         # auf das oberste Element zugreifen, ohne es zu entfernen
   6b.    c.append(value)  # Element auf den Stapel legen (beim Stack meist c.push(value) genannt)
   8b.    c.removeLast()   # oberstes Element entfernen (beim Stack meist c.pop() genannt)

Queue (Schlange) [7]

Eine Queue ist wie eine Warteschlange an der Kasse im Supermarkt, bedient wird derjenige der als erster an die Kasse kommt: FIFO (First In First Out)
Operationen:

   2a.    c.first()
   6b.    c.append(value)
   8a.    c.removeFirst()

Deque (Double Ended Queue) [8]

wie Stack + Queue, d.h. Objekte können am Ende eingefügt, aber sowohl vorn als auch hinten gelesen und entfernt werden.
Operationen

   2a.    c.first()
   2b.    c.last()
   6b.    c.append(value)
   8a.    c.removeFirst()
   8b.    c.removeLast()

Die Deque ist Thema in Übungsblatt 3.

Prioritätswarteschlangen

MinPriorityQueue [9]

Warteschlange, die das Element mit der kleinsten Priorität zuerst zurückgibt (z.B. an der Kasse im Supermarkt diejenige/derjenige, die/der die wenigsten Produkte kaufen möchte)
Mögliche Operationen:

   3a.    c.smallest()
   5d.    c.insert(value)
   9a.    c.removeSmallest()

MaxPriorityQueue [10]

Warteschlange, die das Element mit der größten Priorität zuerst zurückgibt
Unterstützte Operationen sind:

   3b.    c.largest()
   5d.    c.insert(value)
   9b.    c.removeLargest()

MinMaxPriorityQueue [11]

kombiniert MinPriorityQueue + MaxPriorityQueue

Die drei letzten Datenstrukturen behandeln wir im Kapitel Prioritätswarteschlangen.

Container in Python

under construction

Nächstes Thema