Complejidad en espacio en C#

Problema

La exportación que se come la memoria

Cada noche un servicio exporta a un archivo los logs del día de la tienda. Para poder continuar donde se quedó después de una caída, escribe un punto de control después de cada línea. Solo que el punto de control es una copia de todo el archivo hasta ese momento:

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

¿Cuántos espacios ocupan las copias? El programa los cuenta:

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

5 líneas: 15 espacios
1000 líneas: 500500 espacios

Con 1000 líneas son 500 500 espacios. Los logs de un día son 100 000 líneas, y eso son 5 000 050 000 espacios. Cada espacio guarda una referencia de 4 a 8 bytes: entre 20 y 40 GB solo para las copias. En la prueba con 1000 líneas todo pasa, y por la noche la exportación se detiene con OutOfMemoryException.

La idea

La memoria también es un costo

Hasta ahora contabas operaciones. La memoria se cuenta igual: cuántos espacios aparta el algoritmo por sí mismo, aparte de la entrada que recibe. Esa es la complejidad en espacio del algoritmo. También se escribe con Big-O:

O(1): unas pocas variables, sea cual sea el tamaño de la entrada;
O(n): una copia de la entrada, una lista auxiliar, un conjunto con todos los elementos;
O(n²): una copia de la copia en cada paso, como en la exportación.

La entrada no cuenta, porque existe sin el algoritmo. Tampoco cuenta el resultado que pide la tarea: el archivo con n líneas es el trabajo de la exportación. Lo que cuenta son las copias que hace por el camino.

Míralo

Las copias se quedan

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

Paso a paso, en palabras

file es el archivo que escribe la exportación, y logs tiene 4 líneas. checkpoints guarda desde dónde continuar tras una caída.
La línea 1 va al archivo. El punto de control es una copia de todo el archivo: 1 espacio.
Línea 2. El nuevo punto de control copia las dos líneas, y el viejo se queda en la lista: 1 + 2 = 3 espacios.
Tras 4 líneas la memoria guarda 1 + 2 + 3 + 4 = 10 espacios. Tras n líneas son n(n + 1)/2: cinco mil millones con 100 000 líneas.
Para continuar tras una caída solo necesitas saber hasta dónde llegaste. Las copias desaparecen, queda un número.
Cada línea cambia el número: checkpoint = 4. La memoria extra es 1 espacio, sean cuantas sean las líneas.

Cada copia es una lista nueva en la memoria, y nadie borra las viejas: la lista checkpoints las guarda. Por eso los espacios crecen como 1 + 2 + 3 + … + n. Para continuar después de una caída, a la exportación solo le hace falta saber hasta dónde llegó:

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

5 líneas, checkpoint: 5
1000 líneas, checkpoint: 1000

El archivo es el mismo, y la memoria extra es un número: O(1) en lugar de O(n²).

Pruébalo

Predice la salida

La exportación con copias recibe 6 líneas. ¿Cuántos espacios ocupan los puntos de control?

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("línea " + i);
    }
    Console.WriteLine(n + " líneas: " + ExportLogs(logs) + " espacios");
}

Respuesta

6 líneas: 21 espacios

6 líneas: 36 espacios

6 líneas: 6 espacios

Míralo

Una copia o en el sitio

El administrador quiere las líneas de log más nuevas primero. Hay dos maneras. Una crea una lista nueva en orden inverso, y la otra intercambia los elementos de la propia lista: el primero con el último, el segundo con el penúltimo, hasta que los dos extremos se encuentran.

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 inicio de sesión", "09:05 carrito", "09:07 pago" };
List<string> newest = NewestFirst(logs);
Console.WriteLine("Copia:    " + string.Join(", ", newest));
Console.WriteLine("Original: " + string.Join(", ", logs));
ReverseInPlace(logs);
Console.WriteLine("En sitio: " + string.Join(", ", logs));

Copia:    09:07 pago, 09:05 carrito, 09:00 inicio de sesión
Original: 09:00 inicio de sesión, 09:05 carrito, 09:07 pago
En sitio: 09:07 pago, 09:05 carrito, 09:00 inicio de sesión

La copia necesita n espacios nuevos, pero el original se queda como estaba. El cambio en el sitio necesita un espacio para el intercambio, pero el orden viejo desaparece. Cuál es mejor depende de si alguien más sigue leyendo el original.

Más precisamente, para curiosos

Las funciones incorporadas toman la misma decisión, y el nombre no siempre la delata:

var logs = new List<string> { "09:00 inicio de sesión", "09:05 carrito", "09:07 pago" };
List<string> copy = Enumerable.Reverse(logs).ToList();
logs.Reverse();
Console.WriteLine("En sitio: " + string.Join(", ", logs));
Console.WriteLine("Copia:    " + string.Join(", ", copy));

En sitio: 09:07 pago, 09:05 carrito, 09:00 inicio de sesión
Copia:    09:07 pago, 09:05 carrito, 09:00 inicio de sesión

List<T>.Reverse() invierte en el sitio. Enumerable.Reverse de LINQ no hace nada hasta que lo lees, y ToList() hace la copia. GetRange también copia.

La copia es superficial: la lista nueva guarda referencias a los mismos textos, no textos nuevos. Por eso los espacios se cuentan uno por elemento.

Pruébalo

Completa

Termina el intercambio de los dos extremos:

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

Míralo

La recursión también guarda memoria

No solo una lista ocupa espacio. Cada llamada a un método guarda sus parámetros y variables locales en la pila de llamadas hasta que regresa. Aquí se cuentan los errores del log con recursión y con un bucle:

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 líneas: " + ErrorsFrom(small, 0) + " errores");
Console.WriteLine("Con bucle: " + Errors(big) + " errores");

