Das dynamische Array von innen

Code in:JavaC#PythonJavaScript

Kurz gesagt: Ein dynamisches Array (List<T> in C#) 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.

string[] orderLines = { "Mehl 25 kg", "Zucker 10 kg", "Öl 5 l", "Reis 10 kg" };
var cart = new List<string>();
foreach (string line in orderLines)
{
    cart.Insert(0, line);
}
Console.WriteLine("Der Warenkorb: " + string.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<T> 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
{
    private string[] items = new string[8];
    private int size = 0;

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        CheckIndex(index, size + 1);
        if (size == items.Length)
        {
            Grow();
        }
        for (int i = size; i > index; i--)
        {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    public string RemoveAt(int index)
    {
        CheckIndex(index, size);
        string removed = items[index];
        for (int i = index; i < size - 1; i++)
        {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void Grow()
    {
        string[] bigger = new string[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[i];
        }
        items = bigger;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

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

public void Insert(int index, string value)
{
    CheckIndex(index, size + 1);
    if (size == items.Length)
    {
        Grow();
    }
    for (int i = size; i > index; i--)
    {
        items[i] = items[i - 1];
    }
    items[index] = value;
    size++;
}

public string RemoveAt(int index)
{
    CheckIndex(index, size);
    string removed = items[index];
    for (int i = index; i < size - 1; i++)
    {
        items[i] = items[i + 1];
    }
    size--;
    items[size] = null;
    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. RemoveAt(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 null: 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 ArgumentOutOfRangeException.
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.

var cart = new DynamicArray();
cart.Add("Brot");
cart.Add("Milch");
cart.Add("Kaffee");
cart.Add("Butter");
cart.Add("Äpfel");
Console.WriteLine(cart[3]);
cart.Insert(0, "Käse");
cart.RemoveAt(2);
for (int i = 0; i < cart.Count; i++)
{
    Console.WriteLine(i + ": " + cart[i]);
}
Console.WriteLine("Plätze: " + cart.Capacity);
try
{
    Console.WriteLine(cart[5]);
}
catch (ArgumentOutOfRangeException e)
{
    Console.WriteLine("Fehler: " + e.Message);
}

Ausgabe

Butter
0: Käse
1: Brot
2: Kaffee
3: Butter
4: Äpfel
Plätze: 8
Fehler: Specified argument was out of the range of valid values. (Parameter 'index')

this[int index] ist ein Indexer: Dank ihm schreibst du cart[3] wie bei einem Array. List<T> ist genauso gebaut.

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
{
    private string[] items = new string[8];
    private int size = 0;

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        CheckIndex(index, size + 1);
        if (size == items.Length)
        {
            Grow();
        }
        for (int i = size; i > index; i--)
        {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    public string RemoveAt(int index)
    {
        CheckIndex(index, size);
        string removed = items[index];
        for (int i = index; i < size - 1; i++)
        {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void Grow()
    {
        string[] bigger = new string[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[i];
        }
        items = bigger;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

var cart = new DynamicArray();
for (int i = 1; i <= 8; i++)
{
    cart.Add("P" + i);
}
cart.Insert(0, "P0");
Console.WriteLine("Produkte: " + cart.Count);
Console.WriteLine("Plätze: " + cart.Capacity);
Console.WriteLine(cart[8]);

Antwort

Produkte: 9
Plätze: 9
P8

Produkte: 9
Plätze: 16
P0

Produkte: 9
Plätze: 16
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):

string[] orderLines = { "Mehl 25 kg", "Zucker 10 kg", "Öl 5 l", "Reis 10 kg" };
var cart = new List<string>();
foreach (string line in orderLines)
{
    cart.Add(line);
}
var newestFirst = Enumerable.Reverse(cart);
Console.WriteLine("Der Warenkorb: " + string.Join(", ", newestFirst));

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
{
    private string[] items = new string[8];
    private int size = 0;

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        CheckIndex(index, size + 1);
        if (size == items.Length)
        {
            Grow();
        }
        for (int i = size; i > index; i--)
        {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    public string RemoveAt(int index)
    {
        CheckIndex(index, size);
        string removed = items[index];
        for (int i = index; i < size - 1; i++)
        {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void Grow()
    {
        string[] bigger = new string[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[i];
        }
        items = bigger;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

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

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        CheckIndex(index, size + 1);
        if (size == items.Length)
        {
            Grow();
        }
        for (int i = size; i > index; i--)
        {
            items[i] = items[i - 1];
            Writes++;
        }
        items[index] = value;
        Writes++;
        size++;
    }

    public string RemoveAt(int index)
    {
        CheckIndex(index, size);
        string removed = items[index];
        for (int i = index; i < size - 1; i++)
        {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void Grow()
    {
        string[] bigger = new string[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[i];
            Writes++;
        }
        items = bigger;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

foreach (int n in new[] { 10, 1000, 100000 })
{
    var cart = new DynamicArray();
    for (int i = 0; i < n; i++)
    {
        cart.Add((1001 + i).ToString());
    }
    Console.WriteLine($"am Ende, n = {n}: {cart.Writes} Schreibvorgänge");
}
foreach (int n in new[] { 10, 1000 })
{
    var cart = new DynamicArray();
    for (int i = 0; i < n; i++)
    {
        cart.Insert(0, (1001 + i).ToString());
    }
    Console.WriteLine($"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:

var cart = new DynamicArray();
cart.Add("Brot");
cart.Add("Milch");
cart.Add("Kaffee");
cart.Insert(0, "Käse");
for (int i = 0; i < cart.Count; i++)
{
    Console.WriteLine(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 DynamicArray2{3 private string[] items = new string[8];4 private int size = 0;56 public int Count => size;78 public int Capacity => items.Length;910 public string this[int index]11 {12 get13 {14 CheckIndex(index, size);15 return items[index];16 }17 set18 {19 CheckIndex(index, size);20 items[index] = value;21 }22 }2324 public void Add(string value)25 {26 Insert(size, value);27 }2829 public void Insert(int index, string value)30 {31 CheckIndex(index, size + 1);32 if (size == items.Length)33 {34 Grow();35 }36 for (int i = index; i < size; i++)37 {38 items[i + 1] = items[i];39 }40 items[index] = value;41 size++;42 }4344 public string RemoveAt(int index)45 {46 CheckIndex(index, size);47 string removed = items[index];48 for (int i = index; i < size - 1; i++)49 {50 items[i] = items[i + 1];51 }52 size--;53 items[size] = null;54 return removed;55 }5657 private void Grow()58 {59 string[] bigger = new string[items.Length * 2];60 for (int i = 0; i < size; i++)61 {62 bigger[i] = items[i];63 }64 items = bigger;65 }6667 private void CheckIndex(int index, int limit)68 {69 if (index < 0 || index >= limit)70 {71 throw new ArgumentOutOfRangeException(nameof(index));72 }73 }74}

Prüfen

Probier es aus

Ergänze

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

public string RemoveAt(int index)
{
    CheckIndex(index, size);
    string removed = items[index];
    for (int i = index; i < size - 1; i++)
    {
        items[i] = items[];
    }
    size--;
    items[size] = null;
    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. Capacity bleibt, bis du TrimExcess() aufrufst.
• Python (CPython) schrumpft von selbst unter der Hälfte;
• 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: - int[] und List<int> halten die Zahlen selbst nebeneinander. string[] und List<string> halten Referenzen nebeneinander, und die Objekte selbst liegen woanders im Speicher. Das Durchlaufen der Referenzen ist schnell, aber jedes Lesen eines Objekts kann ein Sprung sein.

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(int 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. RemoveAt 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 IndexOf(string value) hinzu, das den Index oder -1 zurückgibt, und Remove(string 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