Estructura de Datos – Pilas en Python

Pila

Estructura de Datos: Pilas en Python

Hola a todos, primero quiero agradecer su apoyo al seguir el blog. Luego de unos días de descanso para poder pensar algunas cosas, aquí traigo un rápido ejemplo, del que me sugirieron escribir vía Twitter. El tema que vamos a revisar en esta ocasión, será el tema perteneciente a la asignatura de Estructuras de Datos: Pilas.

Para esto, los ejemplos que veremos serán llevados a cabo utilizando el lenguaje Python. Esto debido a que el objetivo de esta entrada es que el concepto quede claro para todos, y así pueda ser aplicado en cualquier lenguaje.

Pilas en Python¿Qué es una Pila?

Bien, una pila como estructura de datos, funciona exactamente cómo sucede en el mundo real en un conjunto de objetos superpuestos verticalmente. Imagina que eres estudiante, y estás buscando un objeto en tu mochila. Por más que mueves las cosas no logras encontrar lo que buscas, así que comienzas a sacar tus libros y los apilas, uno sobre otro. Con esto lograste ubicar el objeto que buscabas, paso siguiente, pones los libros de regreso en tu mochila, comenzando por el libro que se encuentra en el tope de la pila, y así hasta llegar al último. (Ya que confío en que eres ordenado).

Libros_apilados: Pilas en PythonSi analizamos un poco el ejemplo, podemos notar ciertas cosas, al agregar un nuevo elemento (un libro) a la pila, pasará a colocarse en el tope, ya que siempre en una pila, el último elemento en ingresar a la pila, será el tope de la misma. Mientras que para eliminar un elemento (guardar un libro) comenzaremos por el último en haber sido introducido a la pila (que se encuentra en el tope).

Esto es debido a que las pilas, son una estructura de datos del tipo LIFO (“Last In, First Out”), lo que nos dice que el último elemento en ingresar a la pila, será el primero en salir de ella. Espero el concepto haya quedado claro, de no ser así, tal vez con el siguiente ejemplo lo puedan comprender mejor.

Las operaciones distintivas de una pila son: pop(), para sacar (remover) el elemento en el tope de la pila y push() para empujar (añadir) un elemento en el tope. Cada vez que se realiza una operación push() la pila aumenta de tamaño y el tope se modifica siendo ahora el elemento añadido. En el caso de la operación pop() disminuye el tamaño de la pila, y el tope ahora será el elemento debajo del elemento a ser removido, generalmente esta operación devuelve el elemento removido. Otra operación que generalmente se implementa en una pila, es peek(), que devuelve el elemento que se encuentra como tope de la pila, sin removerlo.

Creando una pila con Python

class Stack:
elements = []

def __init__(self):
self.elements = []

def get_size(self):
return len(self.elements)

def push(self, x):
self.elements.append(x)

def pop(self):
return self.elements.pop()

def get_peek(self):
return self.elements[-1]

peek = property(fget=get_peek)
size = property(fget=get_size)


s = Stack()
s.push("a")
s.push("b")
s.push("c")
s.push("d")
s.push("e")
s.push("f")
s.push("h")

El código es algo simple, definimos una clase, la cual será nuestra Pila, que contiene un atributo elements, el cual será una lista vacía. Con __init__() establecemos la lista como vacía al crear una nueva instancia. Contiene un método get_size(), que retorna el tamaño de la pila, push() para añadir un elemento al tope de la pila, pop() para remover el elemento en el tope y devolverlo y get_peek(), que nos devuelve el elemento en el tope sin removerlo, en este caso utilizamos la expresión elements[-1], que es la forma de obtener el último elemento de una lista (recuerdan que en Python, una pila no es más que una lista).

Paso seguido creamos una instancia y añadimos algunos valores a nuestra pila, quedando de esta forma:

Pila recién creada: Pilas en PythonComo se observa, h es el elemento que se encuentra en el tope de la pila. Si ejecutamos las operaciones mencionadas anteriormente. get_size() devuelve el valor de 8, con get_peek() obténdremos “h”, y con pop() también obtendremos “h”, la diferencia es que ahora nuestra pila se encuentra de la siguiente forma.

