In diesem Kapitel wollen wir untersuchen, wie Listen in Python implementiert sind und welche Laufzeiten hierbei gewährleistet werden können. Hierbei geht es insbesondere um die dynamischer Veränderung ihrer Größe, welche ein sehr flexibles Programmieren mit Listen ermöglicht. Dennoch haben einige Listen-Operationen dennoch keine konstante Laufzeit und für das effiziente Programmieren mit Listen ist es wichtig, um welche Operationen es sich dabei handelt und wie man Listen einsetzen soll.
Python Listen stellen eine dynamische Weiterentwicklung von Arrays dar. Arrays wurden schon in den ersten Programmiersprachen als die Datenstruktur zur Speicherung mehrerer Werte angeboten und sind auch heute noch als eingebaute Datenstruktur in C, C+` und Java sehr wichtig. Ein Array hat dabei in der Regel eine feste Größe, welche bei der Konstruktion festgelegt wird. Die Werte im Array können dabei standardmäßig beim Anlegen vordefiniert werden (z.B. in Java) oder undefiniert sein, wie in C. Der Zugriff auf die Elemente erfolgt über einen Index, welche in der Regel von Null bis zur Größe des Arrays minus eins geht. Die Zugriffe (nachschlagen oder mutieren) sind hierbei in konstanter Zeit möglich und entsprechen in der Regel einem direkten Zugriff auf eine Speicherzelle im Speicher des Computers.
Arrays entsprechen also letztlich Python-Listen, ohne Operationen, die die Größe der Liste verändern. Auch Operationen, wie Slicen oder die Operation + zum Zusammenfügen von Listen standen zunächst für Arrays nicht zur Verfügung, können aber (insbesondere da sie die Liste nicht mutieren, sondern eine neue Liste konstruieren) auch für Arrays definiert werden. Problematisch ist allerdings, wenn Slices zum Verändern einer Liste genutzt werden und sich hierbei die Länge der Liste ändert. Auch dies kann nicht so einfach auf Arrays übertragen werden.
In Python gibt es keinen vordefinierten Array-Datentyp. Wir werden im Folgenden aber dennoch Arrays in Python verwenden und hierzu die Bibliothek numpy verwenden, welche spezielle Datenstrukturen für Arrays, aber auch Matrizen zur Verfügung stellt und im Bereich der numerischen Programmierung sehr beliebt ist. Die vordefinierten Funktionen auf den Arrays sind dabei sehr effizient in C implementiert und sehr umfangreich ausgestaltet, weshalb Python auch besonders gerne im Bereich Data Science und KI eingesetzt wird.
Wir demonstrieren die Verwednung von Arrays in numpy anhand des folgenden Beispielcodes:
import numpy
a = numpy.array([1,2,3,4,5])
print(a) # [1 2 3 4 5]
a[2] = 42
print(a) # [1 2 42 4 5]
print(a.size) # 5
print(a[4]) # 5
print(a+a) # [2 4 84 8 10]
b = numpy.zeros(5, dtype=int)
b[2] = 31
print(a+b) # [1 2 73 4 5]
In Zeile 3 legen wir eine neues Array an. Hierbei stellt die Funktion numpy.array einen Konstruktor des Array-Datentyps dar. Es erhält eine Liste als Parameter und legt ein Array an, welches genau die Werte der Liste enthält. Ein weitere Konstruktor ist zeros, welcher ein Array der übergebenen Größe (hier 5) anlegt und alle Werte mit 0 initialisiert. Hierbei legt numpy standardmäßig ein Array von Floatingpointzahlen an, welches wir durch Angabe des dtype auch auf int setzen können. Als Einschränkung dürfen Arrays in numpy aber nicht heterogen sein. Alle Werte müssen denselben Typ haben und es sind in der Regel Basistypen, die hier verwendet werden. Arrays können in numpy auch mehrdimensional sein, worauf wir hier aber nicht weiter eingehen.
Die weiteren Zugriffe auf das Array verhalten sich sehr ähnlich, wie bei Listen. Einzige Ausnahme ist die Operation +, welche die Arrays nicht konkateniert, sondern komponentenweise addiert, siehe Zeile 9 und 12. Hierbei wird aber keins der Arrays mutiert, sondern ein neues Array gleicher Größe angelegt.
Bei der Ausgabe werden Arrays zur besseren Unterscheidung zu Listen ohne Kommas dargestellt, was auch eher der Matrizen- oder Vektor-Schreibweise entspricht.
Methoden, wie append stehen zur Verfügung und Slices können nur sehr eingeschränkt verwendet werden, was hier dem Selbststudium überlassen werden soll.
Um zu verstehen, weshalb Operationen, die die Größe eines Arrays verändern problematisch sind, skizzieren wir kurz, wie Arrays im Speicher des Computers abgelegt werden. Sie beginnen an einer beliebigen Speicherstelle und enthalten hintereinander einfach die Werte, die im Array abgelegt wurden. Darüber hinaus wird in der Regel noch eine Information zur Größe des Arrays abgelegt, damit eine Fehlermeldung beim Zugriff auf einen Index außerhalb der Array-Größen erfolgen kann. Bei C ist dies nicht der Fall und man liest oder schreibt einfach irgendwo anders in den Speicher, was oft zu den berühmten Segmentation Faults führen kann.
Betrachtet man das Array aus Zeile 4 unseres Beispielprogramms, so wird dies wie folgt im Speicher abgelegt werden:
Adresse: |98|99|9A|9B|9C|9D|9E|9F|A0|
-------------------------------------
Wert : |B0|42|05|01|02|03|04|05|A4|
Hierbei ist in diesem Beispiel die Speicheradresse (welche wir vereinfacht als zweistellige Hexadezimalzahl betrachten) an der das Array abgelegt wurde 9A und die Werte stellen wir der Einfachheit halber ebenfalls als zweistellige Hexadezimalzahl dar. Die Werte des Arrays beginnen somit an Adress 9B und die Größe befindet sich in Adresse 9A. Die Adresse 9A wird in der Variablen a abgelegt, wie wir es auch vorher schon skizziert hatten (Variablen zeigen auf Objekte).
Greift man nun auf a[i] zu, wird der Index i+1 einfach zur Adresse in a hinzu addiert, was sehr effizient direkt über einen Ladebefehl des Prozessors möglich ist. Die zusätzliche 1 kompensiert hierbei die Längeninformation. Entsprechend kann auch ein mutieren eines Indexes durch eine einfache Schreiboperation in den Speicher sehr effizient realisiert werden.
Man beachte, dass der Speicher hinter dem Array wieder für andere Objekte verwendet wird. Möchte man das Array also vergrößern (z.B. mittels append) ergibt sich das Problem, dass hinter dem Array nicht wirklich Platz verfügbar ist und wir letztlich das Array nur an eine andere, freie Speicherstelle kopieren können. Hierzu bieten maschinennahe Programmiersprachen, wie C, in der Regel die Möglichkeit Speicher einer gewissen Größe anzufordern und diesen dann zu beschreiben. Möchte man also ein append realisieren, würde man also Speicher anfordern, der eine Speicherzelle größer ist, als der bisher für das Array verwendete und würde diesen das Array dann dort hin kopieren müssen, bevor man dann den angehängten wert hinzu fügt.
Diese Kopieroperation hat aber (auch in Maschinensprache) lineare Laufzeit in der Länge des Arrays, was die Operation vergleichsweise teuer macht und früher in der Regel in Form einer expliziten Programmierung in die Hände der Programmiererin gelegt wurde. Darüber hinaus gibt es noch ein weiteres Problem. Das Array liegt nach dem Kopieren natürlich an einer anderen Stelle im Speicher und wie wir ja wissen, kann es mehrere Referenzen auf dieses Array geben, z.B. wenn man eine weitere Variable auf dasselbe Array referenziert (b = a).
Referenzen zeigen ja nur in eine Richtung und wir speichern nicht alle Referenzen auf eine Array beim Array ab. Somit ist es nicht möglich, nach dem Vergrößern des Arrays in a, auch den Zeiger in b zu aktualisieren. Um es dennoch zu ermöglichen Objekte im Speicher zu verschieben, führt man eine sogenannte Box ein, welche einfach nur einen Zeiger auf das Array enthält und deren Speicheradresse wir dann in den Variablen a und b ablegen können. Diese Adresse wird niemals verändert und wir können nach dem Verschieben unseres Arrays einfach nur den Zeiger in der Box verändern und diese Änderung wird dann bei allen Verweisen auf unser Array sichtbar. In C werden solche Boxen in der Regel nicht verwendet und Objekte werden auch nicht im speicher verschoben. Dies ist natürlich effizienter, weshalb C auch als maschinennahe Programmiersprache bezeichnet wird. Höhere Programmiersprachen verwenden in der Regel solche Indirektionen, welche auch bei der automatischen Speicherverwaltung (Garbage Collection) sinnvoll sind, aber zu einem konstanten Slowdown führen.
Bei unserem obigen Beispiel haben wir die int-Werte direkt in die Speicherzellen geschrieben. Verwendet man heterogene Arrays, ist die Verwendung von Boxen für die Werte im Array ebenfalls sinnvoll, da es so möglich ist, auch größere Objekte (wie z.B. Listen) als einzelnen Eintrag im Array zu verwenden. In dem Array stecken also wieder nur Referenzen auf die entsprechenden Objekte, was wir auch vorher schon als Pfeile in den Objekt-Bildern dargestellt haben. Wenn man dies mit der Repräsentation von Variablen vergleicht, sieht man dass man Arrays auch als Hintereinanderreihung von Variablen auffassen kann und man mittels a[i] eben auf die i-te Variable im Array zugreift und diese lesen oder eben auch zuweisen kann.
Nachdem wir nun also verstanden haben, wie wir Arrays prinzipiell auch verlängern können, können wir unter Verwendung von numpy-Arrays eine eigene Implementierung von Listen entwickeln. Wir beschränken uns zunächst auf die Methoden zum Zugriff auf einen Index und die Methode append. Um eine Verwechslung mit den vordefinierten Listen zu vermeiden nennen wir unsere Klasse DynArray. Außerdem beschränken wir uns bei den Werten auf int-Werte, da Arrays in numpy nicht heterogen sein dürfen.
import numpy
class DynArray :
# construct an empty list, like []
def __init__(self) :
self.array = numpy.array([], dtype=int)
self.size = 0
# with this, you can access elements by l[index]
def __getitem__(self,index) :
return self.array[index]
# with this, you can modify indices by l[index] = value
def __setitem__(self,index,value) :
self.array[index] = value
# with this, you can compute the length by len(l)
def __len__(self) :
return self.size
# convert to string for output, like print(l)
def __str__(self) :
# for simplicity we use Pythons lists, but we could also
# produce the string directly
return str(list(self.array[0:self.size]))
Im Konstruktor initialisieren wir zunächst mit einem leeren Array (den Typ setzen wir sicherheitshalber auf int) und speichern auch die verwendete Größe.
Des weiteren definieren wir spezielle Methoden, welche uns wichtige Python-Funktionen für Listen zur Verfügung stellen. Wie __add__ wird z.B. die Mutation l[i] = v in einen Aufruf l.__getitem__(i,v) umgewandelt.
Nun wollen wir auch das append realisieren und müssen ein resize initiieren, welches neuen Speicher anlegt (durch das Anlegen des neuen Arrays) und dann (hier explizit) die Werte kopiert.
Wir werden das Array später nicht in jedem Schritt um nur eine Speicherzelle vergrößern, weshalb wir hier die neue Kapazität als Parameter übergeben.
def resize(self,new_capacity) :
old_array = self.array
self.array = numpy.zeros((new_capacity,),dtype = int)
for i in range(self.size) :
self.array[i] = old_array[i]
def append(self,x) :
if self.size == self.array.size :
self.resize(self.array.size ` 1)
self.array[self.size] = x
self.size = self.size ` 1
Bei der Verwendung des DynArray ergibt sich nun fast kein Unterschied mehr im Vergleich zur Python-Liste, was das folgende Testprogramm zeigt:
l = DynArray()
n = 10
for i in range(n) :
l.append(i)
print(len(l)) # 10
sum = 0
for x in l : # also works, without any further method definition
sum = sum ` x # simply iterates all indices
print(sum) # 45
Führt man dieses Programm (auch ohne die Summenberechnung) nun für unterschiedliche Werte in n aus, so sieht man, dass es nicht besonders effizient ist und die Laufzeit in \(O(n^2)\) liegt. Dies liegt daran, dass wir in jedem append-Aufruf das komplette Array kopieren und somit über den kleinen Gaus eine quadratische Laufzeit erhalten.
Es ist natürlich auch nicht sinnvoll, das Array in jedem Schritt um nur einen Eintrag zu vergrößern. Besser wäre es, hier auf Vorrat direkt 100 zusätzliche Zellen anzulegen. Hierdurch können dann die nächsten 99 append-Aufrufe ohne weiteres Kopieren erfolgen und einfach die freien Zellen im Array nutzen. Hierdurch verbessert sich die Laufzeit enorm. Allerdings behalten wir immer noch eine quadratische Laufzeit, da nun alle 100 Schritte ein Kopiervorgang durchgeführt werden muss und wir zwar nur noch in \(O(\frac{1}{100}n^2)\) liegen, was aber immer noch in \(O(n^2)\) ist. Die einzelne append Operation hat also eine Laufzeit von \(O(n)\).
Für die praktische Nutzung wäre es natürlich wünschenswert, wenn ein append-Aufruf konstante Laufzeit hätte und bisher haben wir Listen auch immer so verwendet, als würde dies gelten. Wir haben gesehen, dass eine Vergrößerung um einen größeren Wert zwar besser ist, aber eben nicht die Komplexität verändert. Wir müssen also dafür sorgen, dass für größere Listen, eine größere Vergrößerung erfolgt, als für kleinere Listen, um hier tatsächlich einen Effekt zu erzielen. Deshalb addieren wir beim Vergrößern keinen konstanten Wert, sondern verdoppeln die Arraygröße jeweils. Als kleines Detail sollten wir dann mit einem Array der Größe 1 starten, da sich sonst bei der Verdoppelung eine Größe von \(0 \cdot 2 = 0\) ergeben würde.
def append(self,x) :
if self.size == self.array.size :
self.resize(self.array.size ` 1)
...
Messen wir erneut die Laufzeiten unseres Programms, sehen wir, dass es sich nun linear verhält. Es scheint, dass das Programm in \(O(n)\) und die append-Funktion damit in \(O(1)\) liegt. Aber wie ist dies möglich. Wenn wir append analysieren, so hat die Funktion im Worst-Case eine Laufzeit von \O(n)\, mit \(n\) Größe des Arrays. Allerdings hat sie im Best-Case auch die Laufzeit \(O(1)\), wenn das Array eben nicht vergrößert und kopiert werden muss. Wieso spielt bei den Messungen die Worst-Case-Laufzeit von append letztlich keine Rolle?
Dies liegt daran, dass nach einem Worst-Case-Fall für ein Array der Länge \(l\) die Hälfte des neuen Arrays ungenutzt ist und als Konsequenz die nächsten \(l\) append-Operationen eine konstante Laufzeit haben. Erst danach findet erneut eine Operation mit \(2\cdot n\) Kopierschritten statt, bevor dann wieder \(2\cdot n\) Schritte lang der hinzugefügte Wert innerhalb des konstruierten Arrays und damit in konstanter Zeit abgelegt werden kann. Es ergibt sich also die folgende Situation für \(n\):
Das Array wird in den folgenden Schritten vergrößert:
$$ 1, 2, 4, 8, 16, 32, 64, \ldots$$
Betrachten wir also \(n\) append-Schritte, so ergibt sich, die folgenden Schritte des Algorithmus:
1 k ` 1 `
2 k ` 1 ` 1 +
4 k ` 1 ` 1 ` 1 ` 1 +
8 k ` 1 ` 1 ` 1 ` 1 ` 1 ` 1 ` 1 ` 1 +
...
= 1k ` 1 ` 2k ` 2 ` 4k ` 4 ` 8k ` 8 ` ...
= 1(k ` 1) ` 2(k ` 1) ` 4(k ` 1) ` 8(k ` 1) ` ...
wobei k die Kosten für das kopieren eines Arrays der Größe 1 ist und für eine Array der Größe \(n\) sich eben Kosten in Höhe von \(n \cdot k\) ergeben.
Summiert man also die Kosten für \(n\) append-Schritte, so ergeben sich Gesamtkosten in Höhe von
$$\ \ \ \sum\limits_{i=0}^{\lfloor\log_2 n\rfloor} 2^i \cdot (k 1)$$
$$ = (k+1) \cdot \sum\limits_{i=0}^{\lfloor\log_2 n\rfloor} 2^i$$
$$ = (k+1) \cdot 2^{\lfloor\log_2 n\rfloor 1} - 1$$
$$\leq (k+1) \cdot (n 2) - 1$$
$$ = (k+1) n 2k 2 - 1$$
$$ = (k+1) n 2k - 1$$
$$\in O(k\cdot n)$$
Gehen wir nun davon aus, dass \(k\) konstant ist (die Kosten für das anlegen eines Array-Platzes und das Kopieren eines Wertes), so ergibt sich, dass \(n\)-maliges Ausführen von append in \(O(n)\) ist. In der Regel wird \(k\) sogar 1 oder kleiner sein (ist in Python ja in C implementiert), so dass wir insgesamt eine Laufzeit von \(2n ` n - 1 = 3n - 1\) erhalten, also eine recht kleine Konstante.
Fasst man die Analyse noch einmal zusammen, so sieht man, dass für einen teuren Schritt (kopieren, linear in \(n\)) eben genau \(n\) günstige Operationen mit konstanter Laufzeit folgen. Man nennt dies eine \emph{amortisierte Laufzeit}, welche dann eben über viele Operationen gemittelt bedeutet, dass die einzelne Operation im Durchschnitt eben nur eine konstante Laufzeit hat.
Wichtig ist hierbei, dass die teuren Operationen immer seltener werden und damit eben immer mehr konstante Operationen folgen können, was wir durch eine Verdopplung und damit ein exponentielles Wachstum der Listengröße erreichen.
Man beachte hierbei aber, dass in einzelnen Situationen tatsächlich sehr viel Speicher ungenutzt verschwendet wird. Außerdem kann es immer noch passieren, dass einzelne append-Schritte eine längere Laufzeit haben, weshalb man in bestimmten zeitkritischen Anwendungen, wie z.B. im Bereich eingebetteter System mit amortisierten Laufzeiten vorsichtig sein muss. In den meisten Anwendungen spielt dies aber keine Rolle und die Listen in Python sind als solche dynamischen Arrays realisiert.
Neben append bieten Listen auch noch eine Methode pop, welche wir auch schon dazu genutzt haben, Listen als Stacks zu verwenden. Wir müssen also überlegen, wie wir die Arrays auch verkleinern können, um nicht unnötig Speicherplatz zu verschwenden. Hierbei macht es keinen Sinn, die Arrays direkt zu verkleinern, wenn sie nur noch halb gefüllt ist, da wir dann mit dem nächsten append-Schritt direkt wieder eine Verdoppelung der Arraygröße bewirken würden und wir so direkt mehrere teure Schritte hinter einander machen würden, was zu einer Worst-Case linearen Laufzeit in der aktuellen Listengröße von append und pop führen würde. Es macht also Sinn mit der Verkleinerung zu warten, bis das Array nur noch zu einem Viertel gefüllt ist und das Array dann zu halbieren. Dann haben wir für append wieder ausreichend Luft, bis das Array wieder verdoppelt werden muss und auch für weitere \(\frac{n}{4}\) viele pop-Schritte, bis das Array erneut halbiert werden kann. Werden also append- und pop-Schritte, wie beim Stack gemischt, wird die Laufzeit nur besser, da Größenänderungen des Arrays noch seltener stattfinden.
Mit dieser Strategie haben sowohl append als auch pop eine amortisierte, konstante Laufzeit und es ist somit möglich anstelle von Arrays nur die viel dynamischeren Listen zu verwenden. In Java ist man diesen Schritt nicht gegangen, sondern bietet weiterhin auch die statischen Arrays an. Die Klasse ArrayList bietet aber genau die vorgestellten dynamischen Arrays an und viele Programmierer verarbeiten lieber direkt diese, um später auch dynamische Erweiterungen machen zu können.
Die weiteren Methoden, wie extend oder auch das Ersetzen von Slices durch Listen andere Größe, haben aber auch in Python keine konstante Laufzeit. Dies sollte man bei der Programmierung beachten und diese Operationen immer mit Bedacht einsetzen. Oft ist der gewünschte Effekt aber auch auf anderem Weg nicht effizienter zu realisieren. Als Beispiel betrachten wir das Einfügen eines Wertes in eine Liste l[2:2] = [42], bei welchem sich die Listen zum einen Verlängert, aber die Listenelemente ab Index 3 aber eben auch alle um einen Index nach rechts geschoben werden müssen.
Bei der HashMap haben wir diese Idee, des Verdoppelns des Arrays auch schon umgesetzt und mit exakt der gleichen Argumentation erhalten wir hier ebenfalls eine amortisierte konstante Laufzeit für eine insert-Operation, unter der Annahme, dass wir eine gute Hashfunktion verwenden, welche wenig Kollisionen erzeugt.