Springe direkt zu Inhalt

Mohamad Weam Albunni:

Dynamische Arrays in optimaler Zeit und Speicher – Theorie, Implementierung und Evaluation

Kurzbeschreibung

Dynamische Arrays sind eine zentrale Datenstruktur moderner Programmiersprachen. Klassische Implementierungen – wie etwa Python-Lists oder Java-ArrayLists – verursachen jedoch typischerweise einen hohen Speicher-Overhead und benötigen beim Vergrößern kurzzeitig doppelten Speicher. In meiner Arbeit untersuche ich mehrere moderne Varianten dynamischer Arrays, darunter den Hashed Array Tree, die Brodnik-Arrays sowie die r-parametrisierten Arrays nach Tarjan & Zwick. Ich habe alle Strukturen in Python implementiert und in einem gemeinsamen Benchmark bezüglich Laufzeit und Speicherverbrauch analysiert. Die Ergebnisse zeigen, wie blockbasierte und mehrstufige Speicherorganisation den Overhead erheblich reduzieren kann, ohne die asymptotische Zeitkomplexität zu verschlechtern. Dadurch lassen sich effiziente Alternativen zum klassischen Doubling-Array bestimmen, die sowohl theoretisch optimal als auch praktisch überzeugend sind.

Abschluss
Bachelor of Science (B.Sc.)
Abgabedatum
09.12.2025