Das dynamische Array von innen

Code in:JavaC#PythonJavaScript

Kurz gesagt: Ein dynamisches Array (list in Python) ist ein Array mit mehr Plätzen als Elementen: Lesen per Index ist O(1), Anhängen am Ende im Mittel O(1), und Einfügen am Anfang ist O(n).

Problem

Der Warenkorb, der langsam wird

Der Online-Shop zeigt den Warenkorb mit dem zuletzt hinzugefügten Produkt ganz oben. Der Code macht das einfach: Jede neue Zeile kommt an Index 0.

order_lines = ["Mehl 25 kg", "Zucker 10 kg", "Öl 5 l", "Reis 10 kg"]
cart = []
for line in order_lines:
    cart.insert(0, line)
print("Der Warenkorb: " + ", ".join(cart))

Ausgabe

Der Warenkorb: Reis 10 kg, Öl 5 l, Zucker 10 kg, Mehl 25 kg

Bei einem normalen Kunden mit 5 Produkten merkst du nichts. Dann kommt ein Großkunde und lädt eine Bestellung aus einer Datei hoch: 50.000 Zeilen. Die Seite hängt sekundenlang.

Der Grund: Jedes Einfügen an Index 0 verschiebt alle schon hinzugefügten Produkte um einen Platz. 50.000 Zeilen machen 1 + 2 + … + 49.999 = 1.249.975.000 Verschiebungen.

Die Idee

Ein Array, das für sich selbst sorgt

list ist innen ein dynamisches Array: ein gewöhnliches Array mit mehr Plätzen, als es Elemente gibt, und einem Zähler, wie viele davon belegt sind.

• Die Kapazität ist, wie viele Plätze das Array hat.
• Die Größe ist, wie viele davon belegt sind, von 0 bis zur Größe minus eins.

Wenn die Plätze aufgebraucht sind, legt es ein neues Array an, doppelt so groß, und kopiert alles. Warum das im Mittel O(1) ist, steht in der Lektion „Amortisierte Komplexität“. Hier schauen wir, was im Inneren des Arrays passiert: beim Lesen, beim Einfügen und beim Entfernen per Index.

Die Plätze des Arrays liegen im Speicher nebeneinander und sind gleich groß. Beginnt das Array bei Adresse 1000 und ist jeder Platz 8 Byte groß, liegt Platz i bei Adresse 1000 + i × 8. Lesen per Index ist also eine Multiplikation und eine Addition: O(1), egal wie viele Elemente es sind.

Sieh es dir an

Dein eigenes dynamisches Array

Hier ist dasselbe, von Hand geschrieben. Das Array beginnt mit 8 Plätzen:

class DynamicArray:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
        self.items[index] = value
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"Index {index}, Größe {self.size}")

Sieh, was beim Lesen, Einfügen und Entfernen mit den Plätzen passiert:

def insert(self, index, value):
    self._check(index, self.size + 1)
    if self.size == len(self.items):
        self._grow()
    for i in range(self.size, index, -1):
        self.items[i] = self.items[i - 1]
    self.items[index] = value
    self.size += 1

def remove_at(self, index):
    self._check(index, self.size)
    removed = self.items[index]
    for i in range(index, self.size - 1):
        self.items[i] = self.items[i + 1]
    self.size -= 1
    self.items[self.size] = None
    return removed

Schritt für Schritt, in Worten

1. Der Warenkorb ist ein einziger Block aus 8 Plätzen nebeneinander im Speicher. 5 sind belegt: Das ist die Größe. Alle 8 sind die Kapazität.
2. cart[3]: Die Adresse ist Start + 3 × 8 = 1024. Ein Sprung, ohne an den anderen vorbeizugehen: O(1), bei jeder Größe.
3. insert(0, …): Platz 0 ist belegt. Jedes Produkt rutscht einen Platz nach rechts, von hinten nach vorn, damit nichts überschrieben wird: 5 Verschiebungen.
4. Erst jetzt kommt „Käse“ auf Platz 0, und die Größe wird 6.
5. remove_at(2) nimmt „Milch“ heraus. Die 3 danach rutschen einen Platz nach links und schließen die Lücke: 3 Verschiebungen.
6. Die Größe sinkt auf 5, und der letzte Platz bekommt None: Die alte Referenz würde das Produkt sonst im Speicher am Leben halten.
7. cart[5]: Platz 5 gibt es (die Kapazität ist 8), aber er gehört nicht zum Warenkorb. Die Prüfung vergleicht mit der Größe und wirft IndexError.
8. Das Lesen per Index ist ein Sprung. Einfügen und Entfernen verschieben alles nach dem Index: Vorne sind das alle n, O(n). Am Ende wird nichts verschoben.

