Nerding about stuff I've found interesting

En términos muy generales, el área de estudio de estructuras de datos como disciplina de las ciencias computacionales (CS) es el almacenamiento y la manipulación de la información. Aunque almacenamiento y manipulación podría abarcar muchísimas cosas, por ejemplo la representación interna de una sola pieza de información en `0`s y `1`s en la memoria de la computadora (mejor conocido como encoding) o incluso la tecnología usada para almacenar la información como el motor de base de datos o el software utilizado, las estructuras de datos, siendo un disciplina dentro de la categoría de la computación teórica, estudian de manera más abstracta la relación entre una colección de datos y las operaciones que pueden ser aplicadas a dicha colección.

Referente a las colecciones, una colección de datos podría ser entendida como un conjunto en matemáticas con la única diferencia de que, aunque en ambas ciencias (CS y Math) los conjuntos son IMPORTANTÍSIMOS, en ciencias de la computación los conjuntos cambian todo el tiempo y los duplicados son el pan de todos los días. Dichos conjunto suelen ser encontrados en la literatura como conjuntos dinámicos o simplemente como colecciones.

Por el lado de las operaciones, de forma general podemos decir que existen dos tipos: las de consulta, que regresan información sobre el conjunto y las de modificación, que cambian el estado del conjunto. A continuación listamos algunas de las operaciones más comunes, aunque claramente la naturaleza de cada estructura puede dar pie a otras operaciones muy particulares:

  • Buscar: Obtener un elemento del conjunto basado en información sobre el mismo.
  • Insertar o eliminar: Agregar o quitar elementos del conjunto.
  • Modificar: Modificar la estructura de los elementos del conjunto o los elementos mismos.
  • Conocer a los vecinos: Si los elementos siguen cierto orden, debemos ser capaces de conocer quiénes son los sucesores o predecesores de un elemento particular.

En este post vamos a hablar acerca de tres estructuras de datos fundamentales en el manejo de colecciones, conocidas por casi todos los programadores: los arreglos, las pilas (stacks) y las colas (queues).

Y sí, aunque las estructuras de datos suelen ser tratadas como algo abstracto y la implementación es ignorada casi por completo en los libros más formales, nosotros haremos algunas implementaciones utilizando Python pero con un pequeño disclaimer: nuestras implementaciones ignorarán un montón de los pequeños detalles ingenieriles por lo que no sería recomendable que utilices el código para cosas serias. Para eso seguramente ya existen implementaciones robustas dentro de la tecnología que estés usando. Lo anterior es principalmente por dos razones: 1) No tiene sentido preocuparnos ya que no es una serie de posts sobre ingeniería, y 2) Los pequeños detalles podrían distraernos muchísimo de las cosas que realmente son importantes en las estructuras de datos como el análisis de complejidad de las operaciones o los algoritmos detrás de cada una.

Arreglos

"Pff arreglos... 😪 que aburrido" ¿cierto? ¿qué cosa podría leer de arreglos que no sepas ya? Sinceramente no mucho, así que vayamos rápido a la definición: Un arreglo es una colección finita (de tamaño fijo) de elementos del mismo tipo.

La forma de almacenar los elementos de un arreglo es apartando una serie de direcciones de memoria donde podamos meter todos y cada uno de los elementos, uno al lado del otro, identificándolos con un índice `i` que va desde `0` hasta `n-1`, donde `n` es el número de elementos dentro de la colección. De esto es que decimos cosas como "el `i`-ésimo elemento de un arreglo" o "the `i`-th element of an array" en inglés. Para visualizar mejor la estructura de un arreglo recordemos el ejemplo gráfico que dimos en el primer post. En dicho ejemplo teníamos un arreglo A=[10, 9, 8, -142, 238] y explicamos que cada elemento ocupaba `4` bytes (`32` bits) y teníamos 5 elementos, por lo tanto nuestro arreglo ocupaba exactamente `20` bytes que iban desde una dirección `x` hasta `x + 20`. En el dibujo `x` está en hexadecimal y es 0xffee0fca840 por lo que `x+20=`0xffee0fca854:

Representación gráfica de arrays.cp del blog post EDD[1]

