Konkrete Datenstrukturen

Aus ProgrammingWiki

Konkrete Datenstrukturen sind Implementierungen eines ADT. Zur Implementierung ein und desselben ADT kann es unterschiedliche konkrete Datentypen geben. Gleiche Operationen können für verschiedene konkrete Datenstrukturen sehr unterschiedliche Laufzeiten haben.

Inhaltsverzeichnis 1 Array 2 Linked List 3 Dynamisches Array 4 Stack 5 Queue 6 Fazit 7 Übungsaufgaben 8 Lösungen

Array

Linked List

Dynamisches Array

Stack

Queue

Fazit

Abschließend stellen wir die Aufwände der einzelnen Operationen übersichtlich zusammen. Derartige Angaben bilden die wichtigste Grundlage für die Interpretation und Entscheidung für oder gegen einen bestimmten Datentyp in entsprechenden Softwareprojekten.

	Access	Search	Insert	Delete
Array	$\mathcal{O}(1)$	$\mathcal{O}(\log_2 n)$, wenn sortiert, sonst $\mathcal{O}(n)$	$\mathcal{O}(1)$	$\mathcal{O}(n)$
Singly linked list	$\mathcal{O}(n)$	$\mathcal{O}(n)$	$\mathcal{O}(1)$, an vorgegebener Position	$\mathcal{O}(n)$
Doubly linked list	$\mathcal{O}(n)$	$\mathcal{O}(n)$	$\mathcal{O}(1)$, an vorgegebener Position	$\mathcal{O}(1)$
Dynamisches Array	$\mathcal{O}(1)$	$\mathcal{O}(\log_2 n)$, wenn sortiert, sonst $\mathcal{O}(n)$	$\mathcal{O}(1)$, amortisiert, sonst $\mathcal{O}(n)$	$\mathcal{O}(1)$, amortisiert, sonst $\mathcal{O}(n)$
Stack	$\mathcal{O}(n)$	$\mathcal{O}(n)$	$\mathcal{O}(1)$	$\mathcal{O}(1)$
Queue	$\mathcal{O}(n)$	$\mathcal{O}(n)$	$\mathcal{O}(1)$	$\mathcal{O}(1)$

Übungsaufgaben

1. Erstellen Sie die Komplexitätsbetrachtungen aller Operationen (Access, Search, Insert und Delete) für die Datentypen Stack und Queue.
2. Wählen Sie die am besten passende (effizienteste) konkrete Datenstruktur (Array, Singly-/Doubly Linked List, dynamisches Array, Stack, Queue) zur Lösung der folgenden Szenarien aus und begründen Sie Ihre Auswahl:
   1. Sie schreiben eine Applikation, bei welcher man Texte editieren kann. Sie möchten nun die Möglichkeit einbauen, etwas rückgängig zu machen. Mit welcher Datenstruktur speichern Sie die vom Benutzer getätigten Aktionen?
   2. Sie programmieren einen Algorithmus, welcher Daten geordnet durchläuft und anhand ihrer vorherigen und nachstehenden Daten vergleicht und bewertet. Welche Datenstruktur eignet sich, um alle Daten die verglichen werden sollen zu speichern?
   3. Sie müssen eine unbekannte Menge an sortierten Daten speichern. Welche Datenstruktur eignet sich dafür am besten?
   4. Sie schreiben ein Programm, welches anfallende Operationen nach und nach abarbeiten soll. Welche Datenstruktur eignet sich am besten, um die anfallenden Operationen zu speichern, bis sie bearbeitet werden können?
3. Ab welcher Belegung wird ein Python Array vergrößert? Überlegen Sie sich, wie man erkennen könnte, wann es vergrößert wird.
4. Zusatzaufgabe: Implementieren Sie Ihre Lösung aus Aufgabe 3.

Hinweis: Nutzen das Array aus dem entsprechenden Python Paket:

from array import array some_array = array("I") some_array.append(1)

Hinweis 2: Zur Darstellung der Zeit, die es pro Insert benötigt, eignet sich pyplot aus der matplotlib Bibliothek. Die Bibliothek funktioniert leider nicht hier im Programming Wiki.

from matplotlib import pyplot pyplot.figure('Figure Title') pyplot.plot(X-AXIS-VALUES, Y-AXIS-VALUES, 'bo', label='Name') pyplot.legend(loc='upper left') pyplot.grid() pyplot.show()

Lösungen

1. Siehe "Stack" und "Queue" im Fazit
2. Folgende Datenstrukturen würden zu den angegebenen Szenarien am besten passen:
   1. Stack: FILO-Prinzip, zuletzt angewandte Aktion wird beim rückgängig machen auch als erstes wieder revidiert. Insert und Delete-Operationen sind beim Stack am effizientesten und der Stack muss nicht erst umgekehrt werden, damit man die zuletzt angewandte Aktion erhält.
   2. Doubly Linked List: Effizienteste Datenstruktur, um vorherige und nachstehende Daten zu bekommen und damit zu arbeiten, da die Pointer auf diese Daten sofort verfügbar sind.
   3. Singly-/DoublyLinkedList: Effizientes Daten schreiben + Ordnung bleibt erhalten. Array auch möglich, garantiert aber nicht, dass die Ordnung beibehalten wird
   4. Queue: FIFO-Prinzip, außerdem am effizientesten darin, Daten ans Ende anzufügen und aus dem Anfang herauszunehmen.
3. Zwei Optionen: bei jeder Insert-Operation die Speicheradresse des Arrays prüfen und schauen wann sich diese verändert, da beim resize das Array an eine andere Speicheradresse verschoben/kopiert wird. Die andere Option wäre die Zeit zu messen, die beim insert gebraucht wird. Bei einem Insert, bei dem das Array vergrößert werden muss, sollte das Einfügen länger dauern, da es erst an eine neue Speicheradresse kopiert werden muss und somit eine Speicherallokation stattfindet.
4. Im Folgenden sind zwei Skripte, die jeweils eine der beschriebenen Lösungen implementieren:

Hinweis: Die Skripte sind in Python3 geschrieben, was im Wiki anscheinend nicht funktioniert, deshalb habe ich die Ausgabe des ersten Skriptes manuell dazu geschrieben.

Änderung der Speicheradresse:

import array buff = 0 vs = array.array('I') for i in range(1, 80): vs.append(i) if buff != vs.buffer_info()[0]: buff = vs.buffer_info()[0] print(f"Buffer changed at insertion {i}")

Buffer changed at insertion 1 Buffer changed at insertion 5 Buffer changed at insertion 9 Buffer changed at insertion 17 Buffer changed at insertion 26 Buffer changed at insertion 35 Buffer changed at insertion 45 Buffer changed at insertion 55 Buffer changed at insertion 66 Buffer changed at insertion 78

Zeitmessung:

from time import time_ns from matplotlib import pyplot from array import array times = [0] iterations = [0] values = array('I') for i in range(1, 80): start = time_ns() values.append(i) end = time_ns() t = end - start times.append(t) iterations.append(i) pyplot.figure('Insertion times of a python array') pyplot.plot(iterations, times, 'bo', label='') pyplot.legend(loc='upper left') pyplot.grid() pyplot.xticks(list(range(len(iterations))), rotation=45) pyplot.show()