cart = DynamicArray()
cart.append("Brot")
cart.append("Milch")
cart.append("Kaffee")
cart.append("Butter")
cart.append("Äpfel")
print(cart[3])
cart.insert(0, "Käse")
cart.remove_at(2)
for i in range(len(cart)):
    print(f"{i}: {cart[i]}")
print("Plätze: " + str(cart.capacity))
try:
    cart[5]
except IndexError as e:
    print("Fehler: " + str(e))

Ausgabe

Butter
0: Käse
1: Brot
2: Kaffee
3: Butter
4: Äpfel
Plätze: 8
Fehler: Index 5, Größe 5

__getitem__, __setitem__ und __len__ sind die speziellen Methoden, dank denen du cart[3] und len(cart) wie bei der eingebauten list schreibst.

Probier es aus

Sag die Ausgabe voraus

Ein Array mit 8 Plätzen enthält 8 Produkte. Du fügst vorn noch eins ein:

class DynamicArray:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
        self.items[index] = value
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"Index {index}, Größe {self.size}")


cart = DynamicArray()
for i in range(8):
    cart.append(f"P{i + 1}")
cart.insert(0, "P0")
print("Produkte: " + str(len(cart)))
print("Plätze: " + str(cart.capacity))
print(str(cart[8]))

Antwort

Produkte: 9
Plätze: 16
P0

Produkte: 9
Plätze: 16
P8

Produkte: 9
Plätze: 9
P8

Prüfen

Die Idee

Einfügen und Entfernen kosten O(n)

Ein Einfügen an Index i verschiebt alles von i bis zum Ende um einen Platz nach rechts, von hinten nach vorn, damit nichts überschrieben wird. Ein Entfernen verschiebt alles nach i um einen Platz nach links. Je näher am Anfang, desto mehr:

• Am Ende: Nichts wird verschoben. O(1), und mit dem Wachstum amortisiert O(1).
• Vorne: Alles wird verschoben. O(n).
• In der Mitte: Im Mittel die Hälfte. Immer noch O(n).

Darum sind n Einfügungen vorne O(n²) und n Anhängungen am Ende O(n). Die Lösung für den Warenkorb: am Ende anhängen und von hinten nach vorn anzeigen. Das Durchlaufen von hinten ist dasselbe O(n):

order_lines = ["Mehl 25 kg", "Zucker 10 kg", "Öl 5 l", "Reis 10 kg"]
cart = []
for line in order_lines:
    cart.append(line)
newest_first = reversed(cart)
print("Der Warenkorb: " + ", ".join(newest_first))

Ausgabe

Der Warenkorb: Reis 10 kg, Öl 5 l, Zucker 10 kg, Mehl 25 kg

Sieh es dir an

Miss es: am Ende gegen vorne

Lass beide Wege mit denselben Produkten laufen. Wir zählen die Schreibvorgänge von Elementen im Array: das neue, jede Verschiebung und jedes Kopieren beim Wachsen. Das Einfügen vorne bei 100.000 wird nicht wirklich ausgeführt: Bench schätzt es aus der Kurve.

• Am Ende anhängen O(n)
• Vorne einfügen O(n²)

Algorithmus	n = 10	n = 1.000	n = 10.000	n = 100.000
Am Ende anhängen	18	2.016	26.376	231.064
Vorne einfügen	63	501.516	50.021.376	≈ 5.002.137.600

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

class DynamicArray:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
        self.items[index] = value
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"Index {index}, Größe {self.size}")

Bei 1000 Produkten macht das Anhängen am Ende 2.016 Schreibvorgänge: 1000 neue und die Kopien beim Wachsen. Das Einfügen vorne macht 501.516. Bei 10.000 ist der Unterschied 26.376 gegen 50.021.376.

Genauer, für Neugierige

Dieselben Zahlen in deiner Sprache, mit einem Zähler für die Schreibvorgänge in der Klasse:

class DynamicArray:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0
        self.writes = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
            self.writes += 1
        self.items[index] = value
        self.writes += 1
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
            self.writes += 1
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"Index {index}, Größe {self.size}")


for n in [10, 1000, 100000]:
    cart = DynamicArray()
    for i in range(n):
        cart.append(str(1001 + i))
    print(f"am Ende, n = {n}: {cart.writes} Schreibvorgänge")
for n in [10, 1000]:
    cart = DynamicArray()
    for i in range(n):
        cart.insert(0, str(1001 + i))
    print(f"vorne, n = {n}: {cart.writes} Schreibvorgänge")

Ausgabe

am Ende, n = 10: 18 Schreibvorgänge
am Ende, n = 1000: 2016 Schreibvorgänge
am Ende, n = 100000: 231064 Schreibvorgänge
vorne, n = 10: 63 Schreibvorgänge
vorne, n = 1000: 501516 Schreibvorgänge

Probier es aus

Finde den Fehler

Ein Kollege hat insert umgeschrieben. Drei Produkte, dann noch eins vorn, und der Warenkorb sieht so aus:

cart = DynamicArray()
cart.append("Brot")
cart.append("Milch")
cart.append("Kaffee")
cart.insert(0, "Käse")
for i in range(len(cart)):
    print(f"{i}: {cart[i]}")

Ausgabe

0: Käse
1: Brot
2: Brot
3: Brot

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1class DynamicArray:2 def __init__(self):3 self.items = [None] * 84 self.size = 056 def __len__(self):7 return self.size89 @property10 def capacity(self):11 return len(self.items)1213 def __getitem__(self, index):14 self._check(index, self.size)15 return self.items[index]1617 def __setitem__(self, index, value):18 self._check(index, self.size)19 self.items[index] = value2021 def append(self, value):22 self.insert(self.size, value)2324 def insert(self, index, value):25 self._check(index, self.size + 1)26 if self.size == len(self.items):27 self._grow()28 for i in range(index, self.size):29 self.items[i + 1] = self.items[i]30 self.items[index] = value31 self.size += 13233 def remove_at(self, index):34 self._check(index, self.size)35 removed = self.items[index]36 for i in range(index, self.size - 1):37 self.items[i] = self.items[i + 1]38 self.size -= 139 self.items[self.size] = None40 return removed4142 def _grow(self):43 bigger = [None] * (len(self.items) * 2)44 for i in range(self.size):45 bigger[i] = self.items[i]46 self.items = bigger4748 def _check(self, index, limit):49 if index < 0 or index >= limit:50 raise IndexError(f"Index {index}, Größe {self.size}")

Prüfen

Probier es aus

Ergänze

remove_at schließt die Lücke, indem es jedes Element danach um einen Platz nach links verschiebt. Woher kommt das Element von Platz i?

def remove_at(self, index):
    self._check(index, self.size)
    removed = self.items[index]
    for i in range(index, self.size - 1):
        self.items[i] = self.items[]
    self.size -= 1
    self.items[self.size] = None
    return removed

Prüfen

Die Idee

Verkleinern oder nicht

Der Warenkorb hatte 10.000 Produkte, dann hat der Kunde fast alle entfernt. Das Array hält immer noch 16.384 Plätze. Soll es schrumpfen?

Wenn es sich halbiert, sobald die Größe unter die Hälfte fällt, gibt es eine Falle. Ein Array mit 16 Plätzen und 9 Elementen: ein Entfernen, und es hat 8 Plätze, voll. Ein Hinzufügen, und es sind wieder 16 Plätze. Wechsle die beiden genau an dieser Grenze ab, und jede Operation kopiert alles: O(n).

Darum wartet das Verkleinern länger: auf die Hälfte, wenn es zu einem Viertel gefüllt ist. Nach dem Verkleinern ist das Array halb voll, und bis zum nächsten Kopieren sind es mindestens n/4 Operationen. Die Kosten bleiben amortisiert O(1).

Die eingebauten Listen entscheiden unterschiedlich:

• Java ArrayList schrumpft nicht von selbst, es hat trimToSize();
• C# List<T> schrumpft nicht von selbst, es hat TrimExcess();
• Python (CPython) schrumpft von selbst, wenn die Größe unter die Hälfte der Plätze fällt. Die Sprache verspricht das nicht, CPython entscheidet es.
• JavaScript (V8) verkleinert manchmal, nach eigenen Regeln.

Das Verkleinern spart Speicher, kostet aber eine Kopie. Wenn das Array bald wieder wächst, ist es billiger, nicht zu verkleinern.

Die Idee

Warum das Array auch in der Praxis schnell ist: der Cache

Der Prozessor liest den Speicher nicht Byte für Byte. Er nimmt eine ganze Zeile von 64 Byte und hält sie im Cache, einem kleinen und sehr schnellen Speicher direkt bei ihm. Das Lesen aus dem Cache ist zehnmal und mehr schneller als das Lesen aus dem Hauptspeicher.

Das Array ist ein Block. Wenn du Platz 0 liest, kommen seine Nachbarn in derselben Zeile mit, und die nächsten Lesevorgänge kommen aus dem Cache. Der Prozessor merkt auch, dass du der Reihe nach liest, und holt die nächsten Zeilen im Voraus. Darum ist das Durchlaufen eines Arrays nicht nur auf dem Papier schnell, sondern auch auf der Uhr.

Wichtig ist, was in den Plätzen steht: - list hält immer Referenzen auf Objekte, auch für Zahlen, und die Objekte selbst liegen woanders im Speicher. Für viele Zahlen nebeneinander gibt es array in der Standardbibliothek, und in der Datenanalyse nimmt man NumPy.

Die nächste Lektion, „Verkettete Liste“, ist das Gegenteil: Jedes Element ist ein eigenes Objekt irgendwo im Speicher. Dort ist das Einfügen vorne O(1), aber der Cache hilft nicht.

Übung

Ein Array, das schrumpft

Löse die Aufgabe in deinem Editor.

Verkleinern bei einem Viertel. Ersetze das Wachsen der Klasse durch eine Methode _resize(self, places), die ein Array mit so vielen Plätzen anlegt und die Elemente kopiert. insert ruft sie mit doppelt so vielen Plätzen auf, wenn das Array voll ist. remove_at ruft sie mit der Hälfte auf, wenn die Größe ein Viertel der Plätze erreicht, aber nie unter 8 Plätzen.

Füge 20 Produkte hinzu und gib die Größe und die Plätze aus. Entferne dann vom Ende, bis 2 übrig sind, und gib bei jeder Änderung der Plätze die Größe und die Plätze aus:

Ausgabe

20 / 32
8 / 16
4 / 8

Weitere Aufgaben

• indexOf und remove. Füge index(self, value) hinzu, das den Index oder -1 zurückgibt, und remove(self, value), das das erste Vorkommen entfernt. Was kostet jedes?
• Vom Anfang entfernen, ohne zu verschieben. Eine Warteschlange von Bestellungen entfernt immer die erste. Halte einen Index head auf den ersten belegten Platz, statt alle zu verschieben. Was passiert, wenn head das Ende des Arrays erreicht? (Tipp: vom Anfang aus weitermachen.)
• In Stücken füllen. Importiere 50.000 Zeilen auf einmal: Sammle sie am Ende und kehre das Array einmal um. Wie viele Schreibvorgänge sind das?

Test

Teste dich

1. Ein dynamisches Array hat 1000 Elemente. Wie viele Elemente verschiebt ein Einfügen an Index 0? Und an Index 990?

1000 und 101000 und 10001 und 1

2. Warum ist Lesen per Index auch bei einer Million Elementen O(1)?

Die Adresse wird berechnet: Start + Index × Größe eines PlatzesDas Array merkt sich in einer eigenen Tabelle, wo jedes Element liegtWeil das Array sortiert ist

3. Das Array hat Kapazität 8 und Größe 5. Was passiert bei get(6)?

Das Array wächst auf 16Ein Fehler wegen eines Index außerhalb der Grenzen, obwohl es Platz 6 gibtEs gibt einen leeren Platz zurück

4. Warum halbiert sich das Array erst, wenn es zu einem Viertel gefüllt ist, und nicht schon bei der Hälfte?

Weil Speicher nur in Vierteln freigegeben wirdBei der Grenze „Hälfte“ würde abwechselndes Hinzufügen und Entfernen genau dort jedes Mal verkleinern und vergrößern, und jedes Mal kopiert allesWeil Verkleinern langsam ist

5. Der Warenkorb soll das zuletzt hinzugefügte Produkt ganz oben zeigen. Was ist die schnelle Lösung?

Nach jedem Hinzufügen sortierenAn Index 0 einfügenAm Ende anhängen und von hinten nach vorn anzeigen

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Big-O: wie die Arbeit wächst · Bester, durchschnittlicher und schlechtester Fall · Speicherkomplexität · Amortisierte Komplexität
• Geht weiter in: Verkettete Liste · Stapel und Warteschlange · Hashtabelle
• Aufgaben zum Thema: Datenstrukturen