Collection-Framework

Collection-Framework für persistente Container in Java

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

Hauptnavigation