Además de eso, vimos que si tenemos un índice válido, entonces acceder al elemento del arreglo que tiene ese índice es extremadamente sencillo siguiendo la siguiente ecuación:

$$A[i] = A + it$$

Donde `A[i]` es el elemento ubicado en el índice `i` (el `i`-ésimo elemento), `A` es la dirección en memoria donde inicia el arreglo, `t` es el tamaño en bytes de cada elemento y claramente `i \in {0, 1, 2,..., n-1\}` donde `n` es el número total de elementos de `A`.


De toda estructura que veamos tenemos que poder decir qué tan eficiente resulta realizar las operaciones básicas (acceder, modificar, eliminar, agregar, conocer a los vecinos, etc.) para entonces saber, basados en el problema que tratamos de resolver, qué estructura utilizar. Lo anterior lo haremos mediante el análisis de la complejidad del algoritmo asociado a cada operación, es decir, utilizando las notaciones `O` (Big-O), `\Theta` (Teta) y `\Omega` (Omega), sobre las cuales ya existe un post y un webinar gratuito que puedes visitar para refrescar la memoria.

De las operaciones para acceder, modificar y conocer a los vecinos podemos concluir fácilmente que tienen complejidad `\Theta(1)` ya que todas suceden gracias al uso de índices y no importa que tan grande sea nuestro arreglo, la ecuación para obtener un elemento no cambia en absoluto, además de que la multiplicación y la suma suelen ser instrucciones que todos los procesadores incluyen y suceden casi instantaneamente.

Pero ¿qué sucede cuando queremos agregar un elemento? Bajo la definición que dimos, agregar un elemento no está permitido. Y dirás "pues que mala definición la tuya, mi lenguaje hipster de programación sí me permite agregar elementos a un arreglo utilizando métodos como push (en JavaScript) o append (en Python)", y bueno, pues realmente eso no es cierto, así que en lugar de dejar el tema aquí y simplemente decir que no se puede, hablemos de lo que realmente sucede en estos lenguajes hipsters de programación. Éstos son capaces de proveer dicha funcionalidad debido a que sus arreglos realmente son otra estructura diferente llamada arreglos dinámicos.

Cuando un arreglo dinámico es creado por primera vez, junto con la asignación de las direcciones de memoria necesaria para almacenar los primeros elementos, se apartan direcciones adicionales. Lo anterior permite que en el momento que un nuevo elemento se quiera insertar existan espacios contiguos al último elemento en haber sido agregado y de esa manera la operación mantenga una complejidad `\Theta(1)`. Cuando no hay más espacios adicionales, entonces TODO el arreglo es copiado a una nueva ubicación de memoria junto con más espacios adicionales y esta operación tiene complejidad `\Theta(n)` 😢.

En Python, los arreglos dinámicos son de tamaño `1.125n`, es decir, si creamos un arreglo de `n` elementos, en la memoria el arreglo realmente tendrá el tamaño de `1.125n` elementos, en otras palabras, adicional a los `n` elementos almacenados, habrá `.125n` direcciones vacías reservadas, y por si no fuera poco: insertar un elemento al principio o a la mitad de un arreglo dinámico tiene complejidad `\Theta(n)` ya que todos los elementos a la derecha tienen que ser movidos una posición a la derecha. ¿No es tan sexy después de todo, verdad? 😔. Por último, es importante mencionar que aunque en muchos textos se diga correctamente que insertar un elemento en un arreglo dinámico tiene complejidad `\Theta(1)` amortizada, no es lo mismo que decir que tiene complejidad `\Theta(1)`.

$$\Theta(1) \; \mathrm{amortizada} \neq \Theta(1)$$

¿Y qué sucede cuando queremos eliminar un elemento? Nuevamente, bajo la definición dada, eliminar un elemento no está permitido. El problema con eliminar un elemento es que (y de hecho es lo que sucede en los arreglos dinámicos) hay que mover a todos los vecinos que estén a la derecha del elemento un lugar a la izquierda, resultando en una operación con complejidad `\Theta(n)`.


