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.