El contenido de este documento son apuntes del Curso de POO y Algoritmos con Python y busca ser una guía a través de los conceptos de la programación orientada a objetos y algoritmos. El mismo está dictado por David Aroesti del team Platzi.
Objetivos del documento:
- Entender como funciona la Programación orientada a Objetos
- Entender cómo medir la eficiencia temporal y espacial de nuestro algoritmos.
- Entender cómo y por qué graficar.
- Aprender a resolver problemas de búsqueda, ordenación y optimización.
Uno de los elementos más importantes de los lenguajes de programación es la utilización de clases para organizar programas en módulos y abstracciones de datos.
La clave para entender la programación orientada a objetos es pensar en objetos como agrupaciones de datos y los métodos que operan en dichos datos.
La programación orientada a objetos nos permite modelar cosas reales y concretas del mundo y sus relaciones con otros objetos.
Por ejemplo:
- Representar a una persona con propiedades como nombre, edad, género, etc. y los comportamientos de dicha persona como caminar, cantar, comer, etc.
- Representar unos audífonos con propiedades como su marca, tamaño, color, etc. y sus comportamientos como reproducir música, pausar y avanzar a la siguiente canción.
Cuando decimos "Los objetos son las principales cosas que un programa de Python manipula. Cada objeto tiene un tipo que define qué cosas puede realizar un programa con dicho objeto.", nos estamos refiriendo a las ideas principales de la programación orientada a objetos. Hemos utilizado los tipos lista y diccionario, entre muchos otros, así como los métodos asociados a dichos tipos.
Así como los creadores de un lenguaje de programación sólo pueden diseñar una fracción muy pequeña de todas las funciones útiles (como abs, float, type, etc.), también pueden escribir una fracción muy pequeña de los tipos útiles (int, str, dict, list, etc.). Ya sabemos los mecanismos que nos permiten crear funciones, ahora veremos los mecanismos que nos permiten crear nuevos tipos (o clases).
Las clases nos permiten crear nuevos tipos que contiene información arbitraria sobre un objeto. En el caso del hotel, podríamos crear dos clases Hotel() y Cuarto() que nos permitiera dar seguimiento a las propiedades como número de cuartos, ocupación, aseo, tipo de habitación, etc.
Es importante resaltar que las clases sólo proveen estructura. Son un molde con el cual podemos construir objetos específicos.
Para definir una clase, simplemente utilizamos el keyword class. Por ejemplo:
class Hotel:
passLa clase señala las propiedades que los hoteles que modelemos tendrán, pero no es ningún hotel específico. Para eso necesitamos las instancias.
Mientras que las clases proveen la estructura, las instancias son los objetos reales que creamos en nuestro programa: un hotel llamado PlatziHotel o Hilton.
Una vez que tenemos una clase llamada Hotel podemos generar una instancia llamando al constructor de la clase.
hotel = Hotel()Los atributos de clase nos permiten:
- Representar datos.
- Procedimientos para interactuar con los mismos (métodos).
- Mecanismos para esconder la representación.
Para acceder a los atributos de estos objetos se hace a través de la notación de punto. Además puede tener atributos privados (Por convención comienzan con _ ).
Los atributos de la instancia describen lo que representa el objeto.
Todas las clases crean objetos y todos los objetos tienen atributos. Utilizamos el método especial __init__ para definir el estado inicial de nuestra instancia.
Recibe como primer parámetro obligatorio self (que es simplemente una
referencia a la instancia).
class Hotel:
def __init__(self, numero_maximo_de_huespedes, lugares_de_estacionamiento):
self.numero_maximo_de_huespedes = numero_maximo_de_huespedes
self.lugares_de_estacionamiento = lugares_de_estacionamiento
self.huespedes = 0
hotel = Hotel(numero_maximo_de_huespedes=50, lugares_de_estacionamiento=20)
print(hotel.lugares_de_estacionamiento) # 20Los métodos de instancia nos indican qué podemos hacer con las instancias de dicha clase y normalmente operan en los mencionados atributos.
Los métodos son equivalentes a funciones dentro de la definición de la clase, pero todos reciben self como primer argumento.
class Hotel:
...
def anadir_huespedes(self, cantidad_de_huespedes):
self.huespedes += cantidad_de_huespedes
def checkout(self, cantidad_de_huespedes):
self.huespedes -= cantidad_de_huespedes
def ocupacion_total(self):
return self.huespedes
hotel = Hotel(50, 20)
hotel.anadir_huespedes(3)
hotel.checkout(1)
hotel.ocupacion_total() # 2Estructura de la definición de una clase
# definición de clase
# Primero definimos el nombre de la clase y podemos determinar si hereda de otra clase.
class nombre_de_la_clase(super_clase):
# El método init es un constructor, y siempre los métodos dentro
# de los parámetros inician con el parámetro self
def __init__(self, params):
expresion
# Las clases pueden tener comportamientos,
# y estos los definimos con los métodos.
def nombre_del_metodo(self, params):
expresionEjemplo:
# Definición
class Persona:
def __init__(self, nombre, edad):
self.nombre = nombre
self.edad = edad
def saluda(self, otra_persona):
return f'Hola {otra_persona.nombre}, me llamo {self.nombre}.'
# Uso
>>> david = Persona('David', 28)
>>> karl = Persona('Karl', 26)
>>>
>>> david.saluda(karl)
>>> 'Hola Karl, me llamo David'En Python todo es un objeto y tiene un tipo, esto significa que todo lo que hacemos en nuestro programa tiene una representación en memoria, los datos y el comportamiento se puede encapsular en un objeto.
Los tipos nos permiten modelar y manipular el mundo a través de la programación.
Las formas de interactuar con un objeto son:
- Creación
- Manipulación
- Destrucción
Cuando trabajamos con programación orientada a objetos tenemos varias ventajas:
- Decomposición: podemos estructurarlos en objetos mas pequeños.
- Abstracción: no nos preocupamos el funcionamiento del proceso de su comportamiento.
- Encapsulación: podemos esconder ciertos datos que solo son relevantes internamente en el objeto.
Primera practica de POO en Python
La decomposición es partir un problema en problemas más pequeños.
Las clases permiten crear mayores abstracciones en forma de componentes.
Cada clase se encarga de una parte del problema y el programa se vuelve más fácil de mantener.
Practica. Ejemplo simple en el cual se trata de modelar un automovil y decomponer en clases que representen a otros objetos, ejemplo, Motor.
Se trata de enfocarnos en la información relevante. Se debe separar la información central de los detalles secundarios. Para realizar este procedimiento podemos utilizar variables y métodos (privados o públicos). Más info en Wiki
Practica. Ejemplo simple en el cual se trata de modelar una Lavadora y abstraerse del funcionamiento de la misma con métodos ocultos.
En programación modular, y más específicamente en programación orientada a objetos, se denomina encapsulamiento al ocultamiento del estado, lo que hacemos específicamente es proteger los datos miembro de un objeto de manera que solo se pueda cambiar mediante las operaciones definidas para ese objeto. Más info en Wiki
Esto nos asegura por ejemplo que “no podremos modificar un atributo si no es a través de un método que hallamos creado específicamente para ello” y aquí es donde nacen los famosos “Getter, Setter, Deleter”. Se
En python las propiedades y métodos privados no existen, por lo que son fácilmente sobre-escribibles.
class usuario (object):
def __init__(self, nombre, clave):
self.nombre = nombre
self._clave = clave # ATRIBUTO PROTEGIDO
Usuario1 = usuario ("Roberto", "qwerty")
print (Usuario1.nombre, Usuario1._clave)En el caso de un atributo privado estamos indicando que este solo podrá ser accedido o modificado si se especifica la clase precedida por un guión bajo seguida del atributo precedido por doble guión bajo.
class usuario (object):
def __init__(self, nombre, clave):
self.nombre = nombre
self.__clave = clave
Usuario1 = usuario ("Roberto", "qwerty")
print (Usuario1.nombre, Usuario1._usuario__clave) # FORMA DE ACCEDER AL ATRIBUTO PRIVADOPodemos acceder igualmente a un atributo por más que sea privado y modificarlo de la misma manera. Pero no es lo que se “considera correcto”. Por lo que para ello si deseamos implementar métodos que nos permitan modificar estos atributos de la forma que se suele hacer en otros lenguajes donde se aplica “encapsulamiento” podemos hacerlo utilizando Getter, Setter, Deleter mediante el uso del decorador @Property.
La función integrada property() nos permitirá interceptar la escritura, lectura, borrado de los atributos y ademas nos permiten incorporar una documentación sobre los mismos.
Si nosotros no pasamos alguno de los parámetros su valor por defecto sera None.
-
Getter: Se encargará de interceptar la lectura del atributo. (get = obtener)
-
Setter : Se encarga de interceptar cuando se escriba. (set = definir o escribir)
-
Deleter : Se encarga de interceptar cuando es borrado. (delete = borrar)
-
doc : Recibirá una cadena para documentar el atributo. (doc = documentación)
Practica. Ejemplo simple en el cual se trata de modelar un Perro y encapsular las propiedades o atributos del mismo. Luego se trata de obtener (get), definir y/o escribir (set) y borrar (delete) estas propiedades utilizando el decorador @property con los métodos adecuados para realizar las acciones anteriores.
La herencia permite modelar una jerarquía de clases, con el cual compartiremos comportamientos en común. Al padre se le conoce como superclase y al hijo como subclase.
Practicando. Ejemplo simple en el cual se modela un Rectangulo con su defición. Luego un Cuadrado hereda el comportamiento de esta última sabiendo que es una caso especial donde la base y la altura son iguales.
La herencia simple tiene lugar cuando una clase hija hereda los atributos y métodos de una única clase padre.
Para que sea posible la herencia de atributos y métodos de una clase, debe existir la superclase o clase principal de la cual la clase hija o secundaria va a heredar. Es decir, para que exista un hijo debe de existir un padre.
Supongamos que nosotros heredamos algunas virtudes y defectos de nuestros padres. Ellos serían nuestras clases primarias, o base. Y nosotros seríamos la secundaria o hija.
Los casos de herencia múltiple en python se dan cuando una clase secundaria o hija hereda atributos y metodos de mas de una clase principal o padre.
-
Ayuda a ahorrar código y tiempo.
-
Los objetos pueden ser construidos a partir de otros similares. Para ello es necesario que exista una clase base (que incluso puede formar parte de una jerarquía de clases más amplia).
-
La clase derivada hereda el comportamiento y los atributos de la clase base, y es común que se le añada su propio comportamiento o que modifique lo heredado.
-
Toda clase pueden servir como clase base para crear otras.
El polimorfismo es la habilidad de tomar varias formas, en este caso la habilidad de cambiar el comportamiento de un método.Este concepto esta estrechamente ligado con la herencia y que nos permite cambiar el comportamiento de una superclase para adaptarlo a la subclase solo nombrando el método y escribiendo su comportamiento.
Practica. Se crea una clase padre llamada Persona que avanza. La segunda clase Ciclista hereda de Persona, pero avanza en bicicleta. El comportamiento anterior se observa en el ejemplo.
La complejidad algorítmica nos permite comparar la eficiencia de 2 algoritmos. Esto a su vez nos permitirá predecir el tiempo que va a tomar resolver un problema.
Podemos analizar la complejidad desde:
- La perspectiva temporal. La complejidad algorítmica temporal la podemos definir como T(n) el cual determinara el tiempo que demora en resolver nuestro algoritmo.
- La perspectiva espacial, como por ejemplo cuanto espacio en memoria necesitamos.
En Resumen:
- Podemos medir la complejidad de los problemas y sus respectivos algoritmos.
- Fundamental en computación.
- NO ES LO MISMO la complejidad de un problema que la forma de resolverlo.
¿Como podríamos aplicar nuestra función T(n)?
-
Cronometrar el tiempo en el que corre un algoritmo. Sin embargo no es una buena forma de medir los algoritmos, ya que no se puede predecir cuanto demorara a medida que crece nuestros pasos.
-
Contar los pasos con una medida abstracta de operación. Nos puede acercar a una medición ideal, sin embargo varia mucho de algoritmo en algoritmo y a medida que crece nuestro dataset existen muchos términos que llegan a ser irrelevantes.
-
Contar los pasos conforme nos aproximamos al infinito pero con una medida asintótica.
Practica. En la siguiente práctica se analiza la complejidad algoritmica y se trata de demostrar como el tiempo cambia de un algoritmo iterativo y otro recursivo.
Con esta técnica contamos los pasos que realiza nuestro algoritmo. En el siguiente ejemplo respuesta tendrá los números de pasos que realiza nuestro código al ejecutar.
def f(x):
# Primera operación
respuesta = 0
# Segunda operacion. Sin importar de x este loop correrá 1000 veces.
for i in range(1000):
respuesta += 1
# Tercera operación. Este loop correrá el valor de x
for i in range(x):
respuesta += x
# Cuarta operación. Esta parte esta corriendo 2 loop. Esto será 2x²
for i in range(x):
for j in range(x):
respuesta += 1
respuesta += 1
# Quinta operación.
return respuesta
# Respuesta
# 1002 + x + 2x²Los términos que más importan son los más grandes, osea, conforme nuestro problema se va haciendo más grande sólo nos importa el término más grande. La Big O notation no permitirá analizar los términos mas irrelevantes el algoritrmo y sólo concentrarnos en los mas importantes.
¿Como comparar algoritmos? Podemos tomar el tiempo que tardan estos en correr, pero esto resulta ineficiente y depende del hardware directamente.
La segunda opción es contar la cantidad de pasos que dá el algoritmo. Pero nos dimos cuenta que hay terminos que no importan cuando se van al infinito.
Antes de analizar la mejor forma de analizar un algoritmo se debe entender que es Asintótico. Esto significa que conforme la función se va al infinito o el input crece hacia el infinito.
Teniendo tal concepto aclarado debemos tener en cuenta que no importan las variaciones pequeñas. Lo que realmente importa es centrarse en lo que pasa conforme el tamaño del problema se acerca al infinito.
Siempre tenemos que estar preparados para cualquier caso, por lo que tenemos que saber medir a nuestro algoritmo en el mejor de los casos, el caso promedio y peor de los casos.
Lo que mejor nos permite comparar y entender cual es la complejidad real algoritmica a la cual nos estamos enfrentando es el peor de los casos. En este caso es cuando entra el Big O Notation.
Big O Notation lo que importa es nada mas el término de mayor tamaño.
Ejemplos de como poder trabajar con Big O:
def f(n):
for i in range(n):
print(i)
for i in range(n):
print(i)
# En este caso el mayor término es n
# O(n) + O(n) = O(n + n) = O(2n) = O(n)def f(n):
for i in range(n):
print(i)
for i in range(n * n):
print(i)
# En este caso el mayor término es n²
# O(n) + O(n * n) = O(n + n²) = O(n²)def f(n):
for i in range(n):
for i in range(n):
print(i, j)
# En este caso el mayor término es n²
# O(n) + O(n * n) = O(n * n) = O(n²)def fibonacci(n):
if n == 0 or n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
# En este caso el mayor término es 2**n (el símbolo ** denota "elevado a"),
# ya que realiza recursividad 2 veces por n veces.
# O(2**n)Big O Notation o Notación Big O es la representación relativa de la complejidad de un algoritmo.
Relativa: Solo puede comparar manzanas con manzanas. No puedes comparar un algoritmo con una multiplicación aritmetica que ordene una lista de enteros. Pero una comparación de dos algorítmos para hacer operaciones aritméticas (una multiplicación, una adición) te dirán algo significativo.
Representación: Big-O reduce la comparación entre algoritmos a una simple variable. Esta variable es elegida basandose en la observación.
Complejidad: Si algo me toma un segundo en ordenar 10 000 elementos, cuanto me tomará ordenar 1M?. La complejidad en esta instancia es una medida relativa a otra cosa.
Existen distintos tipos de complejidad algorítmica:
- O(1) Constante: no importa la cantidad de input que reciba, siempre demorara el mismo tiempo.
- O(n) Lineal: la complejidad crecerá de forma proporcional a medida que crezca el input.
- O(log n) Logarítmica: nuestra función crecerá de forma logarítmica con respecto al input. Esto significa que en un inicio crecerá rápido, pero luego se estabilizara.
- O(n log n) Log lineal: crecerá de forma logarítmica pero junto con una constante.
- O(n²) Polinomial: crecen de forma cuadrática. No son recomendables a menos que el input de datos sea pequeño.
- O(2^n) Exponencial: crecerá de forma exponencial, por lo que la carga es muy alta. Para nada recomendable en ningún caso, solo para análisis conceptual.
- O(n!) Factorial: crece de forma factorial, por lo que al igual que el exponencial su carga es muy alta, por lo que jamas utilizar algoritmos de este tipo.
En el siguiente enlace se observa la fuente el gráfico anterior y la clasificación de los algoritmos en función de la complejidad Big-O.
Se puede leer más al respecto en Eficiencia algorítmica.
Objetivos de esta sección:
- Aplicar los conceptos de complejidad algoritmica.
- Aprender algoritmos de búsqueda y ordenación para resolver problemas.
La búsqueda lineal o la búsqueda secuencial es un método para encontrar un valor objetivo dentro de una lista.Ésta comprueba secuencialmente cada elemento de la lista para el valor objetivo hasta que es encontrado o hasta que todos los elementos hayan sido comparados.
En la siguiente práctica se observa el algoritmo escrito. Analizando al mismo ¿Cuál es el peor caso? Si nos fijamos en el algoritmo existe un for loop que crece según el tamaño de la lista, por lo cual nuestro Big O es O(n).
La búsqueda binaria toma una estrategia llamada "Divide y conquista", la cual consiste en dividir el problema en 2 en cada iteración. Este algoritmo asume que la lista se encuentra ordenada, por lo que es necesario realizar este paso primero.
La búsqueda binaria es uno de los mejores algoritmos que se tienen hoy en día para búsqueda, ya que reduce significativamente el numero de pasos, y así disminuyendo nuestro Big O.
En la siguiente practica se muestra el algoritmo de busqueda binaria.
La búsqueda binaria es computada en el peor de los casos en un tiempo logarítmico, realizando O(log n) comparaciones, donde n es el número de elementos del arreglo y log es el logaritmo. La búsqueda binaria requiere solamente O(1) en espacio, es decir, que el espacio requerido por el algoritmo es el mismo para cualquier cantidad de elementos en el array.
En los siguientes gif's se muestran los mejores casos, caso promedio y peor caso de busqueda binaria y lineal, comparando ambos.
En el siguiente gráfico se puede observar una comparativa entre el algoritmo de busqueda lineal y binaria, donde se analiza el numero de pasos que debe realizar el algoritmo en función del tamaño de la lista.
El algoritmo de ordenamiento burbuja es un algoritmo que recorre repetidamente una lista que necesita ordenarse. Compara elementos adyacentes y los intercambia si están en el orden incorrecto. Este procedimiento se repite hasta que no se requiere mas intercambios, lo que indica que la lista se encuentra ordenada.
En la siguiente practica se muestra el algoritmo de ordenamiento burbuja.
El algoritmo de ordenamiento por inserción lo que hace es tomar una lista y luego esta es dividida entre una sublista ordenada y otra sublista desordenada. Al principio, la sublista ordenada contiene un solo elemento, por lo que por definición se encuentra ordenada.
A continuación se evalua el primer elemento dentro la sublista desordenada para que podamos insertarlo en el lugar correcto dentro de la lista ordenada.
La inserción se realiza al mover todos los elementos mayores al elemento que se está evauluando un lugar a la derecha.
Continua el proceso hasta que la sublista desordenada quede vacia y, por lo tanto, la lista se encontrará ordenada.
En la siguiente practica se muestra el algoritmo de ordenamiento por inserción.
El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n).
Fue desarrollado en 1945 por John Von Neumann.
Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:
- Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:
- Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
- Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
- Mezclar las dos sublistas en una sola lista ordenada.
El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:
- Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
- Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.
En la siguiente practica se muestra el algoritmo de ordenamiento por mezcla.
Los ambientes virtuales permiten aislar el ambiente para poder instalar diversas versiones de paquetes. A partir de python 3 se incluye en la librería estándar en el módulo venv. Ningún ingeniero profesional de Python trabaja sin ellos.
Pip permite descargar paquetes de terceros para utilizar en nuestro programa, también permite compartir nuestros paquetes con terceros y también podemos definir la versión del paquete que necesitamos.
Para crear un ambiente virtual primer crearemos el directorio para nuestro proyecto. El proyecto se llamará graficando, el cual se utilizará para la siguiente sección.
>>:~$ mkdir graficado # Creamos el directorio del proyecto.
>>:~$ cd graficado/ # Ingresamos al directorio.
>>:~$ python3 -m venv env # Creamos un ambiente virtual en env.
>>:~$ source env/bin/activate # Activamos el ambiente.Una vez realizado lo pasos anteriores se ùeden instalar librerías con los siguientes comandos:
>>:~$ pip install bokeh # pip install instalara la librería.
>>:~$ pip freeze # Con pip freeze veremos que librerías están instaladas.Pip es como una tienda virtual para los desarrolladores e ingenieros de software que utilizan Python. En el siguiente navegador de proyectos se pueden observar todas las librerias que contiene Pip, y seleccionar la que mas se adecue o lo que necesitamos para nuestro proyecto.
Cuando graficamos podemos identificar rapidamente patrones adentro de los datos. Esto se debe a que nosotros como seres humanos gran parte de nuestra corteza cerebral se encuentra diseñada para poder identificar información visual muy rápido. Tambien podemos predecir series cuando las vemos graficadas.
Con lo anterior descripto simplificamos la interpretación y podemos sacar conclusiones acerca de los datos, ahorrandonos tiempo.
La librería Bokeh permite construir gráficas complejas de manera rápida y con comandos simples, también nos permite exportar a varios formatos como html, notebooks, imágenes, etc. Bokeh se puede utilizar en el servidor con Flask y Django.
En la siguiente practica podemos observar un graficado simple utilizando Bokeh.
El concepto de optimización permite resolver muchos problemas de manera computacional. Cuando pensamos en un algoritmo de optimización debemos definir una función objetivo que debemos maximizar o minimizar, respetando una serie de limitantes que definamos, o sea, es la selección del mejor elemento (con respecto a algún criterio) de un conjunto de elementos disponibles.
El problema de la mochila o del morral: Imagina que eres un ladrón que entra a un museo pero tienes un gran problema, nada mas tienes una mochila pero hay muchísimas cosas mas de las que puedes cargar, por lo cual debes determinar cuales artículos puedes cargar y te entregaran el mayor valor posible.
Para este problema sabemos que no podemos dividir los artículos, por lo que nuestra primera aproximación sera evaluar los artículos.
En la siguiente practica tenemos el codigo resolviendo un caso simple del problema del morral.
Volver a la tabla de contenido principal de la Escuela de Data Science
Continuar con Programación Dinámica y Estocástica con Python