Space complexity in C#

Problem

The export that eats the memory

Every night a service exports the shop's logs for the day to an archive. So that it can carry on from where it stopped after a crash, it writes a checkpoint after every line. Except that the checkpoint is a copy of the whole file so far:

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;
}

How many places do the copies hold? The program counts them:

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

5 lines: 15 places
1000 lines: 500500 places

For 1000 lines it is 500 500 places. The logs of one day are 100 000 lines, and that is 5 000 050 000 places. Every place holds a reference of 4 to 8 bytes: between 20 and 40 GB just for the copies. In the test with 1000 lines everything passes, and at night the export stops with OutOfMemoryException.

The idea

Memory is a cost too

So far you counted operations. Memory is counted the same way: how many places the algorithm sets aside itself, apart from the input it receives. This is the space complexity of the algorithm. It is written with Big-O too:

O(1): a few variables, however big the input;
O(n): a copy of the input, a helper list, a set with all the elements;
O(n²): a copy of the copy at every step, as in the export.

The input does not count, because it exists without the algorithm. Neither does the result the task asks for: the file with n lines is the export's job. What counts are the copies it makes along the way.

See it

The copies stay

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

Step by step, in words

file is the file the export writes; logs has 4 lines. checkpoints keeps where to resume after a crash.
Line 1 goes into the file. The checkpoint is a copy of the whole file: 1 place.
Line 2. The new checkpoint copies both lines, and the old one stays in the list: 1 + 2 = 3 places.
After 4 lines memory holds 1 + 2 + 3 + 4 = 10 places. After n lines it is n(n + 1)/2: five billion for 100 000 lines.
To resume after a crash you only need how far you got. The copies go; one number stays.
Every line changes the number: checkpoint = 4. The extra memory is 1 place, however many lines there are.

Every copy is a new list in memory, and nobody deletes the old ones: the list checkpoints keeps them. That is why the places grow as 1 + 2 + 3 + … + n. To carry on after a crash, the export only needs how far it got:

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("line " + i);
    }
    Console.WriteLine(n + " lines, checkpoint: " + ExportLogs(logs));
}

5 lines, checkpoint: 5
1000 lines, checkpoint: 1000

The file is the same, and the extra memory is one number: O(1) instead of O(n²).

Try it

Predict the output

The export with the copies gets 6 lines. How many places do the checkpoints hold?

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("line " + i);
    }
    Console.WriteLine(n + " lines: " + ExportLogs(logs) + " places");
}

Answer

6 lines: 36 places

6 lines: 21 places

6 lines: 6 places

See it

A copy or in place

The admin wants the newest log lines first. There are two ways. One makes a new list in reverse order, and the other swaps the elements in the list itself: the first with the last, the second with the one before last, until the two ends meet.

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 login", "09:05 cart", "09:07 payment" };
List<string> newest = NewestFirst(logs);
Console.WriteLine("Copy:     " + string.Join(", ", newest));
Console.WriteLine("Original: " + string.Join(", ", logs));
ReverseInPlace(logs);
Console.WriteLine("In place: " + string.Join(", ", logs));

Copy:     09:07 payment, 09:05 cart, 09:00 login
Original: 09:00 login, 09:05 cart, 09:07 payment
In place: 09:07 payment, 09:05 cart, 09:00 login

The copy needs n new places, but the original stays as it was. The change in place needs one place for the swap, but the old order is gone. Which is better depends on whether someone else still reads the original.

More precisely, if you are curious

The built-in functions make the same choice, and the name does not always tell you:

var logs = new List<string> { "09:00 login", "09:05 cart", "09:07 payment" };
List<string> copy = Enumerable.Reverse(logs).ToList();
logs.Reverse();
Console.WriteLine("In place: " + string.Join(", ", logs));
Console.WriteLine("Copy:     " + string.Join(", ", copy));

In place: 09:07 payment, 09:05 cart, 09:00 login
Copy:     09:07 payment, 09:05 cart, 09:00 login

List<T>.Reverse() reverses in place. Enumerable.Reverse from LINQ does nothing until you read it, and ToList() makes the copy. GetRange copies too.

The copy is shallow: the new list keeps references to the same texts, not new texts. That is why the places are counted one per element.

Try it

Fill in

Finish the swap of the two ends:

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

See it

Recursion holds memory too