Por último y quizá lo más interesante, ¿te has puesto a pensar qué sucede con los arreglos de múltiples dimensiones, es decir, arreglos de arreglos? Pues realmente nada raro, tu tranquil@. Las operaciones de acceso, modificación y vecinos siguen teniendo la misma complejidad (`\Theta(1)`) gracias a que la definición se sigue cumpliendo, es decir, un arreglo multidimensional sigue siendo una "colección finita de elementos del mismo tipo". Veamos lo anterior con un ejemplo: imagina un arreglo `A` de dos dimensiones, por ejemplo la matriz `2 \times 5` con los siguientes elementos (implementación en C++):

int main() {
    int A[2][5] = {
        {1, 3, 9, 27, 81},
        {1, 2, 6, 24, 120}
    };
    return 0;
}

O gráficamente:

Arreglo `A` visto como una matriz indexada en 0, donde en `A[i][j]`, `i` representa la fila y `j` la columna

En el ejemplo anterior el arreglo `A` sigue cumpliendo la definición, porque la primera dimensión es finita (`2` elementos) y almacena elementos del mismo tipo (arreglos de 5 enteros) mientras que la segunda dimensión también es finita (`5` elementos) y también almacena elementos del mismo tipo (enteros). Dicho lo anterior, podemos modificar un poco la ecuación del principio, si conocemos el tamaño del elemento de cada dimensión. Entonces, sabiendo que los elementos de la primera dimensión tienen tamaño \(t_1 = 5 \times (4 \; \mathrm{bytes} ) = 20 \; \mathrm{bytes}\) y la segunda dimensión \(t_2 = 4 \; \mathrm{bytes}\) obtenemos la ecuación:

$$A[i][j] = A + it_1 + jt_2$$

Y lo anterior funciona porque en memoria el arreglo realmente luce así:

Representación de un arreglo 2D en memoria

Aquí vemos un ejemplo de qué sucede con las operaciones si reemplazáramos `i` y `j` de la ecuación anterior y si supusiéramos que el arreglo inicia en la posición `800` (decimal) de la memoria:

  • \(A[\color{red}0][\color{blue}0] = 800 + (\color{red}0 \times 20) + (\color{blue}0 \times 4) = 800 \rightarrow 1\)
  • \(A[\color{red}0][\color{blue}1] = 800 + (\color{red}0 \times 20) + (\color{blue}1 \times 4) = 804 \rightarrow 3\)
  • \(A[\color{red}0][\color{blue}2] = 800 + (\color{red}0 \times 20) + (\color{blue}2 \times 4) = 808 \rightarrow 9\)
  • \(...\)
  • \(A[\color{red}1][\color{blue}0] = 800 + (\color{red}1 \times 20) + (\color{blue}0 \times 4) = 820 \rightarrow 1\)
  • \(A[\color{red}1][\color{blue}1] = 800 + (\color{red}1 \times 20) + (\color{blue}1 \times 4) = 824 \rightarrow 2\)
  • \(A[\color{red}1][\color{blue}2] = 800 + (\color{red}1 \times 20) + (\color{blue}2 \times 4) = 828 \rightarrow 6\)
  • \(...\)
  • \(A[\color{red}1][\color{blue}4] = 800 + (\color{red}1 \times 20) + (\color{blue}4 \times 4) = 836 \rightarrow 120\)

¿Y cuánto espacio ocupa el arreglo en la memoria? En nuestro caso es el tamaño de la dimensión más pequeña (`20` bytes) por la cantidad de elementos que tenga su padre (`2`), es decir, es la multiplicación del tamaño de sus dimensiones (`40` bytes). Pero nuestro caso no tiene absolutamente nada de especial, de hecho, generalicemos lo que acabamos de aprender para un número cualquier de dimensiones:

Sea `d` el número de dimensiones de un arreglo multidimensional, `s` una dimensión especifica tal que `1 \leq s \leq d`, y `n_s` el tamaño de la dimensión `s`, entonces nuestro arreglo medirá:

$$n_1 \times n_2 \times n_3 \times ... \times n_d$$

O más chulo 🤩:

$$\prod_{s=1}^{d} n_s$$

Y como lo anterior también implica que la dimensión `i` tiene tamaño

