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 zu verstehen, wie es funktioniert, gehst du am besten eine Ebene tiefer, direkt zum RAM. Hast du einmal gesehen, wie die Hardware aufgebaut ist, ergibt sich das Verhalten eines Arrays fast von allein.
Mit diesem Bild 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 du mit einem Array Two Sum löst, eines der klassischen LeetCode-Probleme.
Stell dir den RAM als riesiges Array vor
Der Hauptspeicher (DRAM) eines Computers ist eine große Sammlung von Speicherzellen, im Grunde winzige Kästchen, die jeweils ein kleines Stück Daten halten. Stell dir ein riesiges Lagerhaus vor, Reihe um Reihe voller Regale.
Damit die CPU diese Kästchen nutzen kann, muss sie sie ansprechen können und genau dafür gibt es Speicheradressen. Jede Zelle im RAM hält genau 8 Bit (1 Byte) und trägt eine eindeutige Adresse, eine Zahl, die fortlaufend hochzählt und meist hexadezimal geschrieben wird, etwa 0x7ffe5367e044. Als würdest du jedes Regal im Lagerhaus mit einer eigenen Seriennummer beschriften, von null an durchnummeriert.
Tritt einen Schritt zurück und das Ganze wird zu einer langen Kette aus Daten. Jedes Byte sitzt an einer festen Position, eins nach dem anderen, also ist der RAM logisch gesehen 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 erreichst du ein Kästchen, indem du direkt zu seiner Adresse springst, nicht indem du dich durch die anderen suchst. 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 das Ganze. Stattdessen fordert es ein kleines, zusammenhängendes Stück vom Betriebssystem an und dieses Stück nennt man üblicherweise ein Array.
Das Zusammenhängende ist es, was ein Array schnell und nützlich macht. 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. 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 sie direkt, weshalb Element 7 und Element 7000 gleich viel kosten, 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 in dem Moment feststehen, in dem du es allokierst, denn das Stück hat auf beiden Seiten Nachbarn, die du nicht verdrängen willst. 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.
Sortierst du 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, schaust du auf das mittlere und fragst, ob dein Ziel links oder rechts davon liegt. Weil das Array geordnet ist, verrät dir dieser eine Vergleich, welche Hälfte du behältst, die andere wirfst du weg und wiederholst das. 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, du tauschst also O(n) Schreibzugriffe gegen billigere Lesezugriffe.
Dynamisches Array
Wie im letzten Abschnitt erwähnt, hat das Array eine harte Grenze. Du legst seine Größe beim Allokieren fest und sobald jede Zelle voll ist, gibt es keinen Platz mehr zum Wachsen. Was machst du also, wenn du noch einen Wert anhängen willst und nichts mehr frei ist?
Der Trick ist, das Array gar nicht erst wachsen zu lassen. Du allokierst woanders im Speicher einen neuen, größeren Block, kopierst jedes vorhandene Element hinein, gibst den alten Block frei und wechselst zum neuen. Ein dynamisches Array verpackt das alles, sodass du nie etwas davon mitbekommst. 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, du 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 wächst du geometrisch. Geht dem Array der Platz aus, allokierst du die doppelte Größe, eine Kopie fällt also 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. Verteilst du 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 geben dir 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 du eine feste Größe willst). Element 7 etwa liegt vier Bytes hinter Element 6, genau das base + index * elementSize-Layout von vorhin. Läufst du durch den Vektor, 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 du brauchst, liegt meistens längst nah an der CPU.
Eine Python-list sieht von außen gleich aus, hat innen aber etwas anderes. Der Block ist auch zusammenhängend, nur hält er Pointer statt Werte. In Python ist alles ein Objekt, jeder Integer lebt also 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 beim nächsten Schritt, Two Sum.
Two Sum
Two Sum gibt dir ein Array aus Integern und ein Ziel 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 direktesten prüfst du einfach jedes Paar. Für jedes Element läufst du den Rest des Arrays durch und fragst, 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 kannst du deinen Laptop als Heizung benutzen.
Derselbe Code, 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 schenkt dir also den schnellen Teil, den billigen indizierten Zugriff und lässt dir den teuren, die schiere Zahl der Paare. Die loszuwerden ist das eigentliche Problem und mit dem Array allein schaffst du 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 dem Array, das du gerade gesehen hast. So geht der Rest der Serie weiter, von der Hardware aufwärts.