Speicherkomplexität in C#

Problem

Der Export, der den Speicher auffrisst

Jede Nacht exportiert ein Dienst die Logs des Tages des Shops in ein Archiv. Damit er nach einem Absturz dort weitermachen kann, wo er aufgehört hat, schreibt er nach jeder Zeile einen Checkpoint. Nur ist der Checkpoint eine Kopie der ganzen Datei bis dahin:

static long ExportLogs(List<string> logs)
{
    var file = new List<string>();
    var checkpoints = new List<List<string>>();
    foreach (string line in logs)
    {
        file.Add(line);
        checkpoints.Add(new List<string>(file));
    }
    long places = 0;
    foreach (List<string> saved in checkpoints)
    {
        places += saved.Count;
    }
    return places;
}

Wie viele Plätze belegen die Kopien? Das Programm zählt sie:

foreach (int n in new[] { 5, 1000 })
{
    var logs = new List<string>();
    for (int i = 1; i <= n; i++)
    {
        logs.Add("Zeile " + i);
    }
    Console.WriteLine(n + " Zeilen: " + ExportLogs(logs) + " Plätze");
}

5 Zeilen: 15 Plätze
1000 Zeilen: 500500 Plätze

Bei 1000 Zeilen sind es 500.500 Plätze. Die Logs eines Tages sind 100.000 Zeilen, und das sind 5.000.050.000 Plätze. Jeder Platz hält eine Referenz von 4 bis 8 Byte: zwischen 20 und 40 GB nur für die Kopien. Im Test mit 1000 Zeilen läuft alles durch, und nachts bricht der Export mit OutOfMemoryException ab.

Die Idee

Auch Speicher kostet

Bisher hast du Operationen gezählt. Speicher zählt man genauso: wie viele Plätze der Algorithmus selbst anlegt, abgesehen von der Eingabe, die er bekommt. Das ist die Speicherkomplexität des Algorithmus. Sie wird ebenfalls mit Big-O geschrieben:

O(1): ein paar Variablen, egal wie groß die Eingabe ist;
O(n): eine Kopie der Eingabe, eine Hilfsliste, ein Set mit allen Elementen;
O(n²): bei jedem Schritt eine Kopie der Kopie, wie im Export.

Die Eingabe zählt nicht, weil es sie auch ohne den Algorithmus gibt. Das Ergebnis, das die Aufgabe verlangt, zählt ebenfalls nicht: Die Datei mit n Zeilen ist die Aufgabe des Exports. Zählen tun die Kopien, die er unterwegs macht.

Sieh es dir an

Die Kopien bleiben

var file = new List<string>();
int checkpoint = 0;
foreach (string line in logs)
{
    file.Add(line);
    checkpoint = file.Count;
}

Schritt für Schritt, in Worten

file ist die Datei, die der Export schreibt, und logs hat 4 Zeilen. checkpoints merkt sich, wo es nach einem Absturz weitergeht.
Zeile 1 kommt in die Datei. Der Checkpoint ist eine Kopie der ganzen Datei: 1 Platz.
Zeile 2. Der neue Checkpoint kopiert beide Zeilen, und der alte bleibt in der Liste: 1 + 2 = 3 Plätze.
Nach 4 Zeilen belegt der Speicher 1 + 2 + 3 + 4 = 10 Plätze. Nach n Zeilen sind es n(n + 1)/2: fünf Milliarden bei 100 000 Zeilen.
Um nach einem Absturz weiterzumachen, brauchst du nur, wie weit du gekommen bist. Die Kopien verschwinden, eine Zahl bleibt.
Jede Zeile ändert die Zahl: checkpoint = 4. Der zusätzliche Speicher ist 1 Platz, egal wie viele Zeilen es sind.

Jede Kopie ist eine neue Liste im Speicher, und die alten löscht niemand: Die Liste checkpoints hält sie fest. Deshalb wachsen die Plätze wie 1 + 2 + 3 + … + n. Um nach einem Absturz weiterzumachen, braucht der Export nur zu wissen, wie weit er gekommen ist:

static int ExportLogs(List<string> logs)
{
    var file = new List<string>();
    int checkpoint = 0;
    foreach (string line in logs)
    {
        file.Add(line);
        checkpoint = file.Count;
    }
    return checkpoint;
}

foreach (int n in new[] { 5, 1000 })
{
    var logs = new List<string>();
    for (int i = 1; i <= n; i++)
    {
        logs.Add("Zeile " + i);
    }
    Console.WriteLine(n + " Zeilen, checkpoint: " + ExportLogs(logs));
}

5 Zeilen, checkpoint: 5
1000 Zeilen, checkpoint: 1000