$$n_i \times n_{i+1} \times ... \times n_{d-1} \times n_d$$

Entonces también podemos generalizar la ecuación para obtener el `i`-ésimo elemento del arreglo, es decir, `A[i_1][i_2]...[i_d]` (con la obvia restricción de que `0 \leq i_s < n_s`), obteniendo:

$$A[i_1]...[i_d] = A + i_1 \prod_{s=2}^d n_s + i_2 \prod_{s=3}^d n_s + ... + i_{d-2} \prod_{s=d-1}^d n_s + i_{d-1} n_d + i_d$$

O aún más simplificado si definimos a `\prod_{s=d+1}^dn_s = 1`:

$$\sum_{t=1}^d \prod_{s=t+1}^dn_s$$

Manteniendo la complejidad `\Theta(1)` 😎.

La ecuación anterior es conocida como el polinomio de redireccionamiento y aunque es muy raro que tengas que programarla a manita, puedes estar casi seguro de que el lenguaje que estás utilizando tendrá alguna versión de éste polinomio escrito por ahí.

¡Ya casi terminamos la sección 🎉! Ahí les va un meme de `0 \in \mathbb{N}` pal' desestrés matemático:

`0 \in \mathbb{N}` let me in meme

Como mencionamos anteriormente Python no tiene arreglos, pero la estructura que podría ser considerada como arreglo se llama lista (list) y tiene métodos como append y remove para agregar y eliminar elementos respectivamente. En este punto tal vez esté de más decirlo, pero en caso de que no haya quedado claro: Si estás trabajando con listas de Python (o su equivalente en otro lenguaje de programación) y agregando y eliminando elementos constantemente, probablemente deberías usar una estructura de datos diferente:

Listas en Python:

A = [1, 3, 9, 27, 81]
>>> [1, 3, 9, 27, 81]

len(A)
>>> 5 

A.append(243)
>>> [1, 3, 9, 27, 81, 243]

len(A)
>>> 6

A.remove(9)
>>> [1, 3, 27, 81, 243]

A.insert(2, 9)
>>> [1, 3, 9, 27, 81, 243]

A.reverse()
>>> [243, 81, 27, 9, 3, 1]

A.clear()
>>> []

A = [3**i for i in range(6)]
>>> [1, 3, 9, 27, 81, 243]

A[:3]
>>> [1, 3, 9]

A[3:]
>>> [27, 81, 243]

A[2: 4]
>>> [9, 27]

A[::2]
>>> [1, 9, 81]

A[::]
>>> [1, 3, 9, 27, 81, 243]

A = [0] * 10
>>> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Pilas y colas

Quizá las pilas y las colas sean las estructuras de datos más simples de entender y ésto se debe a sus analogías con la vida real. Las pilas (stacks) y las colas (queues) son también una colección finita (o al menos por el momento) con dos operaciones principales: agregar y sacar elementos, donde la diferencia entre éstas radica meramente en la forma en la que las operaciones funcionan.

Las pilas pueden ser entendidas con la analogía de una montaña de objetos, por ejemplo la montaña de hotcakes en la portada de este post, donde agregar un elemento significa agregar un nuevo hotcake encima del último (el de la cima) y sacar un elemento significa quitar el hotcake que está en la cima. La operación de agregar un elemento a una pila se conoce como push, mientras que la operación que saca elementos se conoce como pop. Además, cuando tratamos de agregar elementos a una pila llena (porque las definimos como finitas) ocurre un error conocido como stack overflow, mientras que en el caso opuesto, es decir, sacar elementos de una pila vacía, genera un error con un nombre menos popular conocido como stack underflow. Por último, el comportamiento de una pila suele ser descrito con las siglas LIFO, del inglés, Last In, First Out, que describen claramente sus operaciones.

https://stackoverflow.com/