Pila luego de Pop: Pilas en PythonSi observas, ahora el tope de la pila es “g”, y el tamaño actual es de 7.

Este ejemplo podría mejorarse un poco. Se podría añadir una validación para evitar que se intente hacer pop() si la lista se encuentra vacía, te invito a realizarlo a modo de práctica y lo expongas en los comentarios.

La pila es probablemente una de las estructuras de datos más utilizadas en el ámbito de la programación, y de la informática en general me atrevería a decir. Son utilizadas en ocasiones de manera inconsciente, cuando definimos algoritmos recursivos, dado que los lenguajes de programación implementan este mecanismo mediante una pila que almacena los llamados recursivos.

Y bien, es todo por ahora, espero haber sido lo suficientemente claro, y que los conceptos hayan quedado claros. Cualquier comentarios no dudes en escribirme, ya sea a mi cuenta de Twitter, en donde te invito a que me sigas, como en la FanPage de Facebook, la cual te invito a que le des Me gusta para que te mantengas al tanto de anuncios y nuevas entradas que iré publicando.

Saludos.

Técnicas de programación: Patrón memoize

Patrón Memoize

Hola a todos, bienvenidos a una nueva entrada de este blog, y en esta ocasión vengo a escribir sobre un tema que a muchos les será de utilidad. Conoceremos qué es el patrón memoize o de memorización con ayuda de nuestro buen amigo, el lenguaje Python en su versión 3.6.0.

¿Qué es el patrón memoize o de memorización?

El patrón memoize consiste en almacenar las soluciones calculadas previamente, para evitar que sean recalculadas, logrando con esto, reducir el tiempo computacional de nuestros algoritmos.

Este patrón es empleado en diversas técnicas de programación, entre ellas, la programación dinámica, ¿sencillo, no lo creen?

Creo que un ejemplo permitirá que esto quede más claro. Para ilustrar esto, escribiremos un decorador que siga este patrón, por lo tanto, almacenará las soluciones en un diccionario para ser reutilizadas al ser requeridas nuevamente.


#!/usr/bin/env python
# -*- coding: utf-8 -*-


def memoize(f):
memory = {}

def wrapper(n):
if n not in memory:
memory[n] = f(n)
return memory[n]
return wrapper

 

Como podemos observar, el código no debería resultar demasiado complejo. Es la definición de una función decorator. Si miramos detenidamente el código, observamos que la función memoize recibe un argumento f, que se trata de la función que será “decorada”.

Paso siguiente, se define un diccionario, el cual almacenará los valores que se vayan calculando en la función. Tenemos nuestra función de envoltura (wrapper), la cual recibe un argumento n, que se trata del valor que está siendo calculado.

Dentro de nuestra función de envoltura, se verifica que el elemento no se encuentra en nuestro diccionario, si la condición se cumple entonces lo añade al mismo, de lo contrario, simplemente retorna el elemento desde el diccionario. Y por último, devuelve la función de envoltura.

Poniendo en práctica nuestra función memoize

Un problema que aprovecha enormemente este patrón, es el conocido problema de encontrar el n-ésimo número de la sucesión de Fibonacci. Así que, primero vamos a crear nuestra función para lograr tal objetivo.


def fibonacci(n):
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)

 

Como podemos apreciar, estamos utilizando la versión recursiva de la función para realizar la operación. Con esto, podemos apreciar de mejor forma las ventajas del patrón memoize. En principio este algoritmo genera un árbol recursivo, el cual se halla plagado de subárboles que corresponden a casos resueltos en diferentes ramas, y por lo tanto, están siendo recalculados.  En la siguiente imagen podemos ver la explosión arbórea cuando n = 6.

qué es el patrón memoizePara evitar esta situación, podemos valernos de una solución de ramificación y poda, utilizando el decorador memoize que creamos previamente, evitando así cálculos innecesarios.


# Utilizando Memoize
@memoize
def fib_memoize(n):
if n < 2:
return n
return fib_memoize(n - 1) + fib_memoize(n - 2)

 

