TU Darmstadt / ULB / TUbiblio

Persistente Arrays zur effizienten Speicherung sich partiell wiederholender Objektketten

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.

Typ des Eintrags: Masterarbeit
Erschienen: 2009
Autor(en): Barraci, Nima
Art des Eintrags: Erstveröffentlichung
Titel: Persistente Arrays zur effizienten Speicherung sich partiell wiederholender Objektketten
Sprache: Deutsch
Referenten: Walter, Prof. Dr. H.K.-G. ; Glier, Dipl.-Info Oliver
Publikationsjahr: 25 März 2009
Datum der mündlichen Prüfung: April 2004
URL / URN: urn:nbn:de:tuda-tuprints-13512
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.

Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik > Theoretische Informatik
20 Fachbereich Informatik
Hinterlegungsdatum: 17 Nov 2009 21:02
Letzte Änderung: 05 Mär 2013 09:28
PPN:
Referenten: Walter, Prof. Dr. H.K.-G. ; Glier, Dipl.-Info Oliver
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: April 2004
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen