Amortisierte Komplexität in Python

Problem

Der Import, der alles kopiert

Der Shop importiert die Bestellungen aus einem alten System, eine nach der anderen. Jemand hat den Import so geschrieben, dass das Array mit jeder Bestellung einen Platz größer wird:

def import_orders(n):
    orders = []
    copies = 0
    for i in range(n):
        copies += len(orders)
        orders = orders + [100000 + i]
    return copies

Es sieht harmlos aus: eine Zeile pro Bestellung. Aber jedes neue Array ist eine Kopie des alten plus ein Platz. Das Programm zählt die Kopien:

for n in [1000, 10000]:
    print(f"{n} Bestellungen: {import_orders(n)} Kopien")

1000 Bestellungen: 499500 Kopien
10000 Bestellungen: 49995000 Kopien

Bei 10-mal so vielen Bestellungen gibt es 100-mal so viele Kopien. Bei 100.000 Bestellungen sind es 4.999.950.000, und der Import, der im Test einen Augenblick dauert, läuft jetzt Minuten. Dabei ist list.append mit denselben 100.000 Bestellungen sofort fertig, obwohl es auch manchmal das ganze Array kopiert. Wie geht das?

Die Idee

Die Liste wächst nicht um einen Platz

Innen ist eine Liste ein Array mit mehr Plätzen als Elementen. Wenn es voll ist, legt sie ein neues, größeres Array an und kopiert alles hinein:

cart = ["Brot", "Milch", "Kaffee", "Butter"]
cart.append("Käse")
cart.remove("Milch")
print(cart)
print("Artikel:", len(cart))

Schritt für Schritt, in Worten

cart zeigt auf ein Listenobjekt. Darin liegen ein Zähler ob_size und ein Array ob_item mit 4 Plätzen.
Die Artikel aus dem Code füllen die Plätze nacheinander. Das Array ist voll: 4 von 4.
Es ist kein Platz mehr. append reserviert ein Array mit 8 Plätzen, und die Elemente kommen hinein.
ob_item zeigt jetzt auf das neue Array. „Käse“ kommt auf den ersten freien Platz.
remove entfernt „Milch“, und alles danach rückt einen Platz nach links. Es bleibt keine Lücke.
Von außen siehst du nur eine Liste mit vier Artikeln. Wie viele Plätze sie innen hat, entscheidet CPython: Die Sprache verspricht es nicht.

Das Geheimnis ist, wie viel größer das neue Array ist. Hat es einen Platz mehr, kopiert jedes Hinzufügen nach dem vollen Array alles, wie beim Import oben. Ist es doppelt so groß, kommt die nächste Kopie erst nach noch einmal so vielen Hinzufügungen.

Sieh es dir an

Dein eigenes Array, das sich verdoppelt

Hier ist derselbe Mechanismus von Hand geschrieben, mit einem Zähler für die Kopien. Das Array beginnt mit einem Platz:

class OrderList:
    def __init__(self):
        self.items = [None]
        self.size = 0
        self.copies = 0

    def add(self, order):
        if self.size == len(self.items):
            bigger = [None] * (len(self.items) * 2)
            for i in range(self.size):
                bigger[i] = self.items[i]
                self.copies += 1
            self.items = bigger
        self.items[self.size] = order
        self.size += 1

for n in [9, 1000]:
    orders = OrderList()
    for i in range(n):
        orders.add(100000 + i)
    print(f"{n} Bestellungen: {orders.copies} Kopien, 2n = {2 * n}")

9 Bestellungen: 15 Kopien, 2n = 18
1000 Bestellungen: 1023 Kopien, 2n = 2000

class OrderList:
    def __init__(self):
        self.items = [None]
        self.size = 0
        self.copies = 0

    def add(self, order):
        if self.size == len(self.items):
            bigger = [None] * (len(self.items) * 2)
            for i in range(self.size):
                bigger[i] = self.items[i]
                self.copies += 1
            self.items = bigger
        self.items[self.size] = order
        self.size += 1

orders = OrderList()
for i in range(9):
    orders.add(100000 + i)

Schritt für Schritt, in Worten

Das Array beginnt mit einem Platz, und size ist 0. Wir zählen nur die Kopien alter Elemente.
Die erste Bestellung: Es ist Platz da, add schreibt sie hinein. Kopien: 0.
Die zweite: Das Array ist voll. Ein neues Array mit 2 Plätzen, und die alte Bestellung wird hineinkopiert: 1 Kopie.
Die dritte: wieder voll, 4 Plätze und 2 Kopien. Die vierte kommt ohne Kopieren hinein.
Die fünfte kopiert 4, die neunte 8. Die Kopien wachsen, aber zwischen ihnen kommen immer mehr Hinzufügungen ohne Kopieren.
9 Hinzufügungen, 1 + 2 + 4 + 8 = 15 Kopien, weniger als 2n = 18. Auf alle Hinzufügungen verteilt, sind das weniger als 2 pro Hinzufügung: amortisiert O(1).

Ein Hinzufügen, das das Array voll findet, kopiert alles: 1, 2, 4, 8, 16 … Aber danach kommen so viele Hinzufügungen ohne Kopieren, wie es kopiert hat. Die Summe 1 + 2 + 4 + … + 2ᵏ ist immer kleiner als 2 · 2ᵏ, und die letzte Kopie 2ᵏ ist kleiner als n. Die Kopien sind also unter 2n, egal wie groß n ist.

Die Idee

Amortisierte Komplexität

Ein Hinzufügen kann O(n) kosten: das, das alles kopiert. Aber n Hinzufügungen kosten zusammen weniger als 3n Operationen: n Schreibvorgänge und weniger als 2n Kopien. Geteilt durch n sind das weniger als 3 pro Hinzufügen: O(1).

Die Kosten, verteilt auf eine ganze Folge von Operationen, heißen amortisierte Komplexität. Das Hinzufügen am Ende einer Liste ist amortisiert O(1).

Das ist nicht „im Schnitt bei zufälliger Eingabe“. Das Versprechen gilt für jede Folge von Hinzufügungen, ohne Glück: Die teuren sind selten, und zwar immer so selten.

Probier es aus

Sag die Ausgabe voraus

Fünf Bestellungen in einem Array, das mit einem Platz beginnt und sich verdoppelt. Wie viele Kopien?

class OrderList:
    def __init__(self):
        self.items = [None]
        self.size = 0
        self.copies = 0

    def add(self, order):
        if self.size == len(self.items):
            bigger = [None] * (len(self.items) * 2)
            for i in range(self.size):
                bigger[i] = self.items[i]
                self.copies += 1
            self.items = bigger
        self.items[self.size] = order
        self.size += 1


for n in [5]:
    orders = OrderList()
    for i in range(n):
        orders.add(100000 + i)
    print(f"{n} Bestellungen: {orders.copies} Kopien")

Antwort

5 Bestellungen: 10 Kopien

5 Bestellungen: 4 Kopien

5 Bestellungen: 7 Kopien

Sieh es dir an

Ein Platz mehr: O(n²)

Dieselbe Klasse, nur dass das neue Array einen Platz mehr hat:

bigger = [None] * (len(self.items) + 1)

for n in [9, 1000]:
    orders = OrderList()
    for i in range(n):
        orders.add(100000 + i)
    print(f"{n} Bestellungen: {orders.copies} Kopien")

9 Bestellungen: 36 Kopien
1000 Bestellungen: 499500 Kopien

Bei 1000 Bestellungen kopiert das Verdoppeln 1023-mal, das Wachstum um einen Platz 499.500-mal: 1 + 2 + … + 999. Lass beide Arten wachsen und sieh dir die Kurven an. Wir zählen nur die Kopien:

Wachstum ×2: Kopien O(n)
Wachstum +1: Kopien O(n²)

Algorithmus	n = 10	n = 1.000	n = 100.000
Wachstum ×2: Kopien	15	1.023	131.071
Wachstum +1: Kopien	45	499.500	≈ 4.995.000.000

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.

Das Verdoppeln wächst wie eine Gerade: insgesamt O(n), pro Hinzufügen O(1). Das Wachstum um einen Platz wächst wie eine Parabel: insgesamt O(n²), pro Hinzufügen O(n).

Probier es aus

Ergänze

Wie viele Plätze hat das neue Array, damit das Hinzufügen amortisiert O(1) ist?

if self.size == len(self.items):
    bigger = [None] * ()

Probier es aus

Finde den Fehler

Ein Kollege hat das Verdoppeln ersetzt, „damit kein Speicher verschwendet wird“. Bei 1000 Bestellungen läuft der Test schnell durch, und der nächtliche Import mit 100.000 zieht sich hin:

for n in [1000, 100000]:
    orders = OrderList()
    for i in range(n):
        orders.add(100000 + i)
    print(f"{n} Bestellungen: {orders.copies} Kopien")

1000 Bestellungen: 4510 Kopien
100000 Bestellungen: 49951000 Kopien

Bei 100-mal so vielen Bestellungen gibt es 10.000-mal so viele Kopien. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Wie jede Sprache wächst

Keine Sprache verdoppelt genau, aber jede multipliziert:

Java ArrayList: ×1,5;
C# List<T>: ×2;
Python (CPython 3.12): Die neue Größe ist n + n/8 + 6, abgerundet auf ein Vielfaches von 4. Das ist etwa ×1,125. Die Sprache verspricht es nicht; CPython entscheidet.
JavaScript (V8): etwa ×1,5.