Lo sé, lo sé, seguro están pensando que no hay forma de comprobar que realmente esto funciona. Hagamos algo, modifiquemos un poco el código del decorador para que indique cuando una solución ha sido calculada previamente, con esto podremos apreciar que la memorización se está llevando a cabo.


# Decorador mejorado, para visualización
def memoize_debug(f):
memory = {}

def wrapper(n):
if n not in memory:
memory[n] = f(n)
else:
print("Result was previously calculated: {0}".format(n))
return memory[n]
return wrapper

 

De igual forma, vamos a modificar nuestra función fib_memoize para que utilice nuestro nuevo decorador.


@memoize_debug
def fib_memoize(n):
if n < 2:
return n
return fib_memoize(n - 1) + fib_memoize(n - 2)

 

Si realizamos la prueba de nuestra función, el resultado para n=6 será.

In[1]: fib_memoize(6)

Result was previously calculated: 1
Result was previously calculated: 2
Result was previously calculated: 3
Result was previously calculated: 4

Out[1]: 8

Les dejo el código en el repositorio en Github.

Por esta ocasión es todo, espero los conceptos hayan quedado claros, de lo contrario, no duden en escribir sus dudas en los comentarios. No olviden seguirme en mis redes, ya sea twitter, o en la fanpage en Facebook. Y bien, hasta la próxima entrada.

Desarrollo dirigido por pruebas – Python y Pytest

pytest logo

Desarrollo dirigido por pruebas

Hola a todos, en esta entrada quiero hablar de un tema que me gusta mucho, y que estoy seguro a ustedes también, hablo del desarrollo dirigido por pruebas o TDD. En esta entrada veremos que es TDD, algunos ejemplos y conoceremos una excelente herramienta para llevar esta metodología de desarrollo a la práctica, Pytest.

¿Qué es el desarrollo dirigido por pruebas o TDD?

TDD proviene de Test-Driven Development, lo cual no es más que una técnica de diseño e implementación de software incluida dentro de la metodología ágil. TDD es una técnica para diseñar software que se centra en tres pilares fundamentales:

  • La implementación de las funciones justas que el cliente necesita y no más.
  • La minimización del número de defectos que llegan al software en fase de producción.
  • La producción de software modular, altamente reutilizable y preparado para el cambio.

Al dar los primeros pasos en este tema, muchos suelen caer en la idea equivocada de que TDD se utiliza para que el proyecto, o mejor aún, el código que se está escribiendo, termine cargado con una amplia cobertura de pruebas (casos de uso), y aunque esto no es del todo herrado, y siempre se agradece, la idea principal detrás de TDD es convertir a los programadores en verdaderos desarrolladores.

¿Qué quiero decir con esto? En principio, cualquier persona después de un tiempo de leer libros y ver videos en internet, puede escribir código, pero para considerarse un verdadero profesional, debes ir más allá, conocer metodologías, patrones de diseño de software, pruebas unitarias, etc. Y para lograr esto, TDD nos ayuda bastante.

Cuando por fin nos sentimos cómodos trabajando con TDD (desarrollo dirigido por pruebas) podemos contar con características que de otra manera, sería muy laborioso añadir a nuestro flujo de trabajo en el diseño de software.

