TU Darmstadt / ULB / tuprints

Persistente Arrays zur effizienten Speicherung sich partiell wiederholender Objektketten

Barraci, Nima :
Persistente Arrays zur effizienten Speicherung sich partiell wiederholender Objektketten.
TU Darmstadt - Fachbereich Informatik
[Diploma Thesis or Magisterarbeit], (2009)

[img]
Preview
Text
DAbarraci.pdf
Available under Simple publication rights for ULB.

Download (826Kb) | Preview
Item Type: Diploma Thesis or Magisterarbeit
Title: Persistente Arrays zur effizienten Speicherung sich partiell wiederholender Objektketten
Language: German
Abstract:

In vielen Anwendungen besteht das Problem, dass eine wachsende Folge von Objekten so gespeichert 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 Konkatenieren 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 Lindenmayer Systeme, welche unter anderem das Wachstum von natürlichen Objekten wie P?anzen simulieren. Die vorliegende Arbeit grenzt die bestehenden und etablierten Datenstrukturen gegenüber einer alternativen Implementierung – den Persistent Arrays –, welche diese an sie gestellten Aufgaben unter besserer Speicherausnutzung und mit geringerem Aufwand durchführen kann, ab. Im Rahmen dessen wird auch ein probabilistischer Algorithmus vorgestellt, welcher mit geringerem 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 Datenstrukturen 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 Konkatenation, 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 resultierenden 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 Implementierung 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 implementiert, welche auf Monoide abbilden. Im Zusammenhang dessen bietet diese Arbeit einen Einblick in diese Strukturen der Allgemeinen Algebra. Ferner wird gezeigt, von welchem Vorteil 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 diskrete Wahrscheinlichkeit gegeben, da diese Theorien die Grundlage für probabilistische Algorithmen bilden. Im Rahmen dessen wird eine Adaptierung des Algorithmus zum probabilistischen Vergleich von Strings vorgestellt, welcher in [MR97] von Motwani und Raghavan vorgestellt wurde.

Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik > Theoretische Informatik
Date Deposited: 26 May 2010 10:17
Last Modified: 10 Dec 2012 11:49
URN: urn:nbn:de:tuda-tuprints-13512
License: Simple publication rights for ULB
Referees: Walter, Prof. Dr. H.K.-G. and Glier, Dipl.-Info Oliver
Refereed: April 2004
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/1351
Export:

Actions (login required)

View Item View Item