Una pila puede ser fácilmente implementada utilizando arreglos y manteniendo siempre una referencia a la cima, es decir, un índice que indique la posición del último elemento agregado. Cada que un elemento se agrega a la pila incrementamos en 1 dicho índice y agregamos el nuevo elemento al arreglo en la posición que la cima indica. En el caso de un pop realizamos lo opuesto: regresamos el elemento que se encuentra en la posición de la cima y decrementamos su valor en 1. Se podría también eliminar (volver nulo) el valor en dicha posición antes de regresarlo, pero de todas formas estaremos ocupando la misma cantidad de memoria por lo que la supuesta optimización no tendría sentido.

Operaciones en una pila de 5 elementos

En la última fila del dibujo anterior, los elementos 'b' y 'c', aunque aún están en memoria, ya no existen para el contexto de la pila.

Así luciría una implementación en Python:

class Stack:

    def __init__(self, n):
        self.size = n
        self.data = [None] * n
        self.top = -1

    def push(self, e):
        if self.top + 1 == self.size:
            raise Exception('Stack overflowed')
        self.top += 1
        self.data[self.top] = e

    def pop(self):
        if self.top == -1:
            raise Exception('Stack underflowed')
        e = self.data[self.top]
        self.top -= 1
        return e

Algo interesante que notar en esa implementación es que todas las operaciones, excepto el constructor (tal vez), tienen complejidad `\Theta(1)`, pero por otro lado, y algo aburrido de la misma, es que todo lo que hace la clase Stack ya puede ser realizado por las listas que incluye Python por default si sólo utilizáramos los métodos append (equivalente a push) y pop:

A = []
>>> []

A.append(1)
>>> [1]

for i in range(5):
    A.append(2**i)
>>> [1, 1, 2, 4, 8, 16]

A.pop()
>>> 16

A.pop()
>>> 8

A
>>> [1, 1, 2, 4]

Aunque, ¿no notas algo raro?... ¡LA COMPLEJIDAD! Ya le pusimos en la madre 😅 ¿Por qué? Recuerda que las listas de Python son realmente arreglos dinámicos y  eventualmente tienen que redimensionarse y copiarse a otras ubicaciones de la memoria, las cuales son operaciones con complejidad `\Theta(n)`. Bueno, que tampoco está tan mal, realmente la complejidad de agregar un elemento al final de un arreglo dinámico es `\Theta(1)` amortizada. Por el momento dejémosla así e ignoremos esos problemas ya que más adelante veremos otras formas de tener pilas y colas infinitas en Python con complejidad `\Theta(1)` en todas sus operaciones.


Entonces ¿Qué son las colas (queues)? Pues exactamente lo opuesto, First In, First Out (FIFO). Como la cola de las tortillas/arepas/ATM/etc.: el primero en formarse es el primero en pasar, o visto de otra forma, el que lleva más tiempo esperando es el primero en ser atendido. En las colas la operación que agrega coloca los nuevos elementos después del último. Esta operación es conocida como enqueue (enkiú 😜). Por otro lado, la operación que elimina al primero en la fila se conoce como dequeue (dikiú 😜), es decir, ya atendieron al que llegó primero. Ah! Y cuando se llega al límite y se quiere agregar un elemento más se dice que sucede un queue overflow, y de manera opuesta un queue underflow cuando se desean eliminar elementos de una cola vacía.

La implementación de colas de tamaño fijo puede ser más interesante ya que ahora hay que recordar dos cosas: ¿Dónde está el primero en la cola? y ¿Dónde está el último en la cola? Una forma de implementar las colas es utilizando un apuntador head con la ubicación del primer elemento de la cola y otro apuntador tail con la posición siguiente del último elemento. Lo anterior implica que utilizando un arreglo de tamaño \(n\) podemos guardar máximo \(n-1\) elementos ¿Por qué? Realmente es una decisión de diseño, piensa en esto: Si acordamos que el apuntador \(head\) tiene la posición del primer elemento de la cola y el apuntador \(tail\) tiene la posición del último elemento de la cola, ¿cuál sería la condición que nos permitiría saber si la cola está vacía o está llena utilizando únicamente estos apuntadores?

Agregando elementos a una pila de 4 elementos