Ciclo de un desarrollo dirigido por pruebas

  • Enfocarse en un requerimiento a la vez: Se elige de una lista de requerimientos, aquél que se cree que nos dará mayor conocimiento del problema y que a la vez sea fácilmente implementable.
  • Escribir una prueba: Se comienza escribiendo una prueba para el requisito. Para ello el programador debe entender claramente las especificaciones y los requisitos de la funcionalidad que está por implementar. Este paso nos orilla como programadores a tomar la perspectiva de un cliente considerando el código a través de sus interfaces.
  • Verificar que la prueba falla: Si la prueba no falla es porque el requerimiento ya estaba implementado o porque la prueba no ha sido escrita correctamente.
  • Escribir la implementación: Escribir el código lo más sencillo posible, a modo de que haga que la prueba funcione. Se usa la expresión “Mantenlo simple, Es**.” (“Keep It Simple, Stupid!”), conocida como principio_KISS.
  • Ejecutar las pruebas automatizadas: Verificar que todas las pruebas escritas funcionan correctamente.
  • Eliminación de duplicación de código: El paso final es la refactorización, que se utilizará principalmente para eliminar código duplicado. Se van añadiendo pequeños cambios al código a modo de iteraciones, siempre asegurandose de ejecutar las pruebas para asegurarse de que mantiene un correcto funcionamiento.
  • Actualización de la lista de requisitos: Se actualiza la lista de requerimientos tachando el requerimiento implementado. Asimismo se agregan requerimientos que se hayan visto como necesarios durante este ciclo y se agregan requerimientos de diseño, ya que puede darse el caso en que se encuentre un requerimiento que se encuentre ligado a uno ya establecido previamente.

Una de las mayores ventajas de escribir código utilizando TDD es que rara vez tienes que hacer uso de un depurador. Aunque como cualquier cosa tiene sus desventajas, la más importante, es que para llevar a cabo esta práctica correctamente se requiere de mucha paciencia y dedicación para que las pruebas (casos de uso) que establezcamos sean lo más adecuados posibles.

Ejemplos de TDD (desarrollo dirigido por pruebas) con Python

pytest logoPara los siguientes ejemplos voy a hacer uso de mi librería de testing preferidad de las opciones que podemos encontrar para Python, hablo de Pytest.

¿Qué es Pytest?

Cómo lo describen en su página oficial:

“The pytest framework makes it easy to write small tests, yet scales to support complex functional testing for applications and libraries.”

Y es que es verdad, existen bastantes opciones para desarrollar mediante TDD con Python, pero sólo con Pytest he podido encontrar esa flexibilidad y facilidad con la que me siento tan contento. Para utilizar pytest, basta con instalarlo como cualquier otro paquete


$ pip install pytest

Para escribir nuestras pruebas, debemos hacerlo utilizando archivos con el prefijo “test_”.

Realicemos un sencillo ejemplo del ciclo de desarrollo con TDD. Primero creamos un directorio de trabajo y nos posicionamos dentro del mismo.


$ mkdir [DIRECTORIO] && cd [DIRECTORIO]

No te olvides de reemplazar [DIRECTORIO] con el nombre que le quieras dar tu mismo, en mi caso será tdd_example. Ahora, en este directorio creamos el archivo donde escribiremos nuestro código, en mi caso se llamará test_add.py.


$ touch test_add.py

Ahora, comencemos a escribir nuestro código siguiendo TDD.

  • Recordando el ciclo del desarrollo dirigido por pruebas, debemos elegir un requerimiento, en mi caso será sumar 2 números.
  • Escribimos nuestra prueba.

# Prueba la función con los valores (4, 5)
# Resultado: 9 (True)
def test_add():
assert add(4, 5) == 9

  • Verificamos que la prueba implementada falle, ya que en este punto el requerimiento no se encuentra implementado.

$ pytest

Veremos como nos aparecen mensajes de error, diciendo que no se encuentra implementado el método add, justo lo que esperabamos.

  • El siguiente punto es escribir nuestra implementación.

def add(x, y):
return x + y

  • Ahora, volvemos a ejecutar la prueba para validar el correcto funcionamiento de nuestra implementación.

$ pytest

Nos dará una salida con información de la ejecución, y un mensaje diciendo que todo ha sido ejecutado correctamente.

Y bien, creo que es todo por ahora, aún faltaron algunos pasos, pero siendo un ejemplo tan básico, no lo vi necesario, así mismo, invito a todos a que realicen experimentos más complejos, y lean la documentación de pytest para que lo implementen en sus desarrollos del día a día.

Espero te haya agradado esta entrada, y cualquier comentario no dudes en hacermelo saber por este medio, o en mi cuenta de Twitter.

También te invito a que me sigas en mis redes (Twitter, Facebook) y si te gusta lo que escribo, compartas el blog.

Hasta la próxima.