Container |
sind Datenstrukturen, in denen Elemente oder
Paare von Elementen nach unterschiedlichen Strategien
gespeichert und gelesen werden können.
|
|
|
Set, Bag, List, Map |
sind die wichtigsten ADTs für Container
|
|
|
Persistente Container |
sind Container, sie sich nicht
verändern. Bei schreibenden Operationen, wie
Einfügen, Löschen oder Verändern werden immer
neue Container aufgebaut.
|
|
|
Beispiel |
Set<Integer> s1 = ...;
boolean b10 = s1.contains(42);
Set<Integer> s2 = s1.insert(42);
boolean b11 = s1.contains(42);
boolean b2 = s2.contains(42);
assert (b10 == b11);
assert b2;
|
|
|
Funktionale Programmierung |
Dieser Ansatz ermöglicht es, in Java funktional zu programmieren
und so die Vorteile der funktionalen Programmierung nach Java zu übertragen.
|
|
|
Thread Sicherheit |
Diese Container brauchen bei nebenläufigen Anwendungen beim Zugriff nicht synchronisiert werden.
Sie enthalten immer einen konsistenten Wert.
|
|
|
Effizienz |
Für eine effiziente Implementierung persistenter Container
ist es zwingend notwendig, möglichst viele der im Container enthaltenen Teilstrukturen mehrfach gemeinsam zu nutzen.
|
|
|
Verkettete Listen |
sind üblicherweise eine sehr ineffiziente Implementierung. Das Anhängen eines Elementes
vorne an eine Liste ist konstant in Platz und Laufzeit, die gesammte Liste kann gemeinsam genutzt werden. Beim Anhängen hinten an eine Liste
muss aber die gesammte Liste kopiert werden, die Operation ist also in Platz und Laufzeit linear zur Länge der Liste.
|
|
|
Bäume |
können die Effizienz stark verbessern. Es müssen zum Beispiel beim Einfügen nur die Knoten auf dem Weg von der Wurzel zum Blatt kopiert werden,
der Rest kann gemeinsam genutzt werden.
|
|
|
Literatur |
über persistente Container gibt es im Bereich der Funktionalen Programmierung. Hier sind einige Hinweise:
- Algorithms A Functional Programming Approach
- Buch von Fethi Rabhi und Guy Lapalme, ISBN 0-201-59604-0
- Purely Functional Data Structures
- Buch von Chris Okasaki, ISBN 0-521-66350-4
- List Implementations in Haskell
- http://citeseer.ist.psu.edu/cache/papers/cs/9285/ http:zSzzSzwww.comlab.ox.ac.ukzSzouclzSzuserszSz pedro.borgeszSztransfer.pdf /borges97sequence.pdf
- An Overview of Edison
- http://citeseer.ist.psu.edu/cache/papers/cs/15690/ http:zSzzSzwww.cs.nott.ac.ukzSz ~gmhzSzpaperszSz5.pdf/okasaki00overview.pdf
- Explaining Binomial Heaps
- http://citeseer.ist.psu.edu/cache/papers/cs/10466/ http:zSzzSzwww.informatik.uni-bonn.dezSz ~ralfzSzBinHeap.pdf/hinze99functional.pdf
- Constructing Red-Black-Trees
- http://citeseer.ist.psu.edu/cache/papers/cs/10466/ http:zSzzSzwww.informatik.uni-bonn.dezSz~ralfzSzRedBlackTree2.pdf/ hinze99constructing.pdf
- Efficient Data Structures in a Lazy Functional Language
- http://citeseer.ist.psu.edu/cache/papers/cs2/309/ http:zSzzSzwww.tu-harburg.dezSz ~simh0054zSzEdisonzSzEfficientDataStructures.pdf/ holters03efficient.pdf
- Simple Implementation of Priority Search Queues
- http://citeseer.ist.psu.edu/cache/papers/cs/23580/ http:zSzzSzwww.cs.bonn.eduzSz ~ralfzSzpublicationszSzUU-CS-2001-09.pdf/ hinze01simple.pdf
- Numerical Representations as Purely Functional Data Structures
- http://www.mit.edu/~vkuncak/papers/prim.ps
- Finger Trees
- http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
|
|
|
Ziel |
dieses etwas größeren zusammenhängenden Projekts ist die Entwicklung eines Collection-Frameworks, in dem
für die ADTs Set, Bag, List und Map verschiedene Implementierungen mit unterschiedlichem Speicherplatz- und Laufzeitverhalten erstellt werden.
|
|
|
Schnittstelle |
Eine einheitliche Schnittstelle und eine (sehr ineffiziente) Referenzimplementierung sind vorgegeben.
|
|
|
Themengruppen |
Es werden drei Themengruppen gebildet
|
|
|
Implementierungen |
Eine Themengruppe wird die unterschiedliche Implementierung der einzelnen ADTs enthalten.
|
|
|
Funktionstest |
Die Implementierungen müssen in jeder Situation zuverlässig und korrekt arbeiten.
Hierfür ist für jeden ADT eine Testumgebung zu entwickeln, mit der die
Gesetze des ADTs systematisch und intensiv getestet werden können. Dieses bildet den zweiten Themenkreis.
|
|
|
Performancetest |
Im dritten Themenkreis soll für die einzelnen ADTs eine Benchmark Testumgebung entwickelt werden.
In den Tests soll sowohl das Speicherplatz- als auch das Laufzeitverhalten der einzelnen Operationen eines ADTs gemessen werden.
Die Ergebnisse sollen grafisch visualisiert werden.
In der Visualisierung sollte erkennbar sein, mit welcher Zeit- und Platzkomplexität die verschiedenen Operationen arbeiten.
Die Visualisierung sollte in einem Webbrowser erfolgen.
|
|
|
Programmiersprachen und Werkzeuge |
Java mit Generics
Eclipse oder andere IDEs
JUnit
SVG oder andere webbasierte Werkzeuge zur Visualisierung
|
|
|
Umgebung |
plattformunabhängig
Abnahme unter Linux auf einem gewöhnlichen RZ-Rechner.
|
|
|
Zusammenarbeit |
Die einzelnen 2-er Gruppen müssen in diesem Projekt intensiv zusammenarbeiten.
Die Implementations-Entwickler sollten so früh wie möglich mit den Funktionstest und den
Benchmarkgruppen zusammenarbeiten, damit diese Gruppen gegenseitig voneinander profitieren können.
Sollte sich herausstellen, dass die vorgegebenen Schnittstellen unvollständig sind oder ungeschickt
gewählt sind, so können hier auch Änderungen vorgenommen werden.
Diese mussen dann von allen Gruppen berücksichtigt werden.
|
|
|
Themen |
- OrderedMapAsBinarySearchTree
- OrderedMapAsRedBlackTree
- OrderedMapAsAVLTree
- OrderedMapAsPrefixTree (trie)
- OrderedMapAsPatriciaTrie
- OrderedSetAsBinarySearchTree (as Map)
- OrderedSetAsRedBlackTree (as Map)
- OrderedSetAsLinkedList
- OrderedBagAsBinarySearchTree (as Map)
- OrderedBagAsRedBlackTree (as Map)
- OrderedBagAsLinkedList (as Map)
- OrderedBagAsSkewHeap
- OrderedBagAsPrioritySearchQueue
- ListAsBinaryRandomAccessList
- ListAsSkewBinaryRandomAccessList
- ListAsDeques (symmetrische verkettete Liste)
- ListAsFingerTrees (nicht ganz einfach)
- Funktionstest für List
- Funktionstest für Set und Bag
- Funktionstest für Map
- Performancetest für List
- Performancetest für Map
- Performancetest für Set und Bag
|
|
|