Por otro lado, tenemos que asegurarnos de siempre poder almacenar máximo \(n-1\) elementos sin importar la posición de los apuntadores. A primera vista esto podría parecer obvio, pero ¿qué pasaría si en ejemplo anterior sacáramos los elementos 'a', 'b' y 'c' de la cola? No podemos solamente decirle al usuario que la cola está llena cuando únicamente estamos almacenando un elemento y supuestamente la cola podía guardar hasta `4`. Para resolver esto tenemos que hacer nuestro arreglo circular, es decir, después de la posición `n` estrictamente sigue la posición `1` (hablando de posiciones, no de índices). Entonces, justo como lo imaginaste, necesitaremos de nuestro viejo amigo el módulo o "`\%`" pa' los cuates, y así, el criterio para saber que la cola está llena es si tail+1 `=` head, mientras que la cola estará vacía si tail `=` head.

Propiedad circular de los índices de una cola finita

De la misma manera en que lo propusimos para la pila, podríamos volver nulos los valores que vayamos sacando de la cola, pero realmente no agregaría ninguna optimización a nivel de espacio. Es por esto que en la penúltima fila, aunque los valores 'a', 'b' y 'c' sigan dentro del arreglo, ya no existen dentro del contexto de la cola.

Así luciría una implementación en Python:

class Queue:

    def __init__(self, n):
        self.size = n
        self.data = [None] * (n + 1)
        self.head = 0
        self.tail = 0

    def __plus_one(self, pointer):
        return (pointer + 1) % (self.size + 1)

    def __is_empty(self):
        return self.head == self.tail

    def __is_full(self):
        return self.__plus_one(self.tail) == self.head

    def enqueue(self, e):
        if self.__is_full():
            raise Exception('Queue overflowed')
        self.data[self.tail] = e
        self.tail = self.__plus_one(self.tail)

    def dequeue(self):
        if self.__is_empty():
            raise Exception('Queue underflowed')
        e = self.data[self.head]
        self.head = self.__plus_one(self.head)
        return e

Por otro lado, al igual que en nuestras pilas, todas las operaciones tienen complejidad \(\Theta(1)\), excepto tal vez por el constructor. En contraste con las pilas, haber utilizado únicamente listas nativas de Python para simular el comportamiento de una cola, hubiera sido una pésima idea, ya que agregar o eliminar elementos al inicio o a la mitad de un arreglo dinámico es estrictamente \(\Theta(n)\) sin amortizaciones.

Las implementaciones propuestas arriba tienen un estilo muy particular en el sentido que asemejan a un lenguaje de bajo nivel, donde los arreglos no son dinámicos (no son "listas") y ésto es como fingir que estamos trabajando con un lenguaje de programación diferente a Python, pero de todas formas es importante recordar que si utilizáramos el "poder" de las listas de Python en las implementaciones anteriores, terminaríamos convirtiendo la complejidad de una estructura que debería ser \(\Theta(1)\) en todas sus operaciones principales a una complejidad de \(O(n)\) o incluso \(\Theta(n)\).

Como mencioné anteriormente, existen otras formas de simular la conducta de las pilas y las colas sin la restricción de ser de tamaño fijo. Una de ellas es utilizando la siguiente estructura que veremos en la serie, llamada lista ligada (linked list), y la otra es utilizando un módulo que Python incluye dentro de su librería estándar.


En Python existe el módulo collections y dentro de él la estructura deque la cual soporta operaciones como:

  • append y append_left: Que insertan un elemento al final o al principio de la colección
  • pop y pop_left: Que eliminan un elemento al final o al principio de la colección.

de las cuales todas son \(O(1)\).

from collections import deque

d = deque()
>>> []

for i in range(10):
    if i % 2 == 0:
        d.append(2**i)
    else:
        d.appendleft(2**i)
>>> [512, 128, 32, 8, 2, 1, 4, 16, 64, 256]

for i in range(5):
    if i % 2 == 0:
        d.pop()
    else:
        d.popleft()
>>> [32, 8, 2, 1, 4]

Realmente será raro tener la necesidad de implementar éstas estructuras desde cero, o cualquiera de las que veremos adelante, a menos que estemos resolviendo problemas tamaño Google y necesitemos optimizar cada componente de ellas, pero seguramente para esto se estará usando algún lenguaje de bajo nivel como C o C++.

Recursos