Wie Arrays eine Ebene unter den üblichen Abstraktionen funktionieren, vom RAM-Layout bis Two Sum
Intro
Das Array ist die grundlegendste Datenstruktur der Informatik. Um ein solides Bild davon zu bekommen, hilft es, eine Ebene tiefer zu starten, direkt beim RAM. Hat man einmal verstanden, wie die Hardware aufgebaut ist, folgt das Verhalten des Arrays fast von selbst daraus.
Mit diesem mentalen Modell im Kopf wird leicht verständlich, wie sich Arrays unter der Haube verhalten, warum std::vector in C++ und list in Python so verschieden sind und wie sich mit einem Array Two Sum lösen lässt, ein Klassiker unter den LeetCode-Problemen.
Der RAM ist ein riesiges Array
Der Hauptspeicher (DRAM) eines Computers ist eine große Sammlung von Speicherzellen, im Grunde winzige Kästchen, die jeweils ein kleines Stück Information halten. Wie ein riesiges Lagerhaus, Reihe um Reihe voller Regale.
Damit die CPU diese Kästchen nutzen kann, muss sie sie ansprechen können. Genau dafür gibt es Speicheradressen. Jede Zelle im RAM hält genau 8 Bit (1 Byte) und trägt eine eindeutige Adresse, eine fortlaufend vergebene Nummer, meist hexadezimal geschrieben, etwa 0x7ffe5367e044. Als wäre jedes Regal im Lagerhaus mit einer eigenen Seriennummer beschriftet, von null an durchnummeriert.
Tritt man einen Schritt zurück und betrachtet das Ganze von oben, wird daraus eine lange Kette aus fortlaufenden Speicheradressen. Jedes Byte sitzt an einer festen Position, eins nach dem anderen. Logisch gesehen ist der RAM also nichts weiter als ein einziges riesiges eindimensionales Array, fest in die Hardware eingebrannt.
Dieses Hardware-Array zwingt jeder Software, die darüber läuft, zwei Einschränkungen auf.
Erstens kann die CPU mit einer Zelle genau zwei Dinge tun:
Das Byte an einer Adresse lesen.
Ein Byte an eine Adresse schreiben.
Es gibt keine Hardware-Instruktion, die einen neuen Block zwischen zwei bestehende schiebt und keine, die ein Regal entfernt, um das Lagerhaus zu verkleinern. Die Größe des physischen Arrays steht fest und die Reihenfolge ebenso. Jede höhere Datenstruktur muss aus diesen beiden Bausteinen entstehen.
Zweitens erreicht man ein Kästchen, indem man direkt zu seiner Adresse springt, nicht indem man sich durch die anderen sucht. Das macht einen einzelnen Speicherzugriff zu O(1). Wie lange das Lesen oder Schreiben einer Zelle dauert, hängt nicht davon ab, wo im Speicher sie liegt.
Arrays im Speicher
Bisher war der gesamte RAM ein großes Array, aber ein Programm bekommt fast nie den kompletten RAM. Stattdessen fordert es ein kleines, zusammenhängendes Stück vom Betriebssystem an und dieses Stück heißt üblicherweise Array.
Das Zusammenhängende macht ein Array schnell und nützlich. Weil alle Elemente direkt nebeneinander liegen, ist die Adresse jedes Elements nur eine kleine Rechnung, base + index * elementSize, wobei base die Adresse des ersten Elements ist. Ein Beispiel: Element 7 eines int-Arrays, das bei Adresse 1000 beginnt, liegt bei 1000 + 7 * 4 = 1028. Die CPU sucht nicht danach, sie rechnet die Adresse aus und liest direkt. Deshalb kosten Element 7 und Element 7000 gleich viel, einen Lesezugriff. Wie lange das Durchlaufen des Arrays in der Praxis wirklich dauert, ist eine andere Frage, da redet der Cache mit, aber das kommt später. Für den Moment ist das der O(1)-Zugriff aus dem letzten Abschnitt, mit der Rechnung dahinter.
Aber die Geschwindigkeit hat ihren Preis. Die Größe des Arrays muss im Moment der Allokation feststehen, denn das Stück hat auf beiden Seiten Nachbarn, die es nicht verdrängen darf. Auch die Reihenfolge liegt fest. Einen Wert in der Mitte einzufügen heißt also, jedes Element dahinter eine Zelle weiterzuschieben, um Platz zu machen. Bei einem Array aus n Elementen sind das bis zu n Verschiebungen, ein Einfügen in der Mitte ist damit O(n). Löschen geht genauso, nur rückwärts.
Sortiert man das Array, kommt eine Regel obendrauf. Die Elemente bleiben geordnet und das macht die Suche billig. Statt sie eins nach dem anderen zu prüfen, schaut man auf das mittlere Element und fragt, ob das Ziel links oder rechts davon liegt. Weil das Array geordnet ist, verrät dieser eine Vergleich, welche Hälfte man behält. Die andere fliegt weg und das Spiel beginnt von vorn. Jeder Schritt halbiert den Rest, das drückt die Suche von O(n) auf O(log n). Der Haken: Die Ordnung zu halten ist nicht umsonst. Jedes Einfügen muss erst seinen Platz suchen und dann den Rest verschieben, man tauscht also O(n) Schreibzugriffe gegen billigere Lesezugriffe.
Dynamisches Array
Wie im letzten Abschnitt erwähnt, hat das Array eine harte Grenze. Seine Größe steht beim Allokieren fest und sobald jede Zelle voll ist, gibt es keinen Platz mehr zum Wachsen. Was also tun, wenn noch ein Wert angehängt werden soll und nichts mehr frei ist?
Der Trick ist, das Array gar nicht erst wachsen zu lassen. Man allokiert woanders im Speicher einen neuen, größeren Block, kopiert jedes vorhandene Element hinein, gibt den alten Block frei und wechselt zum neuen. Ein dynamisches Array verpackt das alles, sodass man nie etwas davon mitbekommt. In C++ heißt es std::vector, in Python list. In beiden sieht ein Append nach einer einzelnen billigen Operation aus, auch wenn darunter ab und zu eine teure Komplettkopie ausgelöst wird.
Spannend ist die Frage, wie viel größer der neue Block sein sollte. Angenommen, er wächst jedes Mal um genau eine Zelle. Dann kopiert jeder Append das ganze Array, also n Kopien für n Appends und der Aufbau ist O(n²). Besser ist geometrisches Wachstum. Geht dem Array der Platz aus, allokiert man die doppelte Größe. Eine Kopie fällt dann nur bei 1, 2, 4, 8, 16 Elementen an und wird umso seltener, je größer das Array wird. Der Preis dafür ist etwas überschüssiger Speicher. Verteilt man die Kosten dieser seltenen Kopien auf all die billigen Appends dazwischen, landet jeder im Schnitt bei O(1). Das steckt hinter amortisiertem O(1): Die meisten Appends schreiben nur in eine freie Zelle, ein paar sind teuer und im Mittel bleibt es konstant.
Genau hier fangen C++ und Python an, sich unterschiedlich zu verhalten und darum geht es jetzt.
Arrays in Python und C++
Beide Sprachen bieten ein dynamisches Array, aber was im Block steckt, ist nicht dasselbe und dieser Unterschied entscheidet über das Tempo.
Ein C++ std::vector<int> speichert die Integer selbst, dicht an dicht gepackt (oder ein std::array, wenn die Größe feststeht). Element 7 liegt vier Bytes hinter Element 6, genau das base + index * elementSize-Layout von vorhin. Beim Durchlaufen des Vektors liest die CPU einen zusammenhängenden Abschnitt Speicher und genau dafür ist die Hardware gebaut. Sie lädt Speicher in Blöcken, sogenannten Cache-Lines (meist 64 Bytes). Ein einzelner int zieht also meist die nächsten fünfzehn gratis mit und ein Prefetcher erkennt das geradlinige Muster und holt schon mal vor. Was als Nächstes gebraucht wird, liegt meistens längst nah an der CPU.
Eine Python-list sieht von außen gleich aus, funktioniert intern aber anders. Der Block ist ebenfalls zusammenhängend, nur hält er Pointer statt Werte. In Python ist alles ein Objekt. Jeder Integer lebt als eigenes Objekt auf dem Heap und die Liste merkt sich bloß die Adressen. Ein Element zu lesen heißt: erst den Pointer aus dem Block laden, dann ihm folgen, dahin, wo der eigentliche int liegt. Dieser zusätzliche Sprung bei jedem Zugriff macht eine Liste aus Zahlen langsamer zu durchlaufen als einen flachen Block aus Werten. Deshalb läuft schwere Zahlenarbeit in Python über NumPy, dessen Arrays die rohen Werte hintereinander ablegen statt Pointer.
Dieselbe Idee, anders umgesetzt. C++ hält die Werte genau dort, wo die Rechnung sie hinlegt, Python hält eine ordentliche Tabelle von Pointern auf Werte, die quer über den Heap verstreut liegen. Beide indizieren in O(1), aber die Konstante, die sich in diesem O(1) versteckt, ist viel kleiner, wenn die Daten wirklich zusammenhängen. Genau diese Lücke zeigt sich bei Two Sum.
Two Sum
Two Sum gibt ein Array aus Integern und ein Ziel vor und fragt nach den Indizes der zwei Zahlen, die sich dazu aufaddieren. Für [2, 7, 11, 15] mit Ziel 9 ist die Antwort [0, 1], weil die Werte an diesen Stellen zusammen 9 ergeben.
Am einfachsten prüft man jedes Paar. Für jedes Element läuft man den Rest des Arrays durch und fragt, ob es das Ziel komplettiert.
def two_sum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
Jede Zeile hier ist die eine Array-Operation aus dem ganzen Beitrag: nums[i] und nums[j] sind Index-Lookups, jeder ein O(1)-Lesezugriff direkt auf eine Adresse. Die einzelnen Lesezugriffe sind billig. Teuer wird es durch ihre Anzahl. Die äußere Schleife läuft n-mal, die innere pro Durchlauf bis zu n-mal, macht in der Größenordnung n² Lesezugriffe. Das ist O(n²). Bei zehn Elementen ist das nichts. Bei einer Million sind es eine Billion Lesezugriffe. Da läuft der Laptop nebenbei als Heizung.
Denselben Code habe ich zweimal auf LeetCode eingereicht: Python bei 1719 ms, C++ bei 40 ms. Gleicher Algorithmus, gleiches O(n²), Faktor vierzig dazwischen. Das meiste davon ist der Interpreter, CPython arbeitet jeden Lesezugriff und jede Addition als Bytecode ab, während C++ direkt zu Maschinenbefehlen kompiliert. Das Speicher-Layout aus dem letzten Abschnitt ist der Rest: Die C++-Zugriffe bleiben in Cache-Lines, die Python-Zugriffe jagen Pointern über den Heap hinterher. Das Big-O ist identisch, die Wall-Clock nicht.
Das Array liefert also den schnellen Teil, den billigen indizierten Zugriff. Der teure bleibt übrig, die schiere Zahl der Paare. Die loszuwerden ist das eigentliche Problem und mit dem Array allein geht das nicht. Üblich ist eine Hash Map, die zusätzlichen Speicher gegen einen einzigen O(n)-Durchlauf eintauscht. Das ist eine eigene Struktur, aufgebaut auf genau dem Array aus diesem Beitrag. So geht der Rest der Serie weiter, von der Hardware aufwärts.