Jeder Faktor über 1 ergibt amortisiert O(1). Je kleiner er ist, desto mehr Kopien (unter 3n bei ×1,5, unter 9n bei ×1,125) und desto weniger leere Plätze nach einem Wachstum. Die Wahl ist ein Tausch zwischen Zeit und Speicher, wie in der Lektion „Speicherkomplexität“.

Wie viele Plätze die Liste bei jedem Wachstum hat, bei 1000 Hinzufügungen:

import sys


def places(items):
    return (sys.getsizeof(items) - sys.getsizeof([])) // 8


orders = []
seen = []
for i in range(1000):
    orders.append(100000 + i)
    if not seen or seen[-1] != places(orders):
        seen.append(places(orders))
print("Die Plätze bei jedem Wachstum:", " ".join(str(p) for p in seen))

Die Plätze bei jedem Wachstum: 4 8 16 24 32 40 52 64 76 92 108 128 148 172 200 232 268 308 352 400 456 520 592 672 760 860 972 1100

Genauer, für Neugierige

Amortisiert O(1) heißt nicht, dass jedes Hinzufügen schnell ist. Das Hinzufügen, das kopiert, ist O(n). In den meisten Programmen merkst du es nicht, aber in einem Programm, das nicht stehen bleiben darf (eine Kasse, ein Spiel, Audiobearbeitung), kann das Hinzufügen des millionsten Elements das langsame sein. Wenn du weißt, wie viele Elemente es werden, lege die Plätze im Voraus fest: [None] * n. Dann kopiert die Liste nie.

[None] * n erzeugt eine Liste mit n None-Elementen, und dann schreibst du über den Index, nicht mit append.

Die Grenze für ×2 hat noch eine andere Form: Jedes Hinzufügen „zahlt“ 2 Kopien im Voraus und spart sie an. Wenn das Array mit k Elementen voll wird, haben die letzten k/2 Hinzufügungen k angespart, genau das, was die Kopie kostet. Das Ersparte wird nie negativ, also bleibt die Summe unter 2n.

Übung

Wachstum wie in Java

Löse die Aufgabe in deinem Editor.

Wachstum um die Hälfte. Ändere das Wachstum von OrderList so, dass das neue Array die alten Plätze plus die Hälfte hat (mindestens einen Platz mehr). Zähle die Kopien bei 1000 und bei 100.000 Bestellungen. Sind sie unter 2n? Und unter 3n?

1000 Bestellungen: 2137 Kopien, 2n = 2000
100000 Bestellungen: 276521 Kopien, 2n = 200000

Weitere Aufgaben

Vom Ende entfernen. Füge removeLast hinzu. Wann soll das Array schrumpfen, damit auch das Entfernen amortisiert O(1) ist? Probiere „um die Hälfte, wenn es halb voll ist“ und wechsle genau an der Grenze zwischen Hinzufügen und Entfernen. Probiere dann „um die Hälfte, wenn es zu einem Viertel voll ist“. Warum ist das zweite amortisiert O(1) und das erste nicht?
Wie viele Plätze verschwendet werden. Wie viele Plätze sind nach 1000 Hinzufügungen mit Verdoppeln leer? Und bei Wachstum ×1,5?

Test

Teste dich

1. Ein Array verdoppelt sich, wenn es voll ist. Wie viele Kopien machen 1000 Hinzufügungen insgesamt, wenn es mit 1 Platz beginnt?Weniger als 2000Genau 10001000 × 1000

2. Was bedeutet „Hinzufügen ist amortisiert O(1)“?Jedes Hinzufügen ist schnelln Hinzufügungen kosten zusammen O(n), obwohl eine davon alles kopiertHinzufügen ist im Schnitt bei zufälliger Eingabe schnell

3. Ein Kollege ändert das Wachstum von ×2 auf +1000 Plätze, „damit kein Speicher verschwendet wird“. Was passiert bei einer Million Hinzufügungen?Nichts, 1000 sind viele PlätzeEs wird schneller, weil das Array kleiner istDie Kopien werden etwa n²/2000: eine halbe Milliarde statt etwa einer Million

4. Warum wächst Java um ×1,5 und nicht um ×2 oder ×10?Weil ×1,5 für den Prozessor schneller istNur ×1,5 ergibt amortisiert O(1)Je größer der Faktor, desto weniger Kopien, aber desto mehr leere Plätze nach einem Wachstum

5. Ein Programm für die Kasse darf pro Hinzufügen nicht länger als eine Millisekunde stehen bleiben. Was tust du?Du legst die Plätze im Voraus fest, wenn du weißt, wie viele Elemente es werdenDu wechselst zum Wachstum +1Nichts, Hinzufügen ist O(1)

Amortisierte Komplexität

Cookies