Amortisierte Komplexität

Code in:JavaC#PythonJavaScript

Kurz gesagt: Amortisierte Komplexität sind die durchschnittlichen Kosten einer Operation in einer langen Folge: Das Hinzufügen zu einem dynamischen Array kopiert manchmal alles, aber weil das Array um einen Faktor wächst (zum Beispiel ×2), ist es im Schnitt O(1).

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:

static long ImportOrders(int n)
{
    int[] orders = new int[0];
    long copies = 0;
    for (int i = 0; i < n; i++)
    {
        copies += orders.Length;
        Array.Resize(ref orders, orders.Length + 1);
        orders[^1] = 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:

foreach (int n in new[] { 1000, 10000 })
{
    Console.WriteLine(n + " Bestellungen: " + ImportOrders(n) + " Kopien");
}

Ausgabe

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.Add 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:

List<string> cart = new List<string>(3);
cart.Add("Brot");
cart.Add("Milch");
cart.Add("Kaffee");
cart.Add("Butter");
cart.Remove("Milch");
Console.WriteLine(string.Join(", ", cart));
Console.WriteLine("Artikel: " + cart.Count);

Schritt für Schritt, in Worten

1. cart zeigt auf ein List<string>-Objekt. Darin liegen ein Array _items mit 3 Plätzen und ein Zähler _size.
2. Add legt jedes Element auf den ersten freien Platz und erhöht _size.
3. Das Array ist voll. List<T> legt ein neues mit 6 Plätzen an, doppelt so vielen, und kopiert die drei Elemente hinein.
4. _items zeigt jetzt auf das neue Array, das alte braucht niemand mehr. „Butter“ kommt auf den freien Platz.
5. Remove entfernt „Milch“, und alles danach rückt einen Platz nach links. Es bleibt keine Lücke.
6. Von außen siehst du nur eine Liste mit drei Artikeln: Das Kopieren und Verschieben erledigt List<T>. Capacity sagt dir, wie viele Plätze sie hat.

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
{
    private int[] items = new int[1];
    private int size = 0;
    public long Copies { get; private set; }

    public void Add(int order)
    {
        if (size == items.Length)
        {
            int[] bigger = new int[items.Length * 2];
            for (int i = 0; i < size; i++)
            {
                bigger[i] = items[i];
                Copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}

foreach (int n in new[] { 9, 1000 })
{
    var orders = new OrderList();
    for (int i = 0; i < n; i++)
    {
        orders.Add(100000 + i);
    }
    Console.WriteLine(n + " Bestellungen: " + orders.Copies + " Kopien" + ", 2n = " + 2 * n);
}

Ausgabe

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

class OrderList
{
    private int[] items = new int[1];
    private int size = 0;
    public long Copies { get; private set; }

    public void Add(int order)
    {
        if (size == items.Length)
        {
            int[] bigger = new int[items.Length * 2];
            for (int i = 0; i < size; i++)
            {
                bigger[i] = items[i];
                Copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}

var orders = new OrderList();
for (int i = 0; i < 9; i++)
{
    orders.Add(100000 + i);
}

Schritt für Schritt, in Worten

1. Das Array beginnt mit einem Platz, und size ist 0. Wir zählen nur die Kopien alter Elemente.
2. Die erste Bestellung: Es ist Platz da, Add schreibt sie hinein. Kopien: 0.
3. Die zweite: Das Array ist voll. Ein neues Array mit 2 Plätzen, und die alte Bestellung wird hineinkopiert: 1 Kopie.
4. Die dritte: wieder voll, 4 Plätze und 2 Kopien. Die vierte kommt ohne Kopieren hinein.
5. Die fünfte kopiert 4, die neunte 8. Die Kopien wachsen, aber zwischen ihnen kommen immer mehr Hinzufügungen ohne Kopieren.
6. 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
{
    private int[] items = new int[1];
    private int size = 0;
    public long Copies { get; private set; }

    public void Add(int order)
    {
        if (size == items.Length)
        {
            int[] bigger = new int[items.Length * 2];
            for (int i = 0; i < size; i++)
            {
                bigger[i] = items[i];
                Copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}

foreach (int n in new[] { 5 })
{
    var orders = new OrderList();
    for (int i = 0; i < n; i++)
    {
        orders.Add(100000 + i);
    }
    Console.WriteLine(n + " Bestellungen: " + orders.Copies + " Kopien");
}

Antwort

5 Bestellungen: 4 Kopien

5 Bestellungen: 7 Kopien

5 Bestellungen: 10 Kopien

Prüfen

Sieh es dir an

Ein Platz mehr: O(n²)

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

int[] bigger = new int[items.Length + 1];

foreach (int n in new[] { 9, 1000 })
{
    var orders = new OrderList();
    for (int i = 0; i < n; i++)
    {
        orders.Add(100000 + i);
    }
    Console.WriteLine(n + " Bestellungen: " + orders.Copies + " Kopien");
}

Ausgabe

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 (size == items.Length)
{
    int[] bigger = new int[];

Prüfen

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:

foreach (int n in new[] { 1000, 100000 })
{
    var orders = new OrderList();
    for (int i = 0; i < n; i++)
    {
        orders.Add(100000 + i);
    }
    Console.WriteLine(n + " Bestellungen: " + orders.Copies + " Kopien");
}

Ausgabe

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.

1class OrderList2{3 private int[] items = new int[1];4 private int size = 0;5 public long Copies { get; private set; }67 public void Add(int order)8 {9 if (size == items.Length)10 {11 int[] bigger = new int[items.Length + 100];12 for (int i = 0; i < size; i++)13 {14 bigger[i] = items[i];15 Copies++;16 }17 items = bigger;18 }19 items[size] = order;20 size++;21 }22}

Prüfen

Die Idee

Wie jede Sprache wächst

Keine Sprache verdoppelt genau, aber jede multipliziert:

• Java ArrayList: ×1,5;
• C# List<T>: ×2. Eine leere bekommt beim ersten Add 4 Plätze, und Capacity sagt, wie viele Plätze sie hat.
• Python (CPython): etwa ×1,125;
• 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:

var orders = new List<int>();
var seen = new List<int>();
for (int i = 0; i < 1000; i++)
{
    orders.Add(100000 + i);
    if (seen.Count == 0 || seen[^1] != orders.Capacity)
    {
        seen.Add(orders.Capacity);
    }
}
Console.WriteLine("Die Plätze bei jedem Wachstum: " + string.Join(" ", seen));

Ausgabe

Die Plätze bei jedem Wachstum: 4 8 16 32 64 128 256 512 1024

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: new List<int>(n). Dann kopiert die Liste nie.

List<T> hat für eine schon vorhandene Liste auch EnsureCapacity(n).

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?

Ausgabe

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)

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Zeitkomplexität: Schritte zählen · Big-O: wie die Arbeit wächst · Bester, durchschnittlicher und schlechtester Fall · Speicherkomplexität
• Geht weiter in: Das dynamische Array von innen · Verkettete Liste · Stapel und Warteschlange · Hashtabelle
• Aufgaben zum Thema: Komplexität