Para esta nueva entrega en CódigoFacilito me gustaría hablemos sobre una forma más sencilla de implementar las estrcuturas de datos pilas y colas. Y no, no te preocupes, no implementaremos nuestras propias estructuras y/o algoritmos, si no que haremos uso de las que Python ya nos ofrece. Recordemos que Python viene con baterias incluidas.
Será un post sumamente interesante, así que te invito a que te quedes.
Bien, ahora sí, son más por añadir, comencemos.
Listas como estructuras
Probablemente los primero que se nos viene a la mente la oir los conceptos de pilas y colas en Python es pensar que podemos implementar estas estructuras con objetos de tipo listas, ya que las listas nos ofrecen los métodos insert, append y pop, métodos que, respectivamente, nos permite insertar un elemento en un índice en particular, insertar un elemento al final de la colección o eliminar el último elemento de la coleccíón.
Recordemos que las pilas y colas funciona con el principio el último en entrar es el primero en salir para las pilas y el primero en llegar es el primero en salir para las colas.
Por lo tanto, para implementar, por ejemplo una pila nuestro código pudiera quedar de la siguiente manera.
pila = []
# Agregar elementos a la pila (push)
pila.append(10)
pila.append(20)
pila.append(30)
# Eliminar elementos de la pila (pop)
elemento = pila.pop() # Elimina y retorna el último elemento agregado (30)
print(elemento) # Output: 30
# Imprimir la pila actual
print(pila) # Output: [10, 20]
Esto puede verse bien, y de hecho va funcionar, sin embargo si trabajamos con un gran número de datos, por ejemplo miles, cientos de miles o millones de registros, el perfomance comienza a decaer.
Tareas como insertar un nuevo elemento al principio de un colección de miles de registro es algo que ya computacionalmente hablando para python es costoso.
Veamos.
import timeit
def inser_elements():
numbers = []
for element in range(0, 100_000):
numbers.insert(0, element)
if __name__ == '__main__':
result = timeit.timeit(inser_elements, number=1)
print(result)
Una tarea como insertar 100K registros le toma a Python poco más de 2 segundos. Algo que no esta del todo bien.
Deque
Por lo tanto, siempre que quieres realizar tareas que impleque insertar o eliminar elementos al princio final de la colección, por ejemplo cuando trabajar con pilas o colas, te recomiendo dejar a un lado las listas y usar deque.
Deque por su abreviación: double-ended queue, es una lista doble mente finalizada, esto quiere decir que acciones como añadir al principio o final de la colección, o así como eliminar elementos al principio o final de la colección, tiene una complejidad O1, el mejor performance que podemos obtener en la notación Big O.
Y lo mejor de todo es que deque ya se encuentra en la biblioteca estandar de Python así que no hay que instalar absolutamente nada simplemente importamos y listo
Veamos.
from collections import deque
mi_deque = deque()
mi_deque.append(10)
mi_deque.append(20)
mi_deque.append(30)
mi_deque.appendleft(5)
print(mi_deque[1])
mi_deque.pop()
mi_deque.popleft()
print(mi_deque)
Importamos de collections y comenzamos a definir ya sea nuestro pila o cola.
Podemos añadir elementos al final de la colección con append, o añadir elementos al principio de la colección con appendleft.
Lo mismo con pop, para eliminar elementos de la derecha o popleft para eliminar elementos de la izquieda.
import timeit
from collections import deque
def inser_elements():
numbers = deque()
for element in range(0, 100_000):
numbers.appendleft(element)
if __name__ == '__main__':
result = timeit.timeit(inser_elements, number=1)
print(result)
Siguiendo con nuestro ejemplo anterior, utilizando deque logramos reducir el tiempo de ejecución para insertar un 100l registros de 2.23 segundo a
0.01 Milisegundos
Definitivamente Deque es la mejor opción para realizar tareas que impliequen adir o modificar elementos al principio o final de la colección.
Ahora ya lo sabes, siempre que quieres implementar una pila o cola con Python definitivamente te recomiendo usar Deque.
y cuéntanos, ya conocías Deque, ya lo has utilizado en alguno de tus proyectos, déjanoslo saber en la sección de comentarios.