Die Datei ist dieselbe, und der zusätzliche Speicher ist eine Zahl: O(1) statt O(n²).

Probier es aus

Sag die Ausgabe voraus

Der Export mit den Kopien bekommt 6 Zeilen. Wie viele Plätze belegen die Checkpoints?

static long ExportLogs(List<string> logs)
{
    var file = new List<string>();
    var checkpoints = new List<List<string>>();
    foreach (string line in logs)
    {
        file.Add(line);
        checkpoints.Add(new List<string>(file));
    }
    long places = 0;
    foreach (List<string> saved in checkpoints)
    {
        places += saved.Count;
    }
    return places;
}

foreach (int n in new[] { 6 })
{
    var logs = new List<string>();
    for (int i = 1; i <= n; i++)
    {
        logs.Add("Zeile " + i);
    }
    Console.WriteLine(n + " Zeilen: " + ExportLogs(logs) + " Plätze");
}

Antwort

6 Zeilen: 21 Plätze

6 Zeilen: 36 Plätze

6 Zeilen: 6 Plätze

Sieh es dir an

Eine Kopie oder an Ort und Stelle

Der Admin möchte die neuesten Log-Zeilen zuerst. Es gibt zwei Wege. Der eine macht eine neue Liste in umgekehrter Reihenfolge, der andere vertauscht die Elemente in der Liste selbst: das erste mit dem letzten, das zweite mit dem vorletzten, bis sich die beiden Enden treffen.

static List<string> NewestFirst(List<string> logs)
{
    var result = new List<string>();
    for (int i = logs.Count - 1; i >= 0; i--)
    {
        result.Add(logs[i]);
    }
    return result;
}

static void ReverseInPlace(List<string> logs)
{
    int left = 0;
    int right = logs.Count - 1;
    while (left < right)
    {
        (logs[left], logs[right]) = (logs[right], logs[left]);
        left++;
        right--;
    }
}

var logs = new List<string> { "09:00 Anmeldung", "09:05 Warenkorb", "09:07 Zahlung" };
List<string> newest = NewestFirst(logs);
Console.WriteLine("Kopie:    " + string.Join(", ", newest));
Console.WriteLine("Original: " + string.Join(", ", logs));
ReverseInPlace(logs);
Console.WriteLine("Direkt:   " + string.Join(", ", logs));

Kopie:    09:07 Zahlung, 09:05 Warenkorb, 09:00 Anmeldung
Original: 09:00 Anmeldung, 09:05 Warenkorb, 09:07 Zahlung
Direkt:   09:07 Zahlung, 09:05 Warenkorb, 09:00 Anmeldung

Die Kopie braucht n neue Plätze, aber das Original bleibt, wie es war. Die Änderung an Ort und Stelle braucht einen Platz für den Tausch, aber die alte Reihenfolge ist weg. Was besser ist, hängt davon ab, ob noch jemand das Original liest.

Genauer, für Neugierige

Die eingebauten Funktionen treffen dieselbe Wahl, und der Name verrät sie nicht immer:

var logs = new List<string> { "09:00 Anmeldung", "09:05 Warenkorb", "09:07 Zahlung" };
List<string> copy = Enumerable.Reverse(logs).ToList();
logs.Reverse();
Console.WriteLine("Direkt:   " + string.Join(", ", logs));
Console.WriteLine("Kopie:    " + string.Join(", ", copy));

Direkt:   09:07 Zahlung, 09:05 Warenkorb, 09:00 Anmeldung
Kopie:    09:07 Zahlung, 09:05 Warenkorb, 09:00 Anmeldung

List<T>.Reverse() kehrt an Ort und Stelle um. Enumerable.Reverse aus LINQ tut nichts, bis du es liest, und ToList() macht die Kopie. Auch GetRange kopiert.

Die Kopie ist flach: Die neue Liste hält Referenzen auf dieselben Texte, keine neuen Texte. Deshalb zählen die Plätze einen pro Element.

Probier es aus

Ergänze

Vervollständige den Tausch der beiden Enden:

(logs[left], logs[right]) = (logs[right], );

Sieh es dir an

Auch Rekursion hält Speicher

Nicht nur eine Liste braucht Platz. Jeder Aufruf einer Methode hält seine Parameter und lokalen Variablen auf dem Aufrufstapel, bis er zurückkehrt. Hier werden die Fehler im Log mit Rekursion und mit einer Schleife gezählt:

static int ErrorsFrom(List<string> logs, int i)
{
    if (i == logs.Count)
    {
        return 0;
    }
    int here = logs[i].StartsWith("ERROR") ? 1 : 0;
    return here + ErrorsFrom(logs, i + 1);
}

