Barraci, Nima (2009)
Persistente Arrays zur effizienten Speicherung sich partiell wiederholender Objektketten.
Technische Universität Darmstadt
Masterarbeit, Erstveröffentlichung

Kurzbeschreibung (Abstract)

In vielen Anwendungen besteht das Problem, dass eine wachsende Folge von Objekten so ge- speichert werden muss, dass trotzdem noch ein schneller Zugriff auf die Elemente möglich ist. Ferner wird gewünscht, dass auf diesen Objektketten verschiedene Operationen wie das Sortieren, der Vergleich oder auch einfachere Operationen wie der indizierte Zugriff, das Kon- katenieren und das Aufteilen schnell und mit vergleichsweise geringem Aufwand durchführbar sind. Meist werden für solche Aufgaben Arrays oder linear verketteten Listen verwendet, welche zwar für die meisten Aufgaben ausreichende Laufzeiten garantieren können, jedoch in einigen Anwendungsbereichen aufgrund ihrer Implementierungen Nachteile mit sich bringen. Dies ist vor allem bei Anwendungen der Fall, bei denen auf natürliche Art und Weise die Datenmenge exponentiell wächst. Dies ist zum Beispiel bei Pfaden der Fall, die durch das Formal Language Constrained Path Problem entstehen, bei welchem in einem kantenmarkierten Graph ein Pfad durchlaufen wird, dessen Konkatenation der Kantenmarkierungen die Eigenschaft erfüllen soll, dass das daraus entstehende Wort aus einer durch eine gegebene Grammatik induzierten Sprache liegt. Ferner ist das exponentielle Wachstum von Pfaden ebenfalls eine natürliche Eigenschaft der Linden- mayer Systeme, welche unter anderem das Wachstum von natürlichen Objekten wie Pflanzen simulieren. Die vorliegende Arbeit grenzt die bestehenden und etablierten Datenstrukturen gegenüber einer alternativen Implementierung – den Persistent Arrays –, welche diese an sie gestellten Aufga- ben unter besserer Speicherausnutzung und mit geringerem Aufwand durchführen kann, ab. Im Rahmen dessen wird auch ein probabilistischer Algorithmus vorgestellt, welcher mit geringe- rem Aufwand den Vergleich von exponentiell wachsenden Objektketten ermöglicht. Um einen Vergleich zwischen den etablierten Datenstrukturen und den Persistent Arrays zu ermöglichen, wird zunächst auf den Aufwand und die Implementierung der etablierten Daten- strukturen eingegangen. Da die vorgestellte Erweiterung zu den etablierten Datenstrukturen, die Persistent Arrays, auf AVL-Bäumen basieren, wird diese Technik ebenfalls beleuchtet. Dabei wird für die Persistent Arrays gezeigt, dass für die einzelnen Operationen wie die Konkatena- tion, das Aufteilen und die indizierte Suche eine lineare Laufzeit in Abhängigkeit der Höhe des AVL-Baumes, welcher die Grundlage des Persistent Arrays bildet, garantiert wird. Dies führt sodann zu einer Aussage über die RAM-Simulierbarkeit der Persistent Arrays. Die Vorteile der Persistent Arrays beim Speicherverbrauch resultieren aus der Möglichkeit der Mehrfachreferenzierung von Objekten bzw. Teilen der Objektketten, was aufgrund der Nutzung i einer persistenten Datenstruktur erst möglich wird. In diesem Zusammenhang gibt diese Arbeit ebenfalls einen Einblick in die Nutzung persistenter Datenstrukturen, und zeigt die daraus re- sultierenden Unterschiede zwischen der gewöhnlichen Implementierung der AVL-Bäume und der Implementierung der Persistent Arrays. Die Persistent Arrays wurden zum Vergleich und zur Durchführung verschiedener Tests in der Programmiersprache Java implementiert, und stehen als Package auch anderen Anwendungen zur Verfügung. Dadurch soll die Notwendigkeit unterstrichen werden, dass eine Implemen- tierung der Persistent Arrays, nachdem ihr Nutzen gezeigt wurde, als Standardpaket zu einer Programmiersprache gehört. Die Operationen wie die Suche oder das Sortieren wurden in Form von Homomorphismen im- plementiert, welche auf Monoide abbilden. Im Zusammenhang dessen bietet diese Arbeit einen Einblick in diese Strukturen der Allgemeinen Algebra. Ferner wird gezeigt, von welchem Vor- teil für die über Monoide implementierten Strukturen die Nutzung der Mehrfachreferenzierung von Teilen der Objektketten ist. Neben der konkreten Implementierung, wird im Rahmen dieser Arbeit ein Einblick in die dis- krete Wahrscheinlichkeit gegeben, da diese Theorien die Grundlage für probabilistische Al- gorithmen bilden. Im Rahmen dessen wird eine Adaptierung des Algorithmus zum probabi- listischen Vergleich von Strings vorgestellt, welcher in [MR97] von Motwani und Raghavan vorgestellt wurde.

Frage zum Eintrag

Redaktionelle Details anzeigen