500 líneas: 5 errores
Con bucle: 10000 errores

La recursión no crea ni una sola lista, pero con n líneas hay n llamadas sin terminar en la pila: memoria O(n). La pila es pequeña, y un millón de llamadas no caben. El bucle tiene una variable count: O(1).

En C# el desbordamiento de la pila no se puede capturar con catch: el proceso se detiene con el mensaje «Stack overflow.». Por eso el programa de arriba no llama a la recursión con un millón de líneas. Con 1 000 000 de líneas el servicio se cae.

Más precisamente, para curiosos

Qué tan profunda puede ser la recursión depende del tamaño de la pila y del tamaño de un marco. En .NET la pila del hilo principal es de unos 1 MB en Windows y 8 MB en Linux.

Cuando la llamada recursiva es la última acción de la función (sin here + después), algunos lenguajes la convierten en un bucle (tail call). Java, C#, Python y Node no lo hacen, así que en ellos la profundidad siempre cuesta memoria.

La idea

Tiempo contra memoria

La tienda comprueba si dos pedidos del día tienen el mismo número. La primera manera compara cada par. La segunda recuerda en un conjunto los números que ya vio:

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

Las dos dan la misma respuesta, pero pagan de forma distinta:

los bucles anidados: memoria O(1) y tiempo O(n²);
el conjunto: memoria O(n) (hasta n números) y tiempo O(n).

Es un intercambio común: memoria por tiempo. Cuántas comparaciones y comprobaciones hacen las dos cuando no hay repetido (el peor caso):

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 + " pedidos: " + ComparisonsLoops(orders) + " comparaciones con bucles, " + ChecksSet(orders) + " comprobaciones con set");
}

10 pedidos: 45 comparaciones con bucles, 10 comprobaciones con set
1000 pedidos: 499500 comparaciones con bucles, 1000 comprobaciones con set

Bucles anidados, sin memoria O(n²)
Un conjunto de números vistos, n lugares O(n)

Algoritmo	n = 10	n = 1000	n = 100.000
Bucles anidados, sin memoria	45	499.500	≈ 4.995.000.000
Un conjunto de números vistos, n lugares	10	1000	100.000

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

Con 100 000 pedidos los bucles hacen casi 5 mil millones de comparaciones, y el conjunto hace 100 000 comprobaciones y guarda 100 000 números. Cuando hay memoria, gana el conjunto. Cuando no la hay (un dispositivo pequeño, una entrada enorme), o ordenas los números (así los repetidos quedan juntos) o lees por partes.

Más precisamente, para curiosos

Contamos una comprobación en el conjunto como una operación. Es O(1) en promedio, porque el conjunto es una tabla hash: el número se convierte en un hash, y el hash dice en qué cubeta mirar. Un espacio en un conjunto cuesta más que un número en un array: en un HashSet<int> unos 12–16 bytes (el valor, el hash y el enlace a la entrada siguiente). Así que «memoria O(n)» para 10 millones de pedidos son cientos de MB, no 40.

Pruébalo

Encuentra el error

Un compañero reescribió la comprobación con un conjunto, pero nunca encuentra un repetido:

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

El número 100512 está dos veces, y la respuesta es «no». ¿En qué línea está el error?

Elige la línea con el error.

Ejercicio

Las últimas tres líneas

Resuelve la tarea en tu editor.

Las últimas líneas. Cuando algo se rompe, el administrador quiere solo las últimas k líneas del log. Escribe LastLines(logs, k), que las devuelva guardando en memoria como máximo k líneas, no todo el log: memoria O(k). Ejecútalo con 1000 líneas («línea 1» … «línea 1000») y k = 3.

línea 998
línea 999
línea 1000

Una posible solución

Mantén una cola: cada línea nueva entra por detrás y, cuando hay más de k líneas, la más antigua sale por delante.

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

Más tareas

El promedio de longitud sin copia. Calcula la longitud promedio de una línea del log con memoria extra O(1): sin una lista nueva de longitudes.
Errores por hora. Cuenta los errores de cada hora (09, 10 …). ¿Cuánta memoria necesita tu solución si hay 24 horas y un millón de líneas?
Los números repetidos. Devuelve no solo «sí o no», sino todos los números repetidos. ¿Cuánta memoria necesita la solución con un conjunto, y se puede hacer sin él?

Test

Ponte a prueba

1. Una función crea una lista nueva con n líneas de log en orden inverso. ¿Cuánta memoria extra necesita?O(n)O(n²)O(1)

2. La exportación guarda después de cada línea una copia de todo el archivo hasta ese momento. ¿Cuántos espacios ocupa la memoria con n líneas?n(n + 1)/2, es decir, O(n²)n2n

3. Una función recursiva sin ninguna lista se llama a sí misma 1 000 000 de veces, una dentro de otra. ¿Cuánta memoria necesita?O(n): cada llamada se queda en la pila hasta que regresaO(1), porque no hay listasNinguna, la memoria es solo para objetos

4. Buscas un número repetido entre 10 000 000 de pedidos en un servidor con unos pocos GB de memoria libre. ¿Qué eliges?El conjunto: memoria O(n), pero tiempo O(n) en lugar de O(n²)Los bucles anidados, porque no necesitan memoriaNo hay diferencia

5. ¿Qué no cuenta en la memoria extra de una función?La pila de su recursiónLa entrada que recibe la funciónUna copia de la entrada que hace la función

Complejidad en espacio

Cookies