static int Errors(List<string> logs)
{
    int count = 0;
    foreach (string line in logs)
    {
        if (line.StartsWith("ERROR"))
        {
            count++;
        }
    }
    return count;
}

List<string> small = MakeLogs(500);
List<string> big = MakeLogs(1_000_000);
Console.WriteLine("500 Zeilen: " + ErrorsFrom(small, 0) + " Fehler");
Console.WriteLine("Mit Schleife: " + Errors(big) + " Fehler");

500 Zeilen: 5 Fehler
Mit Schleife: 10000 Fehler

Die Rekursion erzeugt keine einzige Liste, aber bei n Zeilen liegen n unfertige Aufrufe auf dem Stapel: O(n) Speicher. Der Stapel ist klein, und eine Million Aufrufe passen nicht hinein. Die Schleife hat eine Variable count: O(1).

In C# lässt sich ein Stapelüberlauf nicht mit catch abfangen: Der Prozess bricht mit der Meldung „Stack overflow.“ ab. Deshalb ruft das Programm oben die Rekursion nicht mit einer Million Zeilen auf. Bei 1.000.000 Zeilen stürzt der Dienst ab.

Genauer, für Neugierige

Wie tief die Rekursion gehen kann, hängt von der Größe des Stapels und der Größe eines Frames ab. In .NET ist der Stapel des Hauptthreads unter Windows etwa 1 MB und unter Linux 8 MB groß.

Ist der rekursive Aufruf die letzte Aktion der Funktion (ohne here + danach), machen manche Sprachen daraus eine Schleife (Tail Call). Java, C#, Python und Node tun das nicht, deshalb kostet die Tiefe in ihnen immer Speicher.

Die Idee

Zeit gegen Speicher

Der Shop prüft, ob zwei Bestellungen des Tages dieselbe Nummer haben. Der erste Weg vergleicht jedes Paar. Der zweite merkt sich die gesehenen Nummern in einem Set:

static bool HasDuplicateLoops(int[] orders)
{
    for (int i = 0; i < orders.Length; i++)
    {
        for (int j = i + 1; j < orders.Length; j++)
        {
            if (orders[i] == orders[j])
            {
                return true;
            }
        }
    }
    return false;
}

static bool HasDuplicateSet(int[] orders)
{
    var seen = new HashSet<int>();
    foreach (int order in orders)
    {
        if (!seen.Add(order))
        {
            return true;
        }
    }
    return false;
}

int[] today = { 100512, 100513, 100514, 100512 };
Console.WriteLine(HasDuplicateLoops(today) + " " + HasDuplicateSet(today));

True True

Beide geben dieselbe Antwort, zahlen aber unterschiedlich:

die verschachtelten Schleifen: O(1) Speicher und O(n²) Zeit;
das Set: O(n) Speicher (bis zu n Nummern) und O(n) Zeit.

Das ist ein häufiger Tausch: Speicher gegen Zeit. Wie viele Vergleiche und Prüfungen beide machen, wenn es keine Wiederholung gibt (der schlechteste Fall):

static long ComparisonsLoops(int[] orders)
{
    long count = 0;
    for (int i = 0; i < orders.Length; i++)
    {
        for (int j = i + 1; j < orders.Length; j++)
        {
            count++;
            if (orders[i] == orders[j])
            {
                return count;
            }
        }
    }
    return count;
}

static long ChecksSet(int[] orders)
{
    var seen = new HashSet<int>();
    long count = 0;
    foreach (int order in orders)
    {
        count++;
        if (!seen.Add(order))
        {
            return count;
        }
    }
    return count;
}

foreach (int n in new[] { 10, 1000 })
{
    int[] orders = new int[n];
    for (int i = 0; i < n; i++)
    {
        orders[i] = 100000 + i;
    }
    Console.WriteLine(n + " Bestellungen: " + ComparisonsLoops(orders) + " Vergleiche mit Schleifen, " + ChecksSet(orders) + " Prüfungen mit Set");
}

10 Bestellungen: 45 Vergleiche mit Schleifen, 10 Prüfungen mit Set
1000 Bestellungen: 499500 Vergleiche mit Schleifen, 1000 Prüfungen mit Set

Verschachtelte Schleifen, ohne Gedächtnis O(n²)
Eine Menge gesehener Zahlen, n Plätze O(n)

Algorithmus	n = 10	n = 1.000	n = 100.000
Verschachtelte Schleifen, ohne Gedächtnis	45	499.500	≈ 4.995.000.000
Eine Menge gesehener Zahlen, n Plätze	10	1.000	100.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.