A list is not the only thing that takes room. Every call of a method keeps its parameters and local variables on the call stack until it returns. Here is counting the errors in the log with recursion and with a loop:

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 lines: " + ErrorsFrom(small, 0) + " errors");
Console.WriteLine("With a loop: " + Errors(big) + " errors");

500 lines: 5 errors
With a loop: 10000 errors

The recursion makes not a single list, but for n lines there are n unfinished calls on the stack: O(n) memory. The stack is small, and a million calls do not fit. The loop has one variable count: O(1).

In C# a stack overflow cannot be caught with catch: the process stops with the message "Stack overflow." That is why the program above does not call the recursion with a million lines. With 1 000 000 lines the service crashes.

More precisely, if you are curious

How deep the recursion can go depends on the size of the stack and the size of one frame. In .NET the stack of the main thread is about 1 MB on Windows and 8 MB on Linux.

When the recursive call is the last action of the function (with no here + after it), some languages turn it into a loop (a tail call). Java, C#, Python and Node do not, so in them depth always costs memory.

The idea

Time against memory

The shop checks whether two orders of the day have the same number. The first way compares every pair. The second remembers the numbers it has seen in a 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

Both give the same answer, but they pay differently:

the nested loops: O(1) memory and O(n²) time;
the set: O(n) memory (up to n numbers) and O(n) time.

This is a common trade: memory for time. How many comparisons and checks the two make when there is no repeat (the worst case):

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 + " orders: " + ComparisonsLoops(orders) + " comparisons with loops, " + ChecksSet(orders) + " checks with a set");
}

10 orders: 45 comparisons with loops, 10 checks with a set
1000 orders: 499500 comparisons with loops, 1000 checks with a set

Nested loops, no memory O(n²)
A set of seen numbers, n places O(n)

Algorithm	n = 10	n = 1,000	n = 100,000
Nested loops, no memory	45	499,500	≈ 4,995,000,000
A set of seen numbers, n places	10	1,000	100,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

For 100 000 orders the loops make almost 5 billion comparisons, and the set makes 100 000 checks and keeps 100 000 numbers. When the memory is there, the set wins. When it is not (a small device, a huge input), you either sort the numbers (then the repeats are next to each other) or read in parts.

More precisely, if you are curious

We count one check in the set as one operation. It is O(1) on average, because the set is a hash table: the number becomes a hash, and the hash says which bucket to look in. One place in a set costs more than one number in an array: in a HashSet<int> about 12–16 bytes (the value, the hash and the link to the next entry). So "O(n) memory" for 10 million orders is hundreds of MB, not 40.

Try it

Find the bug

A colleague rewrote the check with a set, but it never finds a repeat:

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

Number 100512 is there twice, and the answer is "no". Which line is the bug on?

Pick the line with the bug.

Exercise

The last three lines

Solve the task in your editor.

The last lines. When something breaks, the admin wants only the last k lines of the log. Write LastLines(logs, k), which returns them while keeping at most k lines in memory, not the whole log: O(k) memory. Run it with 1000 lines ("line 1" … "line 1000") and k = 3.

line 998
line 999
line 1000

One possible solution

Keep a queue: every new line goes in at the back, and when there are more than k lines, the oldest goes out at the front.

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);
}

More tasks

The average length without a copy. Compute the average length of a line in the log with O(1) extra memory: without a new list of lengths.
Errors by hour. Count the errors for every hour (09, 10…). How much memory does your solution need if there are 24 hours and a million lines?
The repeated numbers. Return not only "yes or no", but all repeated numbers. How much memory does the solution with a set need, and can you do without it?

Test

Check yourself

1. A function makes a new list with n log lines in reverse order. How much extra memory does it need?O(1)O(n)O(n²)

2. The export keeps a copy of the whole file so far after every line. How many places does memory hold for n lines?n(n + 1)/2, that is O(n²)n2n

3. A recursive function with no list at all calls itself 1 000 000 times, one call inside another. How much memory does it need?O(n): every call stays on the stack until it returnsO(1), because there are no listsNone, memory is only for objects

4. You look for a repeated number in 10 000 000 orders on a server with a few GB of free memory. Which do you choose?It makes no differenceThe set: O(n) memory, but O(n) time instead of O(n²)The nested loops, because they need no memory

5. What does not count in the extra memory of a function?The stack of its recursionA copy of the input the function makesThe input the function receives

Space complexity

Cookies