Bei 100.000 Bestellungen machen die Schleifen fast 5 Milliarden Vergleiche, und das Set macht 100.000 Prüfungen und hält 100.000 Nummern. Wenn der Speicher da ist, gewinnt das Set. Wenn nicht (ein kleines Gerät, eine riesige Eingabe), sortierst du entweder die Nummern (dann liegen die Wiederholungen nebeneinander) oder liest in Teilen.

Genauer, für Neugierige

Wir zählen eine Prüfung im Set als eine Operation. Sie ist im Durchschnitt O(1), weil das Set eine Hashtabelle ist: Aus der Nummer wird ein Hash, und der Hash sagt, in welchem Bucket man nachsieht. Ein Platz in einem Set kostet mehr als eine Zahl in einem Array: in einem HashSet<int> etwa 12–16 Byte (der Wert, der Hash und der Verweis auf den nächsten Eintrag). „O(n) Speicher“ für 10 Millionen Bestellungen sind also Hunderte MB, nicht 40.

Probier es aus

Finde den Fehler

Ein Kollege hat die Prüfung mit einem Set umgeschrieben, aber sie findet nie eine Wiederholung:

static bool HasDuplicateSet(int[] orders)
{
    foreach (int order in orders)
    {
        var seen = new HashSet<int>();
        if (!seen.Add(order))
        {
            return true;
        }
    }
    return false;
}

int[] today = { 100512, 100513, 100514, 100512 };
Console.WriteLine(HasDuplicateSet(today));

False

Die Nummer 100512 kommt zweimal vor, und die Antwort ist „nein“. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Übung

Die letzten drei Zeilen

Löse die Aufgabe in deinem Editor.

Die letzten Zeilen. Wenn etwas kaputtgeht, will der Admin nur die letzten k Zeilen des Logs. Schreibe LastLines(logs, k), das sie zurückgibt und dabei höchstens k Zeilen im Speicher hält, nicht das ganze Log: O(k) Speicher. Lass es mit 1000 Zeilen („Zeile 1“ … „Zeile 1000“) und k = 3 laufen.

Zeile 998
Zeile 999
Zeile 1000

Eine mögliche Lösung

Halte eine Warteschlange: Jede neue Zeile kommt hinten hinein, und sind es mehr als k Zeilen, geht die älteste vorn hinaus.

static List<string> LastLines(List<string> logs, int k)
{
    var recent = new Queue<string>();
    foreach (string line in logs)
    {
        recent.Enqueue(line);
        if (recent.Count > k)
        {
            recent.Dequeue();
        }
    }
    return new List<string>(recent);
}

Weitere Aufgaben

Die durchschnittliche Länge ohne Kopie. Berechne die durchschnittliche Länge einer Zeile im Log mit O(1) zusätzlichem Speicher: ohne neue Liste von Längen.
Fehler pro Stunde. Zähle die Fehler für jede Stunde (09, 10 …). Wie viel Speicher braucht deine Lösung, wenn es 24 Stunden und eine Million Zeilen gibt?
Die wiederholten Nummern. Gib nicht nur „ja oder nein“ zurück, sondern alle wiederholten Nummern. Wie viel Speicher braucht die Lösung mit einem Set, und geht es auch ohne?

Test

Teste dich

1. Eine Funktion erzeugt eine neue Liste mit n Log-Zeilen in umgekehrter Reihenfolge. Wie viel zusätzlichen Speicher braucht sie?O(n²)O(1)O(n)

2. Der Export hält nach jeder Zeile eine Kopie der ganzen Datei bis dahin. Wie viele Plätze belegt der Speicher bei n Zeilen?2nn(n + 1)/2, also O(n²)n

3. Eine rekursive Funktion ganz ohne Liste ruft sich 1.000.000-mal auf, ein Aufruf im anderen. Wie viel Speicher braucht sie?O(1), weil es keine Listen gibtKeinen, Speicher ist nur für ObjekteO(n): Jeder Aufruf bleibt auf dem Stapel, bis er zurückkehrt

4. Du suchst eine wiederholte Nummer in 10.000.000 Bestellungen auf einem Server mit ein paar GB freiem Speicher. Was wählst du?Das Set: O(n) Speicher, aber O(n) Zeit statt O(n²)Die verschachtelten Schleifen, weil sie keinen Speicher brauchenEs macht keinen Unterschied

5. Was zählt nicht zum zusätzlichen Speicher einer Funktion?Die Eingabe, die die Funktion bekommtEine Kopie der Eingabe, die die Funktion machtDer Stapel ihrer Rekursion

Speicherkomplexität

Cookies